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-06-30 02:16:54

Hi Vishnu,

Will look at this this weekend.

Regards, Barend

Sent from iPad.
Barend Gehrels
www.barendgehrels.nl

Op 29 jun. 2011 om 07:01 heeft Vishnu <vrang3_at_[hidden]> het volgende geschreven:

> 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.
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
> http://lists.osgeo.org/mailman/listinfo/ggl