I did some quick metrics, on real-world geometries (outlines of countries, flipped in X and then intersected. This exercises the sweepline a lot, and the MonoChains are utilized to their potential).
France : 921 vertices Overlaps = 3,329 Norway: 4155 vertices. Overlaps = 13,344 Russia: 14,747 vertices Overlaps = 36,124 So the overlap count is much less than n^2, as expected. And the overlap count is going up (very)approximately) linearly with the vertex count. Note that the Monotone Chains also provide efficiency in determining actual segment intersections, since they enable binary search. 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
