Point Inside or Outside Triangle?

Date: 08/02/2001 at 03:52:00
From: Natalie
Subject: Is the point inside of triangle

I have a problem how to find out if a point is inside or outside of 
a triangle.

I have coordinates of three vertices of a triangle and coordinates of 
the point that I have to check. Let's say:

   point A(200,300)
   point B(300,500)
   point C(100,500)
   and the point for checking is D(200,350)

How can I know if D is inside the triangle or not?

                  A
                 / \
                /   \
               /  D  \
              /_______\
             C         B

Date: 08/02/2001 at 17:00:01
From: Doctor Rick
Subject: Re: Is the point inside of triangle

Hi, Natalie.

I went to our Search Dr. Math page,

  http://mathforum.org/mathgrepform.html   

and searched for the words  point inside triangle . You can do this 
too. I found a lot of irrelevant pages, but I also found these:

  Point inside a Triangle
  http://mathforum.org/dr.math/problems/bob.07.15.01.html   

  Point Inside Triangle
  http://mathforum.org/dr.math/problems/point.inside.triangle.html   

  Formula for Point in Rectangle
  http://mathforum.org/dr.math/problems/scott5.31.96.html   

I'll give you an idea of my own, which you may find helpful if you are 
familiar with vectors. (If not, you could just take my word that the 
formula below works. Of course, you'll test it to be sure I didn't 
type something wrong, and let me know if I did.)

I will assume, for the moment, that the points A, B, and C are in 
clockwise order around the triangle. If you look along AB from A 
toward B, all points inside the triangle are on your right. Likewise 
as you look along BC from B toward C, all interior points are on your 
right; and the same for CA.

One way to calculate which side of the line a point is on is to take 
the vector product or cross-product of two vectors. In particular, 
construct the vectors B-A and D-A. I'll do this in three dimensions.

  B-A = (x_b-x_a, y_b-y_a, 0)
  D-A = (x_d-x_a, y_d-y_a, 0)

The cross-product of vectors (x_1, y_1, x_1) and (x_2, y_2, y_2) is

  (y_1*z_2-z_1*y_2, z_1*x_2-x_1*z_2, x_1*y_2-y_1*x_2)

The cross product of two vectors is perpendicular to both vectors. Its 
direction follows the right-hand rule: if the second vector is to the 
left of the first (looking from above), then the cross product points 
up. 

Let's take the cross product (D-A)x(B-A). The x and y components are 
zero; the vector points either up (z component is positive) or down 
(z component is negative) depending on whether B-A is to the left or 
right of D-A. Thus the sign of the z component of the cross product 
tells us what we need:

  z_ab = (x_d-x_a)*(y_b-y_a)-(y_d-y_a)*(x_b-x_a)

If z_ab > 0 then D is on the "inside" side of AB. If you do the same 
replacing AB with CB and then CA, and each time z is negative, then D 
is inside the triangle.

What if you don't know whether the vertices of the triangle are in 
clockwise or counterclockwise order? Just change the condition: a 
point D is inside the triangle if EITHER all of z_ab, z_bc, and z_ca 
are positive, OR they are all negative. If the points are in clockwise 
order, as I assumed above, then there is no (exterior) point such that 
all the z's are negative, so we won't get spurious results due to the 
broader condition.

The area method mentioned in two of the archived answers is 
essentially the same approach as mine, if you consider the derivation 
of the determinant formula for area used there. 

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/