Check if point is within quadratic area.

Question

I have two dimensional Cartesian system and I need to check if certain point is within the geometry formed by four other points. I have few thousands different geometries all with different points to check. So I'm writing a program for it.

HERE is a solution method I started with and it works if the data points are always given in same order: A(x,y) B(x,y) C(x,y) and D(x,y) with the point P(x,y). (But it's not)

My points are randomly given, so when connecting between the dots they might go to "opposite" corner so the drawing wouldn't be box exactly.

Case 1: A(x,y) B(x,y) C(x,y) D(x,y) with the point P(x,y).
Case 2: C(x,y) A(x,y) D(x,y) B(x,y) with the point P(x,y).
Case 3: D(x,y) B(x,y) A(x,y) C(x,y) with the point P(x,y).
Case 4: B(x,y) D(x,y) A(x,y) C(x,y) with the point P(x,y).

So it's impossible to write a program with earlier mentioned method. I've been looking around and I can't seem to find a method that doesn't care in which order it gets the coordinates of the geometry.

Thanks.

Answer 1

Consider point $A$. We need to find which two of the three points $B,C,D$ are its neighbours in the quadrilateral. So we consider the three line segments (or we can consider them as 2-dimensional vectors): $AB,AC,AD$. If $A's$ neighbours are $B,C$, say, then $\angle BAC$ will be greater than both $\angle BAD$ and $\angle CAD$, and therefore their cosines will have the opposite relationship. So we look for the angle with the small cosine.

So calculate:

\begin{eqnarray*} \cos(\angle BAC) &=& \dfrac{AB\cdot AC}{\|AB\|\|AC\|} \\ \cos(\angle BAD) &=& \dfrac{AB\cdot AD}{\|AB\|\|AD\|} \\ \cos(\angle CAD) &=& \dfrac{AC\cdot AD}{\|AC\|\|AD\|}. \end{eqnarray*}

Whichever is the least of these determines the two neighbouring points of $A$.

You can then use the method from the other question you refer to to check for point $P$.

Example: $A=(-2,1),\quad B=(2,6),\quad C=(5,2),\quad D=(1,-4)$.

\begin{eqnarray*} AB &=& (2-(-2))\;\mathbf{i} + (6-1)\;\mathbf{j} = 4\mathbf{i} + 5\mathbf{j} \\ AC &=& (5-(-2))\;\mathbf{i} + (2-1)\;\mathbf{j} = 7\mathbf{i} + \mathbf{j} \\ AD &=& (1-(-2))\;\mathbf{i} + (-4-1)\;\mathbf{j} = 3\mathbf{i} - 5\mathbf{j} \\ && \\ \|AB\| &=& \sqrt{4^2+5^2} = \sqrt{41} \\ \|AC\| &=& \sqrt{7^2+1^2} = \sqrt{50} \\ \|AD\| &=& \sqrt{3^2+5^2} = \sqrt{34} \\ && \\ AB\cdot AC &=& 4\times 7 + 5\times 1 = 33 \\ AB\cdot AD &=& 4\times 3 + 5\times (-5) = -13 \\ AC\cdot AD &=& 7\times 3 + 1\times (-5) = 16 \\ && \\ \therefore\quad \cos\angle BAC &=& \dfrac{33}{\sqrt{41}\sqrt{50}} \\ \cos\angle BAD &=& \dfrac{-13}{\sqrt{41}\sqrt{34}} \\ \cos\angle CAD &=& \dfrac{16}{\sqrt{50}\sqrt{34}}. \end{eqnarray*}

The smallest cosine is $\cos\angle BAD$ so $A$'s neighbours are $B,D$ and the quadrilateral is $ABCD$.

Answer 2

Based on @bjartmar's assertion that the quadrilateral is convex, my preferred approach would be to consider the angle between the line joining P to each of the vertices and some given reference line. If the reference line were to be the North direction, then this would be like finding the bearing of each point from P. I prefer, however, to take the positive x-axis as the reference line.

Let $\hat \theta_i = \begin{cases} \tan^{-1}\left(\frac {y_i-y}{x_i-x}\right)&\textrm{ if }x_i\neq x\\ \frac \pi 2&\textrm{ if }x_i=x \end{cases}$

The standard way of calculating $\tan^{-1}$ means that $-\frac \pi 2 <\hat\theta_i\leq \frac \pi 2$

Make the following adjustments:

Let $\theta_i = \begin{cases} \hat \theta_i + \pi&\textrm{ if }x_i< x \textrm{ and } y_i>y\\ \hat \theta_i - \pi&\textrm{ if }x_i\leq x \textrm{ and } y_i<y\\ \hat\theta_i&\textrm{ otherwise } \end{cases}$

Now we have $- \pi <\theta_i\leq \pi$.

You can then arrange your vertices in increasing order of $\theta_i$