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

Subject: [ggl] Re: intersection of two vectors of polygons
From: Vishnu (vrang3)
Date: 2011-06-29 23:55:37

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

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?
I am using the call exactly as you showed in this post: 
http://codepad.org/MBRPDhwj

    std::cout << "n-log-n solution" << std::endl;
    intersection_visitor visitor;
    boost::geometry::partition
        <
            boost::geometry::model::box<point_type>, do_expand, has_overlap
        >::apply(owners, mineral_rights, visitor, 1);

--
View this message in context: http://boost-geometry.203548.n3.nabble.com/intersection-of-two-vectors-of-polygons-tp2875513p3120379.html
Sent from the Boost Geometry mailing list archive at Nabble.com.