
Geometry : 
Subject: [ggl] Re: intersection of two vectors of polygons
From: Barend Gehrels (barend)
Date: 20110630 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 << "nlogn 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://boostgeometry.203548.n3.nabble.com/intersectionoftwovectorsofpolygonstp2875513p3120379.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
Geometry list run by mateusz at loskot.net