Proposed: Port ST_Subdivide from PostGIS

[brendan-ward]

ST_Subdivide divides complex geometries into smaller rectangular chunks of relatively similar vertex counts, which are then much better to use in spatial indexing, predicate, and related functions. The algorithm works by recursively cutting geometries along one dimension then the other.

This is not strictly about exposing GEOS internals to Python, so it might not be a good fit here. But given the recent work with Cython and strong dependence on internals here, it might be a worthwhile experiment (plus, I need this for one of my projects).

Unless there was opposition, I am hoping to try and implement this within Cython here.

[caspervdw]

I am not per se against it, but shouldn't this better be implemented upstream in GEOS?

[jorisvandenbossche]

For reference, the PostGIS implementation is here: https://github.com/postgis/postgis/blob/6812b00ed6195e151d04be8c78aa8f1c20c628ea/liblwgeom/lwgeom.c#L2268

It would be nice to have this functionality in PyGEOS. I agree with @caspervdw it sounds as this could be potentially be shared in GEOS (but something to ask there first, then). But I would personally not be against prototyping it already in pygeos on the short term, if you want to do this.

[brendan-ward]

Related GEOS ticket: https://trac.osgeo.org/geos/ticket/1075