[geos-devel] Possible speed improvement for overlay operations

[Martin Davis]

Right, I remember you reporting out on that experiment.

At the moment I can't think of a *simple* way to convert the "box-clamped"
geometry to a valid geometry for use in Overlay.   But there might be a
clever way to do this - it's an interesting question.  (One issue as you
probably realize is that the clamped geometry can have a LOT of "collapsed"
edges, including one which may wrap multiple times around the box, in the
worst case...)  But maybe it's better just to implement a robust clipping
algorithm - there's a few implementations around to use as inspiration.

Collapsed linework causes problems in the topology-building phase of
overlay - the noding doesn't care.   I've been wrestling with this a bit
recently, to try and get snap-rounding to work.  Unfortunately it's not
easy.  One issue is that the GeometryGraph code is quite complex and
supports both overlay and relate computation.  I think these are probably
going to have to split apart, and then both can be optimized for their
different usages.

I'm still optimistic that limiting noding to the overlap area (i.e. the
rectangle in the case of clipping) might work and be faster.  But I might
be missing something key that will make this a non-starter.


On Thu, Nov 29, 2018 at 12:20 PM Darafei "Komяpa" Praliaskouski <
me at komzpa.net> wrote:

> Other ideas about performance improvements are welcome.  For instance, I
>> have had some ideas about only noding geometry in the region of actual
>> overlap in the case of an intersection computation.  That probably has
>> implications for robustness, however.  Needs some research...
>>
>
>
> I tried to implement this speed up in PostGIS via box clipping.
> Current GEOS recangle clipping is unfortunately not robust, but helps
> quite a lot when not crashing.
>
> I tried redoing clipping by doing just O(N) clamping to the box. Result
> retains many required properties (ie, raycasting will give correct
> inside/outside result for it, area is okay) but has holes touching edges
> and edges touching themselves. GEOSIntersection can't handle that.
>
> Is there a simple way to recover the boundary for such geometry to feed
> further to GEOSIntersection? Buffer(,0) does not help in many cases,
> ST_MakeValid too.
>
> Can we make GEOSIntersection handle such invalid input, or is it
> completely incompatible with monotone chain conception?
> --
> 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/20181129/35dd2da6/attachment.html>