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 ?

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ That is what I'm trying to prove - how do i show that p lies to the left of every edge of the polygon ? Pls bear with me if its obvious - but I'm not getting it !! $\endgroup$
    – TCSGrad
    Commented Aug 18, 2011 at 18:34
  • 2
    $\begingroup$ @shan23, I assumed that this was clear: "if the determinant is positive if the three points are taken in a counter-clockwise orientation". If it is not, consider the simple case of one point being the origin, the other being $(1,0)$ and the third being $(x,y)$ and compute the determinant. This is indeed the general situation because the sign of the determinant is invariant by rotation and (positive) scaling. $\endgroup$
    – lhf
    Commented Aug 18, 2011 at 18:41
  • $\begingroup$ @lhf I'm sure you didn't intend it in this way, but the phrase "I assumed that this was clear" can be interpreted as an insult, particularly in a text-only environment. $\endgroup$ Commented Aug 18, 2011 at 20:22
  • $\begingroup$ @Austin, 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?) $\endgroup$
    – lhf
    Commented Aug 18, 2011 at 21:47
2
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .