Implement polygon subdivision and expose via C API

[Brendan Ward]

We would like to expose subdivide functionality in pygeos (​https://github.com/pygeos/pygeos/issues/244), relatively similar in intent to ST_Subdivide in PostGIS (​https://postgis.net/docs/ST_Subdivide.html). While this could be handled in client libraries, there may be broader appeal to this functionality in GEOS, as well as the ability to leverage some of the internals for better performance.

For highly complex, irregular polygons (e.g., country or continent boundaries with coastlines), performing subdivision first can greatly speed up spatial index, predicate operations (e.g., intersects), and subsequent intersections.

Essentially, the algorithm in ST_Subdivide recursively subdivides a polygon along the longest axis (width or height) until a target number of vertices are reached. Lower dimension results are discarded along the way.

Since each step in the recursion involves clipping (using intersection) the polygon into a given half, it seems like the noding required for each intersection operation may be a performance bottleneck, and it also involves holding a lot of geometries in memory.

It may be possible recursively calculate the subdivision points in advance, perhaps similar in overall intent to STRtree (or perhaps using a KdTree to partition vertices), and perform a final step to clip the polygon by those partitions. Using an approach that sorts vertices no more than necessary will also likely yield performance benefits (i.e., once vertices are bucketed into groups of N vertices, they do not need to be sorted further).

In order to expose this through the C API, it seems like the primary return value would be either a MultiPolygon (MultiLineString / MultiPoint if other core types supported).

I need to study the internals more to formulate a good plan here. Advice welcome!

I will try to put together a PR to implement this, though it may take some time. My C++ is very rusty...

[robe]

Retargeting in prep for GEOS 3.10.0 release

[dbaston]

Migrated to ​https://github.com/libgeos/geos/issues/717