point in triangle
Author
Question: I'd like to know if a point is contained in a triangle (2D).
Thinking about this, it would seem I could do a dotproduct of each line segment to the point and checking the sign would work, but this seems expensive to do. There must be an easier way, its just late and im tired ) Could anyone help?
Edit: Hmm I should have thought about this - What if I took the distance of the point to each line segment in cyclical order as it wraps around the traingle - if the sign matches for each distance, would this not mean it was inside the triangle? (and if the distance is 0 it would be colinnear). Ill go test this, but feel free to input in the mean time :-)
Thanks,
Edited by - a_question on January 30, 2002 10:06:40 PM
There are a few ways to do this, but none are more efficient than a few dot products (as far as I know).
1 way is to find 3 angles
1) angle between P-P1 line and P-P2 line
2) angle between P-P2 line and P-P3 line
3) angle between P-P3 line and P-P1 line
(where P is your point, and P1, P2 and P3 are the points of the triangle)
If you picture this correctly, you''ll have 3 pie wedges that take up the whole triangle.
Add all 3 angles. If they don''t equal a complete circle (ie about 2*PI) then it''s outside the triangle.
1 way is to find 3 angles
1) angle between P-P1 line and P-P2 line
2) angle between P-P2 line and P-P3 line
3) angle between P-P3 line and P-P1 line
(where P is your point, and P1, P2 and P3 are the points of the triangle)
If you picture this correctly, you''ll have 3 pie wedges that take up the whole triangle.
Add all 3 angles. If they don''t equal a complete circle (ie about 2*PI) then it''s outside the triangle.
The usual method for checking if a point (x, y) is inside a polygon is to count the number of intersections between the line segment (-inf, y)..(x, y) and the polygon''s edges. The point is inside the polygon iff the number of intersections is odd.
There''s probably better ways of doing this for triangles, though.
There''s probably better ways of doing this for triangles, though.
another way is to find the edge normals ( ie cross product of the edge with the triangles face normal ). This should be done so the edge normals are all pointing out (or all in) from the centre of the triangle.
Then its just a set of dot products.
ie
triangle is p1,p2,p3, pn
edge = p1-p3
EdgeNorm = edge cross pn
p'' = p-p1
if( p'' dot EdgeNorm > 0 ) return(0)
edge = p2-p1
EdgeNorm = edge cross pn
p'' = p-p2
if( p'' dot EdgeNorm > 0 ) return(0)
edge = p3-p2
EdgeNorm = edge cross pn
p'' = p-p3
if( p'' dot EdgeNorm > 0 ) return(0)
else
return(1)
of course you can precalc and store off the edge normals.
It also allows you to figure what side the point lies outside of.
[The views stated herein do not necessarily represent the view of the company Eurocom ]
Eurocom Entertainment Software
www.Eurocom.co.uk
The Jackal
Then its just a set of dot products.
ie
triangle is p1,p2,p3, pn
edge = p1-p3
EdgeNorm = edge cross pn
p'' = p-p1
if( p'' dot EdgeNorm > 0 ) return(0)
edge = p2-p1
EdgeNorm = edge cross pn
p'' = p-p2
if( p'' dot EdgeNorm > 0 ) return(0)
edge = p3-p2
EdgeNorm = edge cross pn
p'' = p-p3
if( p'' dot EdgeNorm > 0 ) return(0)
else
return(1)
of course you can precalc and store off the edge normals.
It also allows you to figure what side the point lies outside of.
[The views stated herein do not necessarily represent the view of the company Eurocom ]
Eurocom Entertainment Software
www.Eurocom.co.uk
The Jackal
This example program uses a fast point in triangle test function:
http://nate.scuzzy.net/programming/dlight/dlight.zip
Look at the u3dPointInTriangle function.
http://nate.scuzzy.net/programming/dlight/dlight.zip
Look at the u3dPointInTriangle function.
Yet another method uses Barycentric coordinates. But I doubt if it is faster than the dotproducts or counting the number of intersections with a line. However, if you want to interpolate some quantities between the vertices (colors, texture coordinates, plausibility units, whatever), then the Barycentric coordinates thing can be very usefull.
Here''s how it works: say you have the vertices of the triangles stored as V1, V2, V3 in counter-clockwise order, and you have the point stored in P. You now calculate the Barycentric coordinates w1, w2, w3 so that:
w1 + w2 + w3 = 1
P = w1*V1 + w2*V2 + w3*V3
If any of w1, w2, w3 is smaller than 0 or larger than 1, then the point does not lie within the triangle. If one of them is 1 and the others are 0 then the point is exactly on a vertex. If one of them is 0 and the others are between 0 and 1 then the point lies on an edge. Otherwise the point is somewhere in the middle.
Now if you want to interpolate some quantity B of every vertex to find the value of B at the intersection point, you simply do:
BP = w1*B1 + w2*B2 + w3*B3
It''s that simple! This technique is used a lot in raytracers if I recall correctly.
If you''re interested I can mail you how to calculate w1,w2,w3 but I''m sure you''ll be able to find it with Google or a Gamedev forum-search.
Here''s how it works: say you have the vertices of the triangles stored as V1, V2, V3 in counter-clockwise order, and you have the point stored in P. You now calculate the Barycentric coordinates w1, w2, w3 so that:
w1 + w2 + w3 = 1
P = w1*V1 + w2*V2 + w3*V3
If any of w1, w2, w3 is smaller than 0 or larger than 1, then the point does not lie within the triangle. If one of them is 1 and the others are 0 then the point is exactly on a vertex. If one of them is 0 and the others are between 0 and 1 then the point lies on an edge. Otherwise the point is somewhere in the middle.
Now if you want to interpolate some quantity B of every vertex to find the value of B at the intersection point, you simply do:
BP = w1*B1 + w2*B2 + w3*B3
It''s that simple! This technique is used a lot in raytracers if I recall correctly.
If you''re interested I can mail you how to calculate w1,w2,w3 but I''m sure you''ll be able to find it with Google or a Gamedev forum-search.
Is stroring each lines equation in form of y = mx + b and then testing to see which side of the line the point is on, not fast or whatever, just wondering cause I havnt yet figured out how exactly to tell how fast an algo will be.
Tazzel3d ~ zach
Tazzel3d ~ zach
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
