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

Martin Davis mbdavis at refractions.net
Wed Sep 2 14:25:49 EDT 2009

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 Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

More information about the geos-devel mailing list