This is interesting. 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.
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." We can probably optimize further if shape is split into all-convex parts. сб, 1 дек. 2018 г. в 00:25, Martin Davis <mtncl...@gmail.com>: > 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 -- Darafei Praliaskouski Support me: http://patreon.com/komzpa
_______________________________________________ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
