[geos-devel] Possible speed improvement for overlay operations

[Paul van der Linden]

I'm currently getting familiar with the GEOS code, especially to see if I
can improve the performance, and I saw a potential improvement from a
O(n^2) piece to a O(n*m) with according to my findings a rather small m.

It's in the combination of
SimpleMCSweepLineIntersector::computeIntersections and
SimpleMCSweepLineIntersector::processOverlaps.

For what I can see, (at least in my test case of 2 ordinary polygons
without holes) in processOverlaps, the ev0->edgeSet is not equal to nullptr
and for the rest all events[i]->edgeSet are the same.

So the condition on
https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L164
is never true and this whole method is doing nothing but burning cpu cycles.

My proposal involves changes in
SimpleMCSweepLineIntersector::computeIntersections:

One solution is to simply test if all edgeSets are equal and if so, skip
the whole processOverlaps, but that wouldn't help ofcourse in all
situations.
The other solution that I thought of, was to create lists for each
different edgesets and only call processOverlaps for edgeSets other than
the current one (ev @
https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L136
).

The latter one probably goes wrong, because I saw that the events are
sorted here
https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L113
and probably for a good reason.
Splitting that list into buckets of equal edgeset messes up that order.

Third solution is to come up with some kind of datastructure to get all
events without the ones having edgeset equal to ev, but in the correct
order...

Anyone any ideas on that?

Sidenode: I found that an easy way of testing performance is to get a
couple of very large polygons and put them through the desired algo
(intersect in this case).
Whenever your patience has run out, just press break in the debugger and
see where it stopped...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181129/397680cc/attachment.html>