Archived

This topic is now archived and is closed to further replies.

point in triangle

This topic is 5798 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites