point inside a triangle.....
Author
anyone knows how to test whether a point say P(x,y) is inside a triangle or outside the triangle.
Let''s suppose we have a triangle with three vertices (a(x,y),b(x,y),c(x,y)) and now we gotta test whether any point
like p(x,y) is inside the triangle or not. plzzzzzz helppppp............
http://www.peroxide.dk/tutorials/tut10/pxdtut10.html
had exactly what i was looking for halfway down, and it should help you. basically, if all the angles add up to 360, you are in the triangle. if not, you are outside of it. hope it helps.
had exactly what i was looking for halfway down, and it should help you. basically, if all the angles add up to 360, you are in the triangle. if not, you are outside of it. hope it helps.
Another resource:
http://www.acm.org/pubs/tog/editors/erich/ptinpoly/
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
http://www.acm.org/pubs/tog/editors/erich/ptinpoly/
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
I recently asked the Algorithm list this,
The answer is basicaly this,
Starting at the first point we work around the triangle in a clockwise order calculating if the point is above or below the line.
Because we go in a clockwise order, if the point is above all of the lines that make up the triangle it is inside the triangle!!
The formula for if the point is above or below the line is as follows
result = xa*yb + xc*ya + xb*yc - xc*yb - xa*yc -xb*ya
where x and y relate to coords!!
a = start of the line, b = end of the line
c = point we are testing!!
if result = 0 the point is on the line
if result < 0 point is below the line
if result > 0 point is above the line
So simplified, work round your triangle with this formula if any results a less than zero, point is outside the triangle!!
Paul.
Edited by - Spider_In_A_Web on October 30, 2001 11:29:05 AM
The answer is basicaly this,
Starting at the first point we work around the triangle in a clockwise order calculating if the point is above or below the line.
Because we go in a clockwise order, if the point is above all of the lines that make up the triangle it is inside the triangle!!
The formula for if the point is above or below the line is as follows
result = xa*yb + xc*ya + xb*yc - xc*yb - xa*yc -xb*ya
where x and y relate to coords!!
a = start of the line, b = end of the line
c = point we are testing!!
if result = 0 the point is on the line
if result < 0 point is below the line
if result > 0 point is above the line
So simplified, work round your triangle with this formula if any results a less than zero, point is outside the triangle!!
Paul.
Edited by - Spider_In_A_Web on October 30, 2001 11:29:05 AM
hmmmmmmm i stared at this for a while but my eyes went cross. is there a nice way to turn this into a three dimensional equation?
A triangle is a 2-dimensional surface. It might exist in 3-dimensional space, but all points within the triangle can be represented parametrically by the 2-dimensional plane equation for the triangle. There really is no 3-dimensional point-in-triangle test. The trick is to transform the triangle vertices and point-of-interest into an appropriate 2-dimensional space, then do the 2-d point-in-triangle test.
If you are interested in finding out if a point in screen space is within the triangle in screen space then you only have to project the triangle into screen space, which is 2-d, and do the point-in-triangle test in screen space. If you''re interested in a truly arbitrary 3-d point, then you first have to make sure the point is in the plane of the triangle. If it is not, the point is not in the triangle. If the point is in the plane of the triangle, then project the triangle and point into a common 2-d space (preferably a 2-d space that lies within the plane of the triangle----the most reliable way) and do the 2-d point-in-triangle test in the projection space.
That may confuse things, but the bottom line is that it always boils down to a 2-dimensional test. See the link I gave previously for some more description "3D to 2D". The web source is a draft of a chapter that ultimately appeared in "Graphics Gems IV." The author is Eric Haines of "Real-Time Rendering" fame. Eric even provides source code.
The 360 angle summation test is apparently slower than the crossings test. To quote my source, "it will still always be faster to use any other algorithm in this Gem."
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
If you are interested in finding out if a point in screen space is within the triangle in screen space then you only have to project the triangle into screen space, which is 2-d, and do the point-in-triangle test in screen space. If you''re interested in a truly arbitrary 3-d point, then you first have to make sure the point is in the plane of the triangle. If it is not, the point is not in the triangle. If the point is in the plane of the triangle, then project the triangle and point into a common 2-d space (preferably a 2-d space that lies within the plane of the triangle----the most reliable way) and do the 2-d point-in-triangle test in the projection space.
That may confuse things, but the bottom line is that it always boils down to a 2-dimensional test. See the link I gave previously for some more description "3D to 2D". The web source is a draft of a chapter that ultimately appeared in "Graphics Gems IV." The author is Eric Haines of "Real-Time Rendering" fame. Eric even provides source code.
The 360 angle summation test is apparently slower than the crossings test. To quote my source, "it will still always be faster to use any other algorithm in this Gem."
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
