Interesting idea. Sounds like should be discussed on a different thread, perhaps?
On Sat, Dec 1, 2018 at 2:34 AM Darafei "Komяpa" Praliaskouski <m...@komzpa.net> wrote: > 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
_______________________________________________ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
