Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply




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







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.