# Geometry :

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