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

Subject: [ggl] intersection of two vectors of polygons
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-05-01 22:41:49

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

Consider me misinformed until corrected.  Divide and conquer is a reasonable way to approach map overlay.

>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.
Speaking of spatial index, if you have the recursive spatial division algorithm already implemented as the partition algorithm (now the name makes sense to me) then why not use that algorithm to write out the data structure for the spatial index project.  We want to seperate the algorithms for spatial index from the data structures, and here we have an algorithm.  Perhaps I wasn't paying close enough attention and this has already been discussed, but recent posts about spatial index construction being changed indicate that the implementation of tree construction is not re-using your partition algorithm.  If we can have a boost graph like abstraction here then improved or alternate partition algorithms can be implemented for spatial index and applied to partiion, making it easier to reuse code across the library.

Thanks,
Luke
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20110501/88c95a76/attachment.html