[geos-devel] Any sneaky tricks for speeding up operations with complex geometries?

[Nyall Dawson]

On Tue, 27 Aug 2019 at 13:51, Martin Davis <mtnclimb at gmail.com> wrote:
>

Thanks for the quick reply Martin!

> About the union question, probably no good news there, unless your data has some very unlikely characteristics.  The GEOS Cascaded Union approach is remarkably efficient at unioning sets of overlapping polygons - which it sounds like you have.  The other alternative hack is to run buffer(0), but it is unlikely to be faster.

Ok, thanks for the confirmation. Is there any benefit in "batching"
sets of geometries to cascaded union (e.g. unioning 100 geometries in
sets of 10, and then doing a final union of the result)? Or best to
throw EVERYTHING at GEOS and let it sort it out?

> IF the data was a true polygonal coverage (i.e. strictly non-overlapping) then there is a faster approach in GEOSCoverageUniion.  [1].  But if you are trying to find gaps then it's likely your data is not a true coverage.

Interesting. I have one application which would definitely benefit
from this. GEOS 3.8 looks to be a very exciting release..! One thing I
couldn't determine from the coverage PR and the docs of the new
operation is what happens when the data **isn't** a non-overlapping
coverage. Is the result total garbage in this case or is an exception
raised? Are holes/non-contiguous parts allowed?

> As for actually finding gaps, the good news is that there likely is a more efficient and effective approach. But it's not implemented directly in GEOS, so will take some work to accomplish.  The algorithm is to reduce the input to a large set of line segments, and then discard all segments which occur more than once (irrespective of direction/vertex order).  What is left will be the outer boundaries and any internal gaps which occur.  You can then refine this by looking for segments which are nearly, but not exactly parallel.  It would probably be nice to provide this as GEOS functionality at some point...

Thanks -- let me mull on that one!

Nyall

>
>
> [1] https://github.com/libgeos/geos/pull/158
>
> On Mon, Aug 26, 2019 at 7:50 PM Nyall Dawson <nyall.dawson at gmail.com> wrote:
>>
>> Hey GEOS community!
>>
>> I'm wondering if anyone has any sneaky/brilliant approaches on
>> speeding up GEOS operations with complex input geometries. Right now
>> I'm looking for a way to speed up a unary union operation with the
>> order of 100 input polygons, each of which is quite complex. I'm
>> currently throwing these all into GEOSUnaryUnion and relying on GEOS
>> to internally do things the best way, but I suspect there IS some
>> optimisations I could do to pre-process the geometries in order to
>> speed up the actual union operation.
>>
>> Has anyone any tips here?
>>
>> The other operation I'd like to optimise somehow is detecting whether
>> gaps exist between a set of features. Currently the code is unioning
>> all the input goemetries, then differencing it against the area of
>> interest and checking if the result is empty. I suspect there's a much
>> smarter way of doing this which would avoid the expense of the
>> differencing operation, so I'd love to hear if anyone has any
>> optimised approaches for handling this...
>>
>> Nyall
>> _______________________________________________
>> 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