[geos-devel] [Fwd: [Boost-users] [boost] Formal Review: Boost.Polygon starts today August 24, 2009]

[Martin Davis]

> 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