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

Martin Davis mbdavis at refractions.net
Tue Sep 22 12:26:42 EDT 2009

```Sounds like you've got all the right ideas, Barend.  Good luck with the
optimizations...

Martin

Barend Gehrels wrote:
> Hi Martin,
>
> I was on holiday, therefore my delay in answering your question.
>
>
> Martin Davis wrote:
>> 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.
> That is true. I made some measurements in July: in "normal" cases 84%
> of the time is spent on finding intersections (using GGL). In cases
> where there are much more intersections (the star-ellipse), still 54%
> is spent on intersections. So yes, the intersection detection is the
> most important phase for performance.
>
>> 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?
> We currently use *monotonic sections* to speed this phase up. It is
> then not O(n^2). You've written about monotonic sections in your
> weblog. These monotonic sections are created on the fly. So the
> intersection finding could be faster by having prepared monotonic
> sections. However, determining the monotonic sections is not heavy,
> one loop per polygon.
>
> Another option, which is investigated, would be to use a spatial index
> for this. We already have a spatial index, but currently it does not
> speed the process up, it is not yet optimal. However, a spatial index
> would reduce the segments-to-be-compared by a factor of about 6 (see
> below). So if the spatial index generation is (slightly) faster, it
> would be an alternative.
>
> We've done another test to research this:
> - brute force (O(n^2)):  11856331 comparisons (factor 339.95)
> - monotonic sections: 213732  comparisons (factor 6.13)
> - spatial index: 34877 comparisons (factor 1)
> These data are for a specific case, but it gives an idea.
>
> Regards, Barend
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel

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

```

More information about the geos-devel mailing list