Port of PostGIS ST_Subdivide to GEOS / downstream libraries

[Brendan Ward]

I would like to expose functionality similar to ST_Subdivide (https://postgis.net/docs/ST_Subdivide.html) in pygeos (ref: https://github.com/pygeos/pygeos/issues/244), which provides a Python interface to GEOS.

The algorithm recursively subdivides input geometries along alternating x vs y dimensions until a target number of vertices per geometry is reached, which can greatly improve spatial index performance for complex polygons (e.g., countries with coastlines).  Paul has written a very nice overview of it here: http://blog.cleverelephant.ca/2019/11/subdivide.html

Apologies if this has already been raised here; I was unable to find any record of such a discussion in Github, Trac, mailing list archives.

I did not find a counterpart in JTS, so perhaps this is out of scope for GEOS?

While we can take this on in a downstream library (and indeed may want to pilot there first), this seems like it would have broader appeal to the GEOS community if exposed via the C API.  There may also be potential performance improvements to leveraging aspects of something like STRtree to help identify x or y subdivision points (ideas not yet well developed though).

Is there any interest in providing something similar within GEOS?  If so, perhaps the next stage is to log this as a feature request to Trac.  I anticipated the need for a little discussion around this topic, so I'm raising here first.

Thanks,

BCW

--

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel

[Daniel Baston]

Hi Brendan,

I don't remember it being discussed anywhere, but it's certainly been floating around in my head for a while. I think it's very much worth pursuing.

Dan

On Fri, Nov 13, 2020 at 11:41 AM Brendan Ward <[hidden email]> wrote:

I would like to expose functionality similar to ST_Subdivide (https://postgis.net/docs/ST_Subdivide.html) in pygeos (ref: https://github.com/pygeos/pygeos/issues/244), which provides a Python interface to GEOS.

The algorithm recursively subdivides input geometries along alternating x vs y dimensions until a target number of vertices per geometry is reached, which can greatly improve spatial index performance for complex polygons (e.g., countries with coastlines).  Paul has written a very nice overview of it here: http://blog.cleverelephant.ca/2019/11/subdivide.html

Apologies if this has already been raised here; I was unable to find any record of such a discussion in Github, Trac, mailing list archives.

I did not find a counterpart in JTS, so perhaps this is out of scope for GEOS?

While we can take this on in a downstream library (and indeed may want to pilot there first), this seems like it would have broader appeal to the GEOS community if exposed via the C API.  There may also be potential performance improvements to leveraging aspects of something like STRtree to help identify x or y subdivision points (ideas not yet well developed though).

Is there any interest in providing something similar within GEOS?  If so, perhaps the next stage is to log this as a feature request to Trac.  I anticipated the need for a little discussion around this topic, so I'm raising here first.

Thanks,

BCW

--

Brendan C. Ward

Owner | Lead Software Engineer

Astute Spruce, LLC

astutespruce.com

541-250-9544

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel