-----------------------------------

Mazer

Sun Sep 19, 2004 7:45 am


Point in triangle algorithm

-----------------------------------

I've been reading up on collision detection, and most tutorials talk about how there are many algorithms for determining whether or not a point is on a triangle. But they all talk about one algorithm which involves getting angles and checking to see if their sum is ~2*Pi. They also tend to say that this algorithm, while simple, isn't the best.

Does anybody know which is the "best"? Or, of the algorithms you do know, which do you think is the best?


-----------------------------------

thegoose

Mon Sep 20, 2004 11:17 am



-----------------------------------

The solution I'm familar with involves the usage of vectors. Essentially, you cycle through the edges on every two pairs of lines from a point. Then using cross product to check if the point is between the two lines using the cross product. If it's verified for all 3 points, then the point is inside the triangle. The good thing about this method is that it does not create any float-point errors which happens if you check for angles.


-----------------------------------

Mazer

Mon Sep 20, 2004 12:48 pm



-----------------------------------

Could you possibly explain that differently?
the edges on every two pairs of lines from a point.This line in particular, please.


-----------------------------------

bugzpodder

Mon Sep 20, 2004 2:55 pm



-----------------------------------

An easier way than what Richie mentioned is to the following:

if a point P is inside triangle ABC, then 

Area PAB+Area PBC +Area PAC=Area ABC

notice that if P is on the edge of AB, BC, or CA, the above hold.  But effectively, one of the area PAB, PBC, PAC is 0 (so just make sure you check that).

if P is outside, the above equality does NOT hold...

How to determine area?  you have two options:
1) Heron's theorem, involves sqrt, slower
2) the more perferred way is the cross products (or effectively, the half of absolute value of (sum of the down products minus the sum of up products))

for example, if A=(x1,y1) B=(x2,y2), C=(x3,y3)
Area= abs(x1*y2+x2*y3+x3*y1-x1*y3-x3*y2-x2*y1)/2

also you might want to be careful about floating point errors... instead of checking for strict inequality, check for abs(b-a)