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 18:31:17

Mateusz Loskot wrote:
>> It should be implemented as three half plain tests
> 
> You likely mean half plane...

English is my 2nd language since C++ has become my first...
 
> 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

Triangle concept can be added as a refinement of polygon concept that imposes the restriction that the polygon have three vertices.  Recall that refinement narrows the definition of a concept.  Optimized triangle specific algorithms can then be selected at compile time based on concept type.  A object that models triangle concept should be acceptable as an input type for any algorithm expecting polygon, but not acceptable as an output type for any algorithm expecting to output a polygon.  An example of this is axis-parallel rectangle is a refinement of axis-parallel polygon in my concept hierarhcy.  Any algorithm expecting triangles for output should accept polygon types.  A polygon type that is known (either statically or at runtime) to have three points could be viewed as a model of triangle with a concept cast.  Getting this right would probably require invasive changes in the library to extend it to support a triangle concept as a refinement of convex polygon.

Regards,
Luke