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

Subject: [ggl] Point in triangle test available?
From: Mateusz Loskot (mateusz)
Date: 2010-12-01 18:38:34

On 01/12/10 23:31, Simonson, Lucanus J wrote:
> 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...
Luke,

English is my 2nd language too.
Please, don't get me wrong, it wasn't my intention to correct you
but to confirm my own understanding. There could be some algorithm with
"plain" word in name. I'm not as vastly knowledgeable in computational
geometry as you are, so I needed confirmation.

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

It would require changes to the Boost.Geometry concepts.

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

Indeed, good point.

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

Understood. I will leave such design decisions to Barend as he is the
main conductor here.

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