The input to the algorithm is eight numbers: the x,y coordinates of a single point, P, and 3 pairs of x,y coordinates giving the corners A, B, and C of the triangle.
The output from the algorithm is the word "Inside" if the point is inside the triangle, or the words "Not Inside" if the point is not inside the triangle.
Here's the logic:
Imagine standing on one corner of the triangle, looking at the next corner. Keep point P in view, noting whether it's somewhere on your left or on your right or neither. Now walk along the side of the triangle. When you get to the second corner, turn to face the third corner, keeping point P in view. Walk along the second side of the triangle. When you get to the third corner, turn to face the first corner, still keeping point P in view. Now walk along the third side of the triangle back to the point from which you started. Did P stay on the same side of you during your entire trip? That is, did P stay always on the left or always on the right? If so, P is inside the triangle. If not, P is not inside the triangle.
So the crux of this program is to develop a function that tells us whether a point is to the "left" or "right" of a particular line as we look in a particular direction along the line. Here's how we do that.
Given two different points, A=(x1,y1), and B=(x2,y2), the line, AB, that passes through points A and B is given by the equation,
(y-y1)(x2-x1) = (x-x1)(y2-y1)
The set of (x,y) that satisfies this equation is the line that passes through those two points. To show this is true, first notice that it is linear. That is, it has the form ay+b = cx+d, where a, b, c, and d are constants. Now notice that when x=x1 and y=y1, the equation is satisfied -- 0=0. Finally notice that when x=x2 and y=y2, the equation is also satisfied.
Now consider a function suggested by the equation of this line AB,
|Aside: The signed distance, dAB,
of a point (x,y) from the line determined by A(x1,y1)
and B(x2,y2) is found by dividing twice the signed
area by the base of the triangle:
(See Distance from line to point where the line is given as Ax+By+C=0)
fAB(x,y) = (y-y1)(x2-x1) - (x-x1)(y2-y1)
fAB(x,y) is zero for all points on the line, and non-zero for all other
points. In fact, if you're standing on B looking at A, then fAB(x,y) is
negative for all points (x,y) to your left, and fAB(x,y) is positive for all
points (x,y) to your right! This is a very interesting function. It
represents twice the "signed area" of the triangle (x,y),(x1,y1),(x2,y2)
and also the determinant of a
Here is a program written in REXX that implements this algorithm. Notice that it has only 7 lines -- much simpler than you might have thought...
|/* REXX */
parse upper arg x y x1 y1 x2 y2 x3 y3
if fAB()*fBC()>0 & fBC()*fCA()>0 then say "Inside"
else say "Not Inside"
fAB: return (y-y1)*(x2-x1) - (x-x1)*(y2-y1)
fCA: return (y-y3)*(x1-x3) - (x-x3)*(y1-y3)
fBC: return (y-y2)*(x3-x2) - (x-x2)*(y3-y2)
Triangle Area using Determinant
Distance from line to point - The distance from a line of the form Ax+By+C=0 to a point (h,k) is |Ah+Bk+C|/sqrt(A²+B²)
The webmaster and author of this Math Help site is Graeme McRae.