[geos-devel] [Fwd: [Boost-users] [boost] Formal Review: Boost.Polygon
starts today August 24, 2009]
Martin Davis
mbdavis at refractions.net
Wed Sep 2 12:00:53 EDT 2009
> The GGL overlay algorithm will be described in a paper. It is a modern
> variant of the classic Weiler-Atherton algorithm.
Have you done anything to make the algorithm robust? My impression of
this algorithm is that it might be more complex to make robust (although
perhaps you can handle that in the intersection determination).
>
>> The JTS/GEOS predicate and overlay algorithms were developed with the
>> primary goal being first generality and then performance. So no
>> doubt there's better ways of doing things.
> Actually the GGL algorithm is generic as well, in the sense that it is
> able to overlay polygons and polygon/rectangle (clipping) with the
> same algorithm. The only difference is getting the intersections,
> which is more efficient for the rectangle case. Also
> intersection/union are implemented in one algorithm.
The JTS/GEOS generality extends to handling all combinations of
polygons, lines and points.
As you say, rectangles are special cases of polygons which allow faster
intersection detection, and which don't have any self-intersections, so
don't need an initial topology building step. JTS/GEOS has some
optimized code for rectangle handling, but there's still opportunity for
further optimization.
>
>> In the GEOS algorithms at least I don't see any way of avoiding
>> dynamic allocation, since there's no way to predict a priori how many
>> line segment intersections will be found, or how what the structure
>> of the output geometry is. Does GGL avoid this problem in some way?
> Yes. It will be described, but in short: we don't insert the found
> intersection points into the polygons (as done in many algorithms, but
> I don't know about GEOS) but register them separately. That saves a
> copy, plus many inserts (shifts). However, it requires somewhat more
> bookkeeping. So intersected polygons are assembled in the end, in
> between there are no large pieces of memory allocation.
JTS/GEOS uses the same approach. As you say, it's more efficient to
collect the intersection points first and then create the split edges.
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
More information about the geos-devel
mailing list