optimization of polygon intersection and difference calculations

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

optimization of polygon intersection and difference calculations

Vishnu
Are the functions that calculate intersection and difference of two multi_polygons optimized to rule out testing polygons in the 'subject' set against those polygons in the 'clip' set that don't overlap with the subject? Suppose one has a multi_polygon with one polygon in a 'subject' set and a second multi_polygon with 1000 polygons in the 'clip' set. It's possible that only one of the 1000 polygons in the 'clip' set overlaps the polygon in the 'subject' set.
Reply | Threaded
Open this post in threaded view
|

Re: optimization of polygon intersection and difference calculations

Barend
Hi Vishnu,



On 30-3-2011 20:16, Vishnu wrote:
> Are the functions that calculate intersection and difference of two
> multi_polygons optimized to rule out testing polygons in the 'subject' set
> against those polygons in the 'clip' set that don't overlap with the
> subject?

Yes. They are overlayed by monotonic sections, and those sections are
handled by partitioning (quad-tree like approach without a stored index).


> Suppose one has a multi_polygon with one polygon in a 'subject' set
> and a second multi_polygon with 1000 polygons in the 'clip' set. It's
> possible that only one of the 1000 polygons in the 'clip' set overlaps the
> polygon in the 'subject' set.

Yes. Do you experience problems with this? If so, can you send me a
test-set? (2 wkt's)

The only optimiziation which still can be done is the assignment of
non-overlapping rings after intersecting. It might be that that is an
issue here. Will be solved later on, the problem is assigned.

Regards, Barend

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

Re: optimization of polygon intersection and difference calculations

Vishnu
I was just asking (I'm not reporting a problem).

Vishnu