Geometry Boost List: [ggl] intersections and unions

Subject: [ggl] intersections and unions
From: Hartmut Kaiser (hartmut.kaiser)
Date: 2009-06-20 09:58:51

> - 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
> geometry/geography
> 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)

I know naming issues tend to become bicycle shed discussions, and
additionally, my vote is probably the least significant here. Nevertheless,
I'd go for a), because

- all Boost libraries I know of dealing with this type of name clash resolve
it by appending an underscore to the reserved name (MPL, Fusion, Phoenix,
Proto, Spirit, to name a few)
- a geometry union is - well - a union, and not a join

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

Sounds like a solid argument against output iterators.

> 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
> polygons).
> This gives about 5-10% performance increase.

Cool.

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

What about geometric stability? This is alwys my main concern when it comes
to geometric algorithms. Speed is fine and necessary, but only as long as
they converge :-P

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

A simple sorting along the outer edge of one of the polygons already helps a
lot (using one dimensional indexing). But you're probably doing that
already.

Regards Hartmut