[geos-devel] Possible speed improvement for overlay operations

[Martin Davis]

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