<div dir="ltr">Some more thoughts:<div><br></div><div>- 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?</div><div><br></div><div>- 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.</div><div><br></div><div>- 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.</div></div><br><div class="gmail_quote"><div dir="ltr">On Fri, Nov 30, 2018 at 1:25 PM Martin Davis <<a href="mailto:mtnclimb@gmail.com">mtnclimb@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">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. <div><br></div><div>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.<div><div><br><div class="gmail_quote"><div dir="ltr">On Fri, Nov 30, 2018 at 1:13 PM Paul van der Linden <<a href="mailto:paul.doskabouter@gmail.com" target="_blank">paul.doskabouter@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div style="font-size:small">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.</div><div style="font-size:small">Traced through from <a href="https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/GeometryGraph.cpp#L393" target="_blank">https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/GeometryGraph.cpp#L393</a> to <a href="https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L55" target="_blank">https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L55</a> to <a href="https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L126" target="_blank">https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L126</a></div><div style="font-size:small"><br></div><div style="font-size:small">Increased a counter here <a href="https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/" target="_blank">https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/</a> SimpleMCSweepLineIntersector.cpp#L161 and put a breakpoint here <a href="https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L166" target="_blank">https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp#L166</a></div><div style="font-size:small">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.</div><div style="font-size:small"><br></div><div style="font-size:small">Not really sure how "representative" my polygons are, but they are squares with zig-zag boundaries</div><div style="font-size:small">/\/\/\/\/\/\/\/\</div><div style="font-size:small">\ /<br></div><div style="font-size:small">/ \<br></div><div style="font-size:small">\ /<br></div><div style="font-size:small">/ \<br></div><div style="font-size:small">\ /</div><div style="font-size:small">\/\/\/\/\/\/\/</div><div style="font-size:small"><br><br></div></div></div></div></div></div></div></div></div></blockquote></div></div></div></div></div>
</blockquote></div>