Test for Point Inside Triangle

Date: Fri, 4 Nov 1994 16:08:30 +0000 (TST)
From: Boonchai Techaumnat
Subject: Geometry Problem

I have one geometry problem and want a simple solution that can be
solved by computer program -- numerically -- with good resolution.

The Problem: How can I know whether a point P(x,y) is in a triangle
with vertices P1(x1,y1), P2(x2,y2), and P3(x3,y3)?

Thanks for any help
Boonchai T.

Date: Fri, 4 Nov 1994 08:24:14 +0900
X-Sender: mpatter1@cc.swarthmore.edu

Hi Boonchai!

Thanks for writing to us. This is a good question.  It sounds like a
fun project. What language are you planning to write the program in?

Here are some tips to get started:

1) Using the coordinates of the points, compute the equations of the
lines containing the sides of the triangle.

2) Draw a triangle and label each side, l1, l2, and l3. (The l stands
for line.) If a point is in the interior of the triangle, what has to
be true about its relationship to the three lines? (Hint: think less
than or greater than)

3) More specifically, think of the lines in terms of three pairs. Given
any pair, what is the relationship between the point and the two lines
of the pair?

4) Now, when you have some ideas, check to make sure that a point that
is exterior to the triangle does not pass your tests for interior
points.

I hope this helps. I (and the other math doctors too) would love to
hear about the solution you come up with.  Please write back if you
have questions about this response or some other topic.  

-Margaret, Math Doctor on call

Date: Sun, 6 Nov 1994 14:19:12 +0000 (TST)
From: Boonchai Techaumnat

No, it's not fun, but my serious project. I will use C++ to solve this
problem.

From (3) I thought that if a point is in the triangle, it must be in
the angle range of all 3 pairs. This gives me a solution for my
problem! Thanks a lot, but I don't get anything from (2). Can you make
it clearer? It may point to an alternate solution.

Thanks,
Boonchai T.

Date: Mon, 7 Nov 1994 01:04:27 +0900
X-Sender: mpatter1@cc.swarthmore.edu

Hi again.

I am glad that you have a solution. The solution that I had in mind
when I wrote tip #2 was to find the equations for each line and then
compare the point P to those lines. I had thought that for each pair
the point must be less than one of the lines and greater than the
other, but now that I draw it out on my scratch paper, I don't think
that it would always be true (like in the case of an obtuse triangle).
So, your idea sounds good.

-Margaret

Date: Mon, 10 Mar 1997
From: 
Subject: Solution to an old problem

Hello Doctors!

Here is an alternate solution to this problem:

How can I know whether a point P(x,y) is in a triangle with vertices
P1(x1,y1), P2(x2,y2), and P3(x3,y3)?

There are two possibilities:

     1. P is INSIDE or ON,
     2. P is OUTSIDE triangle P1P2P3.

If you draw a sketch and consider triangles,

     PP1P2, PP2P3, PP3P1

You will notice the following relationship in their areas.

If P is ON or INSIDE,

     A(PP1P2) + A(PP2P3) + A(PP3P1) = A(P1P2P3)

If P is OUTSIDE then,

     A(PP1P2) + A(PP2P3) + A(PP3P1) > A(P1P2P3)

Area of a triangle can be found using the determinant:

     A = abs(1/2 * |x1  y1  1| )
                   |x2  y2  1|
                   |x3  y3  1|

You can write a function in C++ that accepts the three points
(as Classes) or their coordinates and returns the area.

Finally if you have to distinguish between ON and INSIDE, put the point
in the equations of the three lines that form the sides. If one of them
is satisfied, P is ON a side. If two are satisfied, P is a vertex of
the triangle.

- Ujjwal Rane