# Geometry :

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

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:

>
> 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]

Geometry list run by mateusz at loskot.net