<div dir="ltr">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).<div><br></div><div>France : 921 vertices   Overlaps = 3,329</div><div>Norway: 4155 vertices.   Overlaps = 13,344</div><div>Russia: 14,747 vertices   Overlaps = 36,124</div><div><br></div><div>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.</div><div><br></div><div>Note that the Monotone Chains also provide efficiency in determining actual segment intersections, since they enable binary search.</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>