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

[Barend Gehrels]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20090922/248b37fc/attachment.html