[geos-devel] Possible speed improvement for overlay operations

[Martin Davis]

I did some quick metrics, on real-world geometries (outlines of countries,
flipped in X and then intersected.  This exercises the sweepline a lot, and
the MonoChains are utilized to their potential).

France : 921 vertices   Overlaps = 3,329
Norway: 4155 vertices.   Overlaps = 13,344
Russia: 14,747 vertices   Overlaps = 36,124

So the overlap count is much less than n^2, as expected.  And the overlap
count is going up (very)approximately) linearly with the vertex count.

Note that the Monotone Chains also provide efficiency in determining actual
segment intersections, since they enable binary search.

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/f8414b01/attachment.html>