Geometry Boost List: [ggl] optimization of polygon intersection and difference calculations

Subject: [ggl] optimization of polygon intersection and difference calculations
From: Barend Gehrels (barend)
Date: 2011-03-31 04:52:10

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