Geometry Boost List: [ggl] Re: intersection of two vectors of polygons

Subject: [ggl] Re: intersection of two vectors of polygons
From: Barend Gehrels (barend)
Date: 2011-07-04 16:52:31

Hi Vishnu,

I have looked to your mail but not all is clear to me.

On 29-6-2011 7:01, Vishnu wrote:
> Hi Barend,
>
> I've used both the O(n log(n)) and the O(n^2) methods you described in this
> post and am looking for ways to speed up the O(n log(n)) implementation. My
> observations on times are based on using the following.
>
> 1) 100x100 grid of polygons intersected with a 10x10 grid of polygons
> 2) 1000x1000 grid of polygons intersected with a 10x10 grid of polygons

I have't done testcases yet with this distribution. The 10x10 will 
overlap with many of all other polygons, especially because that is the 
one rotated.

> All of the polygons above are squares. In each of the two cases above, the
> first vector of polygons has edges parallel to the x and y axes and the
> second vector of polygons is rotated about the center of the first set of
> polygons so that the edges of its polygons are at 45 degree angles to the x
> and y axes.
>
> I find that the O(n.log(n)) method is about 2.4 times faster than the O(n^2)
> method and would like to achieve a better speed improvement relative to the
> O(n^2) method. I wonder if I'm not setting something quite right in order to
> make better use of  the partitioning.
>
> Stepping through your sample with 9 squares in each vector,  I see that when
> has_overlap::apply() is called, there are only two values that the box has
> on input to this function:
>
> {0,0} to {0.625,1.25}, and
> {0.625,0} to {1.25, 1.25}
>
> Can one specify the number and size of partitions that contain the polygons?

Yes, the "min_elements" can be set as a runtime parameter, it defaults 
to 16. If there are more than that left (in a set), it will partition. 
If there are less, it will handle that quadraticly.

I can repeat what you did, but (if possible and convenient) you might 
mail the code such that I can have a closer look.

Regards, Barend