
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 3Dmodelling >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 CSy 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 PA, B by BA, C by CA.
(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)/(b1a1) [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

