[geos-devel] Intersection determination for overlay in GGL?

[Martin Davis]

Barend Gehrels wrote:
>
> The GGL overlay algorithm will be described in a paper. It is a modern 
> variant of the classic Weiler-Atherton algorithm.
>
Barend, the references I've seen about Weiler-Atherton don't specify the 
approach taken to compute intersections.  In my experience this is the 
most time-consuming part of overlay computation. A simplistic 
implementation is O(n^2), but there are a variety of techniques which 
can be used to improve this.  Can you comment on the approach GGL uses 
for intersection determination?

Martin

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022