<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">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">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">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>