<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
Hi Martin,<br>
<br>
I was on holiday, therefore my delay in answering your question.<br>
<br>
<br>
Martin Davis wrote:
<blockquote cite="mid:4A9EB8AD.8060803@refractions.net" type="cite">Barend
Gehrels wrote:
  <br>
  <blockquote type="cite"><br>
The GGL overlay algorithm will be described in a paper. It is a modern
variant of the classic Weiler-Atherton algorithm.
    <br>
    <br>
  </blockquote>
Barend, the references I've seen about Weiler-Atherton don't specify
the approach taken to compute intersections.&nbsp; In my experience this is
the most time-consuming part of overlay computation. </blockquote>
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.<br>
<br>
<blockquote cite="mid:4A9EB8AD.8060803@refractions.net" type="cite">A
simplistic implementation is O(n^2), but there are a variety of
techniques which can be used to improve this.&nbsp; Can you comment on the
approach GGL uses for intersection determination?
  <br>
</blockquote>
We currently use <b>monotonic sections</b> 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.<br>
<br>
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. <br>
<br>
We've done another test to research this:<br>
- brute force (O(n^2)):&nbsp; 11856331
comparisons (factor 339.95)<br>
- monotonic sections: 213732&nbsp;
comparisons (factor 6.13)<br>
- spatial index: 34877
comparisons (factor 1)<br>
These data are for a specific case, but it gives an idea.<br>
<br>
Regards, Barend<br>
<br>
</body>
</html>