[geos-devel] Possible speed improvement for overlay operations

[Darafei "Komяpa" Praliaskouski]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181201/48145b22/attachment.html>