PDA

View Full Version : point lies...



ricfow
02-08-2004, 03:35 PM
Hi,
I have a triangle defined by the vertices,
V1{x1,y1,z1)
V2{x2,y2,z2)
V3{x3,y3,z3)
now i need to know if a point P(x4,y4,z4)
lies inside the triangle,
(i'm sure that this point is on triangle's
plan.)
how can i do this?

thanks,

madmortigan
02-09-2004, 12:55 AM
Hi

A general method that will work with any polygon is to cast (fire) a ray from the test point to any direction (in principal) on your plane. By ray, I mean a half-infinite line, starting at a point and direction away from that point. Then count the number of intersections you get with the triangle. if it is 1, then the point is inside, if 2, its outside.

You have to expect some tricky cases, sooner or later, for example, your ray may actually hit a vertex. For your triangle, a way around that is to cast the ray form the test point to say, the midpoint of one of the edges.

mad

Mega
02-09-2004, 11:23 PM
Assume that you have three line equations for segments V1V2, V2V3, V3V1, in form of Ax+By+Cz+D=0. If you substitute coordinates of point P in left-hand sides of those equations, you will get a nonzero results. If all those results are of the same sign, then the point P lies inside, if at least one result is another sign, P lies outside. But, for this to be correct, the order of V1, V2, V3 must be clockwise (or counterclockwise) for all triangles.