[geos-devel] Intersection determination for overlay in GGL?
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?
Senior Technical Architect
Refractions Research, Inc.
More information about the geos-devel