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

[Martin Davis]

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