
Geometry : 
Subject: [ggl] Point in triangle test available?
From: Mateusz Loskot (mateusz)
Date: 20101201 17:33:40
On 01/12/10 20:37, Simonson, Lucanus J wrote:
> Hartmut Kaiser wrote:
>>>> Does Boost.Geometry have a precanned '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 halfplane
algorithm is straightforward. However, I'm not sure how to bite the
selection of this strategy in compiletime 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 runtime 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
Geometry list run by mateusz at loskot.net