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

Subject: [ggl] intersection of two vectors of polygons
From: Barend Gehrels (barend)
Date: 2011-05-02 17:51:59

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

Good question. If a quadtree index is being built, using partition would 
be very useful and I would certainly have brought this up. But building 
an r-tree is different and I don't know if it would add value. Maybe it 
would, Adam could probably say that.

The other reason that it is not (yet) reused is that it was extracted 
early this year, at about the time when Adam was already busy 
refactoring / rebuilding the r-tree index. I have mentioned partition 
once or twice on this list but had not yet documented, making it 
difficult to elaborate on it. So yes, partly a time issue, it was quite 
busy this spring with preparation for the release (and I also changed job).

Regards, Barend

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