Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: How to determine if a point is within a triangle or not.
Replies: 11   Last Post: Jul 12, 1996 7:20 AM

 Messages: [ Previous | Next ]
 Ted Alper Posts: 51 Registered: 12/6/04
Re: How to determine if a point is within a triangle or not.
Posted: Jul 10, 1996 6:42 AM

In article <4rumuc\$q8e@mn5.swip.net>, jwrdv93@tufvan.hv.se says...
>
>A problem me and my friend encountered while implementing a 3D-modelling-
>editor is how to determine if a point p is inside or outside a triangle
>(in two dimensions).

[method of jwrdv93 omitted]
>>Anyone has a better formula for this ?

I'm sure some CS-y person can give you some standard algorithms, but
just off the top of my head here are two ways:

Problem: points P and A,B,C to determine if P in triangle formed by ABC

Method I:
(1) subtract vect. A from P,B, and C (i.e. translate to case where A=(0,0))
that is replace P by P-A, B by B-A, C by C-A.

(2) For P,B,C modified as in (1):
take linear transformation that takes B to (1,0) and C to (0,1)
that's just the inverse of matrix: [row1: b1 c1 and row2: b2 c2]
i.e. the matrix: 1/(b1c2 - b2c1) * [row1: c2 -c1 and row2 -b2 b1]
apply this to P to get the vector:
(x,y) = 1/(b1c2 - b2c1) * (p1c2 - p2c1 , -p1b2+ p2b1)
This will be in interior exactly when x and y are both positive and x+y < 1

Method II:
(1) determine whether P is on the same side of line AB as C is:
that is, let m = (b2 - a2)/(b1-a1) [for b1 neq a1]
and be sure c2 - mc1 and p2 - mp1 have the same sign.
(if b1=a1, then instead check that c1 - a1 and p1 - a1 have same sign)
(2 and 3): repeat this idea for lines BC, point A and line AC, point B.

Ted Alper
alper@epgy.stanford.edu

Date Subject Author
7/9/96 Jonas WranÃÂ¥
7/9/96 Jonas WranÃÂ¥
7/10/96 Ted Alper
7/10/96 Hauke Reddmann
7/10/96 Dave Lantz
7/10/96 Dave Rusin
7/10/96 Jim Ward
7/10/96 Kevin Brown
7/10/96 Jeff Erickson
7/11/96 Frank R Bernhart
7/11/96 Christian Ehrhardt
7/12/96 Gordon Cooper