[geos-devel] Possible speed improvement for overlay operations
mtnclimb at gmail.com
Sat Dec 1 14:07:13 PST 2018
Interesting idea. Sounds like should be discussed on a different thread,
On Sat, Dec 1, 2018 at 2:34 AM Darafei "Komяpa" Praliaskouski <me at komzpa.net>
> 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 <mtnclimb at 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.doskabouter at 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
>>> Increased a counter here
>>> SimpleMCSweepLineIntersector.cpp#L161 and put a breakpoint here
>>> 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 at lists.osgeo.org
> Darafei Praliaskouski
> Support me: http://patreon.com/komzpa
> geos-devel mailing list
> geos-devel at lists.osgeo.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the geos-devel