3
$\begingroup$

I came across the following method to determine whether a given point lies inside a convex polygon - however, I'm not sure how to prove it.

Given any three points on the plane $(x_0,y_0)$, $(x_1,y_1)$, and $(x_2,y_2)$, the area of the triangle determined by them is given by the following formula:

$A=\frac12\begin{vmatrix}x_0&y_0&1\\x_1&y_1&1\\x_2&y_2&1\end{vmatrix},$

where the vertical bars represent the determinant. If you don't know what a determinant is, it doesn't matter too much; the value of the expression above is:

$\frac12(x_1 y_2 - y_1 x_2 -x_0 y_2 + y_0 x_2 + x_0 y_1 - y_0 x_1)$

The amazing thing is that $A$ is positive if the three points are taken in a counter-clockwise orientation, and negative otherwise.

To be inside a rectangle (or any convex body), as you trace around in a clockwise direction from $p_1$ to $p_2$ to $p_3$ to $p_4$ and back to $p_1$, the "areas" of triangles $p_1 p_2 p$, $p_2 p_3 p$, $p_3 p_4 p$, and $p_4 p_1 p$ must all be positive. If you don't know the orientation of your rectangle, then they must either all be positive or all be negative.

(I found the above method from here)

How do I prove that the above is correct ?

2 Answers 2

2

Subtracting any row in a matrix from the other rows does not affect the determinant of the matrix, so $ A=\frac{1}{2}\left|\begin{array}{c c c}x_0&y_0&1\\x_1-x_0&y_1-y_0&0\\x_2-x_0&y_2-y_0&0\end{array}\right| $ which, when expanded on the right column, does not depend on the top-left or the top-center elements, therefore $ A=\frac{1}{2}\left|\begin{array}{c c c}0&0&1\\x_1-x_0&y_1-y_0&0\\x_2-x_0&y_2-y_0&0\end{array}\right| $ Setting $P_k=(x_k,y_k,0)$, $A=\frac{1}{2}\overrightarrow{P_0P_1}\times\overrightarrow{P_0P_2}\cdot(0,0,1)$, which is the directed area of the triangle with $\overrightarrow{P_0P_1}$ and $\overrightarrow{P_0P_2}$ as sides projected onto the plane perpendicular to $(0,0,1)$, which is the plane in which $\overrightarrow{P_0P_1}$ and $\overrightarrow{P_0P_2}$ lies.

Taking the smallest angle, if $\overrightarrow{P_0P_2}$ is counter-clockwise from $\overrightarrow{P_0P_1}$, then $A>0$; if $\overrightarrow{P_0P_2}$ is clockwise from $\overrightarrow{P_0P_1}$, then $A<0$. Another way of looking at this is if $P_0$ is to the left of $\overrightarrow{P_1P_2}$, then $A>0$; if $P_0$ is to the right of $\overrightarrow{P_1P_2}$, then $A<0$.

6

The test you describe checks that $p$ is to the left of every edge of the polygon and so lies in the intersection of the corresponding half-planes, which is the polygon itself.

  • 0
    @A$u$stin, I meant *no* insult. I've just expressed myself badly. What I meant what that I assumed that the OP was clear about that statement. (Or am I making it worse now?)2011-08-18