<div dir="ltr">I don't think this is an accurate analysis of how the Overlay noding works.<div><br></div><div>In the current JTS/GEOS Overlay algorithm the noding phase works like this:<br></div><div><br></div><div>1. Compute self-intersection nodes for Geometry A</div><div>2. Compute self-intersection nodes for Geometry B</div><div>3. Compute intersection nodes for Geometry A against Geometry B</div><div><br></div><div>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..)</div><div><br></div><div>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.</div><div><br></div><div>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...</div><div><br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr">On Thu, Nov 29, 2018 at 10:18 AM Paul van der Linden <<a href="mailto:paul.doskabouter@gmail.com">paul.doskabouter@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div dir="ltr">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.<br><br>It's in the combination of SimpleMCSweepLineIntersector::computeIntersections and SimpleMCSweepLineIntersector::processOverlaps.<br><br>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.<br><br>So the condition on <a href="https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L164" target="_blank">https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L164</a> is never true and this whole method is doing nothing but burning cpu cycles.<br><br>My proposal involves changes in SimpleMCSweepLineIntersector::computeIntersections:<br><br>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.<br>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 @ <a href="https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L136" target="_blank">https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L136</a>).<br><br>The latter one probably goes wrong, because I saw that the events are sorted here <a href="https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L113" target="_blank">https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L113</a> and probably for a good reason.<br>Splitting that list into buckets of equal edgeset messes up that order.<br><br>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...<br><br>Anyone any ideas on that?<br><br>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).<br>Whenever your patience has run out, just press break in the debugger and see where it stopped...<br><br></div></div>
_______________________________________________<br>
geos-devel mailing list<br>
<a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a></blockquote></div>