Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
+1 You beat me to the punch! –  Jyrki Lahtonen Aug 18 '11 at 18:34
    
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 !! –  TCSGrad Aug 18 '11 at 18:34
2  
@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. –  lhf Aug 18 '11 at 18:41
    
@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. –  Austin Mohr Aug 18 '11 at 20:22
    
@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?) –  lhf Aug 18 '11 at 21:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.