What most efficient method to find a that triangle which contains the given point?
- by Christo
Given the triangle with vertices (a,b,c):
c
/ \
/ \
/ \
a - - - b
Which is then subdivided into four triangles by halving each of the edges:
c
/ \
/ \
ca / \ bc
/\ - - - /\
/ \ / \
/ \ / \
a- - - - ab - - - -b
Wich results in four triangles (a, ab, ca), (b, bc, ab), (c, ca, bc), (ab, bc, ca).
Now given a point p. How do I determine in which triangle p lies, given that p is within the outer triangle (a, b, c)?
Currently I intend to use ab as the origin. Check whether it is to the left of right of the line "ca - ab" using the perp of "ca - ab" and checking the sign against the dot product of "ab - a" and the perp vector and the vector "p - ab". If it is the same or the dot product is zero then it must be in (a, ab, ca)... Continue with this procedure with the other outer triangles (b, ba, ab) & (c, ca, ba). In the end if it didn't match with these it must be contained within the inner triangle (ab, bc, ca).
Is there a better way to do it?
