Boost logo

Geometry :

Subject: [ggl] intersections and unions
From: Barend Gehrels (Barend.Gehrels)
Date: 2009-06-20 04:33:32


Everything is checked in again (namespace "impl" renamed to "detail",
one of the last renamings I hope, it should not influence normal use of
the library).

Herewith some news about intersections and unions

Regards, Barend

*Intersections and unions:
*- preview 1 had clipping (clipping polygons by a box)
- this is now replaced by a more generic algorithm which can do clips,
intersections and unions
- about 90% is done. What still has to be done is handling the holes
which do NOT intersect (so they should be new holes), and more of these
- the algorithm is for 95% the same for intersections and unions. The
difference is the way of traveling, left or right, but that is a
parameter. Also the assembling of holes / multi parts is different

- the algorithm can basically handle two geometries, but is also be able
to handle one geometry (so remove self intersections, e.g. after a
buffer) or more than two geometries

- the "union" has a weird name because it is a reserved word. Other
libraries (SQL) do have the same and offer alternatives. We can have:
a) union_ (as in MPL)
b) st_union (as in SQL) but I reject this, it would require renaming all
algorithms for consistency and the st_ prefix is by us the ggl:: prefix
c) gunion (as in SpatialLite), in Italian (SL is built by italians) this
is probably pronounced the same, and "g" probably stands for
d) join (cannot remember but some library uses this) sounds good to me
e) unite, so take the verb instead of the noun
f) Union with a capital

I would go for d)

- resulting rings/polygons are currently outputed to an output iterator.
This was requested last year by the boost list. However, I've
performance problems with it. Assembling polygons from rings take two
extra copies. While I avoid making copies in the complete rest of the
process... Chris also had some remark about this.

So I propose to add an overload, or replace the output iterator, with a
templated collection of rings / polygons. This ALSO avoids the need for
specifying the output-type. And it automatically enables the output to a
multi-polygon (because that is nothing else than a vector or deque of
This gives about 5-10% performance increase.

- speaking about performance, the performance is good. I've compared it
with other libraries and GGL is faster. More information about this will

- ~80% of the process is spent on finding intersections. Without
monotonic sections it would be much longer. But it can probably be
enhanced with spatial indexing instead
- as this is investigated / decided it will also be possible to generate
those (sections/indexes) before, they can be reused or might even be
stored in a database or so. We've then to add it the the concept / make
a traits for it
- the performance of the version with Boxes (clipping) can be enhanced
because collecting segment intersections can be more efficient for
box/rings (without indexes of sections). This was done in the old
version (Jan 2008) so can be adapted here again.

Some examples (using SVG, which is also new):

-------------- next part --------------
An HTML attachment was scrubbed...

Geometry list run by mateusz at