Geometry Boost List: [ggl] Point in triangle test available?

Subject: [ggl] Point in triangle test available?
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2010-12-01 15:38:54

Hartmut Kaiser wrote:
>>> Does Boost.Geometry have a pre-canned 'point in triangle' test
>>> available? I could come up with one myself easily, but asking might
>>> allow me to stay lazy :-P
>> 
>> There is point in polygon, of course.  I'm not sure of the syntax
>> required, however.
> 
> I understand that, but point in triangle is usually simpler (I don't
> need to sort my points for that), and additionally faster (as I could
> use the barycentric coordinate).

It should be implemented as three half plain tests which can bee SSE accelerated and use barycentric coordinates in a very straightforward manner.  If you want that specifically you'll need to use something like NT2.  I'm not sure why there would be value in a half measure efficient point in triangle test that isn't SSE accelerated.  You have to ask youself if performance matters and how much.  

My understanding is that Boost.Geometry uses the area type point in polygon test where if the area comes out positive the point is inside the polygon of conventional winding direction.  It should be linear and not require sorting, per se, though you may need to reverse your winding direction, which is comparable to sorting for n = 3.  I'm not sure how they handle the case where the point is on the boundary.  The area test is pretty poor in terms of robustness because accumulated numerical error summing trapezoidal areas of cross products over n polygon verticies creates a pretty wide error band around the boundary.  We see this problem frequently in non-robust point in polygon tests.  If you recall from boostcon the polyboolean library's point in polygon test was not robust, which was a fatal error.

My own point in polygon algorithm discards edges that have an x interval that doesn't overlap with the x coordinate of the point and then performs half plain tests on the remaining edges looking for odd number of edges the point is above or below.  It doesn't support floating point, however, because it uses the robust half plain test that I use for the booleans.  It accepts a flag for whether to consider the point on boundary in or out, which becomes important for dealing with holes.

Regards,
Luke