[geos-devel] Intersection determination for overlay in GGL?
Barend.Gehrels at geodan.nl
Tue Sep 22 10:51:13 EDT 2009
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the geos-devel