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@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
