Some more thoughts: - it is always good to validate that algorithms are working as expected. What happens if you use best-case geometry as input? E.g. a square with dense but flat edges?
- if the overlay algorithms really were egregiously O(n^2) I'm fairly sure that would have been noticed by now. n^2 is REALLY slow on large inputs. You can easily test for n^2 by creating a sequence of increasingly densified inputs. - One way to improve performance for the worst-case geometries you are using is to switch from a sweep-line to using a true spatial index (such as the STRtree). The MCIndexNoder uses this approach. One downside of this is that the order of processing overlaps becomes somewhat non-deterministic, which has been problematic for some uses. On Fri, Nov 30, 2018 at 1:25 PM Martin Davis <mtncl...@gmail.com> wrote: > Those polygons are a worst-case scenario for MonotoneChains, and they are > a sub-optimal case for sweepline as well. So maybe not surprising you are > seeing a n^2 count. > > There doesn't seem much point in working to optimize such an artificial > case, especially if it will impact code complexity or performance for the > "average" case. But it's hard to speculate without a working > demonstration of a potential improvement. > > On Fri, Nov 30, 2018 at 1:13 PM Paul van der Linden < > paul.doskabou...@gmail.com> wrote: > >> Well, the part I'm referring to is the 1. and 2 (Compute >> self-intersection nodes for A and B) as far as I understand. >> Traced through from >> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/GeometryGraph.cpp#L393 >> to >> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L55 >> to >> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L126 >> >> Increased a counter here >> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/ >> SimpleMCSweepLineIntersector.cpp#L161 and put a breakpoint here >> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L166 >> counter's value at the end of the computeintersections was n*n, and >> breakpoint never hit, so a lot of checks were done without any useful work. >> >> Not really sure how "representative" my polygons are, but they are >> squares with zig-zag boundaries >> /\/\/\/\/\/\/\/\ >> \ / >> / \ >> \ / >> / \ >> \ / >> \/\/\/\/\/\/\/ >> >> >>
_______________________________________________ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
