Hi all Is there an easy way to determine if a point inside a triangle? It's 2D not 3D.
Best Regards,
A:
google search: http://mathforum.org/library/drmath/view/54505.html
Michael Bray
2010-01-12 14:26:57
+9
A:
Here's some high quality info in this topic on GameDev, including performance issues.
And here's some code to get you staret:
float sign(fPoint p1, fPoint p2, fPoint p3)
{
return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}
bool PointInTriangle(fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
bool b1, b2, b3;
b1 = sign(pt, v1, v2) < 0.0f;
b2 = sign(pt, v2, v3) < 0.0f;
b3 = sign(pt, v3, v1) < 0.0f;
return ((b1 == b2) && (b2 == b3));
}
In general, the simplest (and quite optimal) algorithm is checking on which side of the half-plane created by the edges the point is.
Kornel Kisielewicz
2010-01-12 14:27:02
That's a pretty inefficient way of solving this problem, see my answer for a better approach.
Andreas Brinck
2010-01-12 14:42:43
It's commonly used in 2D. Barycentric coordinates tend to confuse people. Also, given the cooridates of the triangle, and the point cordinate, I'm unsure about the efficiency of using barycentrics.
Kornel Kisielewicz
2010-01-12 14:51:22
@Kornel The barycentric version is more efficient in 2D as well. Your solution also has the problem that it will report a different result for points exactly on the edges of the triangle depending on wether the triangle is specified in clockwise or counter clockwise order.
Andreas Brinck
2010-01-12 15:09:44
+1
A:
A simple way is to:
find the vectors connecting the point to each of the triangle's three vertices and sum the angles between those vectors. If the sum of the angles is 2*pi then the point is inside the triangle.
Two good sites that explain alternatives are:
Simon P Stevens
2010-01-12 14:31:40
Um, that method isn't exactly efficient, and is very prone to numerical errors...
Kornel Kisielewicz
2010-01-12 14:35:03
It's quite the opposite, it's very inefficient :-) It's just one simple way though, that's easy to implement.Can you give an example of a numerical error this would cause?
Simon P Stevens
2010-01-12 14:38:40
+10
A:
Solve the following equation system:
p = p0 + (p1 - p0) * s + (p2 - p0) * t
The point p is inside the triangle if 0 <= s <= 1 and 0 <= t <= 1 and s + t <= 1.
s,t and 1 - s - t are called the barycentric coordinates of the point p.
Andreas Brinck
2010-01-12 14:41:40
This is faster than the half-plane check, but perhaps a little bit harder to grasp if you are new to barycentric coordinates.
DR
2010-01-12 14:51:53
@DR That's a little like saying you should use bubblesort instead of quicksort because recursion is hard to grasp ;)
Andreas Brinck
2010-01-12 15:04:42
Those are not exactly the barycentric coordinates, just 2 of them. The 3rd is of course 1-s-t, and if all 3 are >= 0 the point is inside.
phkahler
2010-01-12 18:50:18
With trivial exits (not implemented) in Kornel's method, his can actually far more efficient than yours. If you actually try to compute s and t you'll know what I mean.
Beh Tou Cheh
2010-01-16 22:14:22
@Ben You can implement trivial exits in this version as well, for instance you can begin by calculating only `s` and exit if it isn't in the `[0 1]` range. If the triangles can be both clockwise and counter clockwise you'll still have to calculate at least two signs in the halfplane version. Finally, how effective any trivial exits are depend on the input data.
Andreas Brinck
2010-01-17 08:49:06
A:
For my purposes (the reason I found this site) the original answer proposed by Kornel Kisielewicz is much more efficient. I'm working with an LCD display with BYTE size coordinates and a very typical microprocessor where integer multiply is a very fast instruction, and division is much, much, slower.
Numeric issues are also much smaller, due to no division! all calculations are exact.
Thanks,
Rick
Rick Sharpe
2010-01-16 04:57:47