Boost logo

Geometry :

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

Geometry list run by mateusz at