Re: [geos-devel] Any sneaky tricks for speeding up operations with complex geometries?
On Thu, 29 Aug 2019 at 03:42, Martin Davis wrote: >> >> >> >> > 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? > > > Best to let GEOS handle it. It uses a spatial index to choose sets of > polygons to union. It's unlikely you could do this better (unless there is > some characteristic of the data you can take advantage of) Perfect, thanks Martin! > It looks like GEOSCoverageUnion is able to detect non-fully-noded inputs [1] > and overlaps [2], and throws an exception in this case. And this is ideal too, great. Nyall > > I would think holes and non-contiguous parts are fine as input. > > [1] > https://github.com/libgeos/geos/pull/158/files#diff-7cd9f5f9244e77677b80591da3d99207R94 > [2] > https://github.com/libgeos/geos/pull/158/files#diff-7cd9f5f9244e77677b80591da3d99207R123 > ___ > geos-devel mailing list > geos-devel@lists.osgeo.org > https://lists.osgeo.org/mailman/listinfo/geos-devel ___ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
Re: [geos-devel] Any sneaky tricks for speeding up operations with complex geometries?
> > > > > 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? > Best to let GEOS handle it. It uses a spatial index to choose sets of polygons to union. It's unlikely you could do this better (unless there is some characteristic of the data you can take advantage of) > > > 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? > > It looks like GEOSCoverageUnion is able to detect non-fully-noded inputs [1] and overlaps [2], and throws an exception in this case. I would think holes and non-contiguous parts are fine as input. [1] https://github.com/libgeos/geos/pull/158/files#diff-7cd9f5f9244e77677b80591da3d99207R94 [2] https://github.com/libgeos/geos/pull/158/files#diff-7cd9f5f9244e77677b80591da3d99207R123 ___ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
Re: [geos-devel] Any sneaky tricks for speeding up operations with complex geometries?
On Tue, 27 Aug 2019 at 13:51, Martin Davis 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 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@lists.osgeo.org >> https://lists.osgeo.org/mailman/listinfo/geos-devel > > ___ > geos-devel mailing list > geos-devel@lists.osgeo.org > https://lists.osgeo.org/mailman/listinfo/geos-devel ___ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
Re: [geos-devel] Any sneaky tricks for speeding up operations with complex geometries?
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 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@lists.osgeo.org > https://lists.osgeo.org/mailman/listinfo/geos-devel ___ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
