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

Subject: [ggl] Point in triangle test available?
From: Mateusz Loskot (mateusz)
Date: 2010-12-01 17:33:40

On 01/12/10 20:37, Simonson, Lucanus J wrote:
> 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

You likely mean half plane...

> which can bee SSE accelerated and use barycentric coordinates in a
> very straightforward manner.

Tomas M?ller's ray/triangle intersection algorithm is based on
barycentric coordinates. Perhaps this could be a basis for point in
triangle variation in such case.

> 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.

Yes.

> I'm not sure how they handle the case where the point is on the
> boundary.

AFAIR, there are two strategies implemented for point in polygon:
one based on counting crossings and another is Franklin's algorithm
Both don't really work well with point on boundary case.

Regarding point in triangle, the implementation of the half-plane
algorithm is straightforward. However, I'm not sure how to bite the
selection of this strategy in compile-time as we don't have a dedicated
type for triangles.

There are two solutions I think:
- user knows his polygon is a triangle and explicitly selects optimised
strategy
- optimised strategy is selected automatically based on run-time check
of number of vertices in a polygon

Best regards,
-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org
Member of ACCU, http://accu.org