point-in-polygon tests

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

point-in-polygon tests

Vishnu
Point-in-polygon tests can be optimized if it is known that the polygon is convex. Does boost-geometry's point-in-poly function do any optimization using convexity?
Reply | Threaded
Open this post in threaded view
|

Re: point-in-polygon tests

Barend
Hi Vishnu,

On 31-3-2011 17:51, Vishnu wrote:
> Point-in-polygon tests can be optimized if it is known that the polygon is
> convex. Does boost-geometry's point-in-poly function do any optimization
> using convexity?

No. The reason is that we don't know before if it is convex (unless we
could create an additional property for it, might be possible in the
future), and the point-in-polygon is linear so another test to check if
a polygon is convex is not useful.

Regards, Barend

_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
Reply | Threaded
Open this post in threaded view
|

Re: point-in-polygon tests

Vishnu
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
Reply | Threaded
Open this post in threaded view
|

Re: point-in-polygon tests

Simonson, Lucanus J
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

_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
Reply | Threaded
Open this post in threaded view
|

Re: point-in-polygon tests

Barend
In reply to this post by Vishnu
Hi Vishnu,


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

No, not yet, but I agree it would be useful. Started once but it is as
an unfinished testfile only in an extension, so it will be there once.

Regards, Barend

_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl