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

[Barend Gehrels]

Hi Martin,


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

Sorry, I've to keep this short. We're busy with that robustness and 
there is indeed at least one issue. I'll come back to this (in a few weeks).

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

Regards, Barend