[geos-devel] Possible speed improvement for overlay operations

[Martin Davis]

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 <me at 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 <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
>>> 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 at 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 at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181201/06f735c4/attachment.html>