3

Consider random triangle which is represented by 3 points on Cartesian plane.

Now, I want to check whether point (0,0) lies within the triangle.

There are several ways to solve this problem, but there is one that I cannot understand.

Assume we have three points with coordinates: (a1,a2),(b1,b2),(c1,c2)

Now, we find cross product of each pair

x1= a1*b2-a2*b1
x2= b1*c2-b2*c1 
x3= c1*a2-c2*a1

If x1>=0 and x2>=0 and x3>=0

OR x1<0 and x2<0 and x3<0

then point (0,0) is inside the triangle.

Can someone use plain English to explain why this method works?

Misha Lavrov
  • 142,276
Stokolos Ilya
  • 3,371

2 Answers2

1

$x_i$ is positive if $(0,0)$ lies on one side of the line segment that defines it (either left or right, depending on the handedness of the coordinate system), and negative if it lies on the other side. The point is in the triangle if and only if $(0,0)$ consistently remains on the same side of an observer walking around the triangle's edges in either direction – that is, if and only if the three $x_i$ have the same sign.

Parcly Taxel
  • 103,344
0

$(1/2)(a\times b)$ indicates the signed area enclosed by points $(0,0),(a_1,a_2),(b_1,b_2)$ in this order. That means on the perimeter of the triangle formed by $(0,0),(a_1,a_2),(b_1,b_2)$ if we traverse from $(0,0)\rightarrow (a_1,a_2)\rightarrow(b_1,b_2)$, and if the traversing is anticlockwise, then the area is given by $(1/2)(a\times b) = (1/2)ab\sin\theta$, where $\theta$ is the angle between a and b. You can easily draw and convince yourself.

If we traverse $(0,0)\rightarrow(b_1,b_2) \rightarrow (a_1,a_2)$ (that means clockwise) then area is given by $(1/2)(b\times a) = (1/2)ab\sin{(-\theta)} = -(1/2)ab\sin{(\theta)}$

Now for any polygon $a,b,c,..,n$ (not only triangle) where these vertexes are in order clockwise or anticlockwise if $\textbf{the origin is inside it}$ and we start traversing from 0 to a to b then again 0, this is the area $(1/2)(a\times b) = (1/2)ab\sin\theta_1$ if we have traversed anticlockwise otherwise $-(1/2)ab\sin\theta_1$. Suppose we traversed anticlockwise then we see that $\textbf{traversing from o to b to c to 0, will be also anticlockwise}$ this is the area given by $(1/2)(b\times c)$ so the $\textbf{sign will be also positive}$. Similarly sign of $(1/2)(c\times d)$,...sign of $(1/2)(n\times a)$ all will be positive.

If $(1/2)(a\times b)$ is negative then all the above signs will be negative.

note: cross product is zero means area is zero.

amitava
  • 838