
Geometry : 
Subject: [ggl] Re: pointinpolygon tests
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 20110331 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
> beforehand that it is convex, fewer edgeintersections need to be
> checked.
>
> Is there a way to test whether a polygon is convex in boostgeometry?
> 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
Geometry list run by mateusz at loskot.net