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
