[geos-devel] Possible speed improvement for overlay operations

[Martin Davis]

I don't think this is an accurate analysis of how the Overlay noding works.

In the current JTS/GEOS Overlay algorithm the noding phase works like this:

1. Compute self-intersection nodes for Geometry A
2. Compute self-intersection nodes for Geometry B
3. Compute intersection nodes for Geometry A against Geometry B

In steps 1 and 2 the noder (MCSweepLineIntersector) has to process all
overlaps of all chains, but each step is only processing chains for a
single geometry.  Note that this process is NOT O(n^2), it is much more
performant due to the use of a sweep-line algorithm.   (If it was O(n^2)
overlay would be too slow to be usable..)

In step 3 the noder processes all chains from both geometries, but due to
the previous self-noding it only needs to process overlaps between chains
from different geometries.

Other ideas about performance improvements are welcome.  For instance, I
have had some ideas about only noding geometry in the region of actual
overlap in the case of an intersection computation.  That probably has
implications for robustness, however.  Needs some research...



On Thu, Nov 29, 2018 at 10:18 AM Paul van der Linden <
paul.doskabouter at gmail.com> wrote:

> 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...
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181129/8e9c78b1/attachment.html>