[geos-devel] Possible speed improvement for overlay operations

[Martin Davis]

Some more thoughts:

- it is always good to validate that algorithms are working as expected.
What happens if you use best-case geometry as input?  E.g. a square with
dense but flat edges?

- if the overlay algorithms really were egregiously O(n^2) I'm fairly sure
that would have been noticed by now.  n^2 is REALLY slow on large inputs.
You can easily test for n^2 by creating a sequence of increasingly
densified inputs.

- One way to improve performance for the worst-case geometries you are
using is to switch from a sweep-line to using a true spatial index (such as
the STRtree).  The MCIndexNoder uses this approach. One downside of this is
that the order of processing overlaps becomes somewhat non-deterministic,
which has been problematic for some uses.

On Fri, Nov 30, 2018 at 1:25 PM Martin Davis <mtnclimb at gmail.com> wrote:

> Those polygons are a worst-case scenario for MonotoneChains, and they are
> a sub-optimal case for sweepline as well.  So maybe not surprising you are
> seeing a n^2 count.
>
> There doesn't seem much point in working to optimize such an artificial
> case, especially if it will impact code complexity or performance for the
> "average" case.   But it's hard to speculate without a working
> demonstration of a potential improvement.
>
> On Fri, Nov 30, 2018 at 1:13 PM Paul van der Linden <
> paul.doskabouter at gmail.com> wrote:
>
>> Well, the part I'm referring to is the 1. and 2 (Compute
>> self-intersection nodes for A and B) as far as I understand.
>> Traced through from
>> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/GeometryGraph.cpp#L393
>> to
>> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L55
>> to
>> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L126
>>
>> Increased a counter here
>> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/
>> SimpleMCSweepLineIntersector.cpp#L161 and put a breakpoint here
>> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L166
>> counter's value at the end of the computeintersections was n*n, and
>> breakpoint never hit, so a lot of checks were done without any useful work.
>>
>> Not really sure how "representative" my polygons are, but they are
>> squares with zig-zag boundaries
>> /\/\/\/\/\/\/\/\
>> \              /
>> /              \
>> \              /
>> /              \
>> \              /
>> \/\/\/\/\/\/\/
>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181130/4a377e39/attachment-0001.html>