Geometry Boost List: [ggl] intersections and unions

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

Hi,

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

- 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 
polygons).
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 
come.

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

http://www.xs4all.nl/~barend/geodan/overlays/traverse_union_4.svg
http://www.xs4all.nl/~barend/geodan/overlays/traverse_union_5.svg
http://www.xs4all.nl/~barend/geodan/overlays/traverse_intersection_4.svg
http://www.xs4all.nl/~barend/geodan/overlays/traverse_intersection_5.svg

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20090620/090f9fcb/attachment-0001.html