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, 

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 certain matrix. 

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

On the next page, I'll show you the JavaScript program that does the same thing.

Related Pages in this website

Triangle Area using Determinant

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]