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

Subject: [ggl] intersection of two vectors of polygons
From: Barend Gehrels (barend)
Date: 2011-04-30 12:46:08

Hi Luke,

> I did not know of the existence of the partition algorithm in ggl.  
> Can you comment on how it works?  The functor based interface looks 
> interesting.

Will elaborate on it in a blog. It is n-log-n (typical case) or still 
n^2 (worst case, e.g. all boxes same size/position).  It is not an 
extension from intersection, it can relate anything. See it as a 
quad-tree on the fly, the visitor does the work, nothing is stored (so 
not a real quad-tree). It's a complete rework of a divide-and-conquer 
spatial division which you mentioned before or during review. It divides 
alternating in two dimensions (theoretically more dimensions are 
supported), comparable to quadtree or octree.

It did exist before (in get_turns, and separately (but commented) in 
assemble). I merged the two implementations while refactoring the 
assembly phase, early this year, enhanced it, and made a separate and 
indepedant function of it.

>
> I can unsubscribe if you prefer.

No, please don't, you joined for spatial index (IIRC) and your input is 
valuable, plus of course good to be informed.

Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20110430/85f1945c/attachment.html