In article <email@example.com>, firstname.lastname@example.org 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.