<div dir="ltr">Interesting idea.   Sounds like should be discussed on a different thread, perhaps?</div><br><div class="gmail_quote"><div dir="ltr">On Sat, Dec 1, 2018 at 2:34 AM Darafei "Komяpa" Praliaskouski <<a href="mailto:me@komzpa.net">me@komzpa.net</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">This is interesting.<div><br></div><div>In PostGIS 2.5 I changed ST_Subdivide to accommodate similar cases. The splits it's going to produce is a bunch of triangles on the edge and a bunch of box-shaped geometries in the meat of polygon. Putting these in a tree (new year, boxes in the tree) is probably going to help perform several smaller overlays faster.</div><div><br></div><div>What are the properties that help in such a split, and what are the ones that don't? For point-in-polygon it's definitely better to have large squares and get the outer void defined by the shape of the tree and not the shape of parts. Will another kind of algorithm for splitting in some predefined dimension help? Like, "if you see shape going up and then down, it's a good split point and it's more preferred than one close to center."</div><div><br>We can probably optimize further if shape is split into all-convex parts.<br><br><br><br><div class="gmail_quote"><div dir="ltr">сб, 1 дек. 2018 г. в 00:25, Martin Davis <<a href="mailto:mtnclimb@gmail.com" target="_blank">mtnclimb@gmail.com</a>>:<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><div dir="ltr"><div><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>
_______________________________________________<br>
geos-devel mailing list<br>
<a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a></blockquote></div></div></div>-- <br><div dir="ltr" class="m_-661925544326765357gmail_signature" data-smartmail="gmail_signature"><div dir="ltr">Darafei Praliaskouski<br>Support me: <a href="http://patreon.com/komzpa" target="_blank">http://patreon.com/komzpa</a></div></div>
_______________________________________________<br>
geos-devel mailing list<br>
<a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a></blockquote></div>