Geometry Boost List: [ggl] Re: point-in-polygon tests

Subject: [ggl] Re: point-in-polygon tests
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-03-31 13:58:07

Vishnu wrote:
> Thanks, Barend.
> 
> I think it would be good to have such an optimization in the future.
> If a polygon has a large number of vertices and it is known
> before-hand that it is convex, fewer edge-intersections need to be
> checked. 
> 
> Is there a way to test whether a polygon is convex in boost-geometry?
> This would be useful for other reasons also.
> 
> Vishnu

The larger the number of vertices, the less likely the polygon is convex.  Also, in the worst case you inspect every edge of the convex polygon and it is probably slower to do n/2 half plane tests than n interval overlap tests and 2 half plane tests for the edges of the polygon that contain the point in their x interval for evaluating the winding number of the point.

I believe there is a convex test.

A convex polygon concept that is a refinement of polygon would be a generally useful thing.  Rectangle concept would then be a refinement of convex polygon, as would triangle concept.  The problem is, adding a concept to the generic type system is a lot of work.

Regards,
Luke