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

Martin Davis mtnclimb at gmail.com
Mon Aug 26 20:54:18 PDT 2019


Hey Nyall!

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.

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.

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


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


More information about the geos-devel mailing list