[geos-devel] Possible speed improvement for overlay operations

[Darafei "Komяpa" Praliaskouski]

On Fri, Nov 30, 2018 at 12:05 AM Martin Davis <mtnclimb at gmail.com> wrote:

> 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.
>

Can you share one?

I used one from Mapnik, and it has comments on how AGG is tolerant to
"box-clamping" so they don't bother.

Fixing the clipped one, even slowly, will be beneficial, as it's used for
interval clipping in Z/M dimensions which is not available in
GEOSIntersects.


>
> 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.
>

May it happen that snap-rounding for axis aligned overlaps is more trivial
than one for generic overlap?


>
> 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
>
> _______________________________________________
> 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/20181130/dea305d7/attachment-0001.html>