ENH: geometry agnostic Voronoi based on shapely

[martinfleis]

This pushes upstream code I have been refactoring for momepy. It is an implementation of Voronoi tessellation that works not only with points but also lines and polygons by discretising their boundaries into a set of points and dissolving the result back.

It also does not use scipy but shapely and avoids unnecessary bottlenecks when clipping the result to pre-defined limit.

It makes sense to me that it lives in cg rather than in momepy, where I'll just wrap it and add sensible default values that work for building footprints.

It is a bit different than existing voronoi_frames so I am not sure what is the best way forward here... I can try to mimic the API and eventually replace the scipy version with this one. Not sure what is the best way forward.

[codecov[bot]]

Codecov Report

Attention: 8 lines in your changes are missing coverage. Please review.

Comparison is base (65379ef) 85.0% compared to head (6c2b321) 85.0%. Report is 1 commits behind head on main.

Additional details and impacted files

[](https://app.codecov.io/gh/pysal/libpysal/pull/678?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal) ```diff @@ Coverage Diff @@ ## main #678 +/- ## ======================================= - Coverage 85.0% 85.0% -0.1% ======================================= Files 141 141 Lines 15061 15187 +126 ======================================= + Hits 12809 12907 +98 - Misses 2252 2280 +28 ``` | [Files](https://app.codecov.io/gh/pysal/libpysal/pull/678?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal) | Coverage Δ | | |---|---|---| | [libpysal/cg/tests/test\_voronoi.py](https://app.codecov.io/gh/pysal/libpysal/pull/678?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal#diff-bGlicHlzYWwvY2cvdGVzdHMvdGVzdF92b3Jvbm9pLnB5) | `100.0% <100.0%> (ø)` | | | [libpysal/graph/\_triangulation.py](https://app.codecov.io/gh/pysal/libpysal/pull/678?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal#diff-bGlicHlzYWwvZ3JhcGgvX3RyaWFuZ3VsYXRpb24ucHk=) | `97.9% <100.0%> (ø)` | | | [libpysal/graph/tests/test\_triangulation.py](https://app.codecov.io/gh/pysal/libpysal/pull/678?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal#diff-bGlicHlzYWwvZ3JhcGgvdGVzdHMvdGVzdF90cmlhbmd1bGF0aW9uLnB5) | `98.8% <100.0%> (ø)` | | | [libpysal/cg/voronoi.py](https://app.codecov.io/gh/pysal/libpysal/pull/678?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal#diff-bGlicHlzYWwvY2cvdm9yb25vaS5weQ==) | `72.9% <94.6%> (-15.7%)` | :arrow_down: | | [libpysal/weights/contiguity.py](https://app.codecov.io/gh/pysal/libpysal/pull/678?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal#diff-bGlicHlzYWwvd2VpZ2h0cy9jb250aWd1aXR5LnB5) | `78.6% <20.0%> (ø)` | | ... and [1 file with indirect coverage changes](https://app.codecov.io/gh/pysal/libpysal/pull/678/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal)

[ljwolf]

I think this is great. I would just drop this in directly, and write a wrapper to intercept the old arguments and warn about the new argument names next release, with voronoi_frames() being changed fully over within 2 releases.

[martinfleis]

I have merged this with voronoi_frames including some transition period. There are very minor differences in the output:

• with clip=False, shapely defaults to a rectangle going significantly beyond the extent of original points but still way smaller that what libpysal is doing at the moment. See the comparison:

I can try to expand that but I don't think it is worth it very much, so I'd just say this is a price to pay.

• the polygons may have slightly different coordinates due to me fixing the geometry precision. So if there are some downstream tests checking exact geometries, those may fail.

Still need to update docstring and add tests.

[martinfleis]

CI failing due to some deep dependency in GDAL causing segfaults... solution in progress elsewhere.

[martinfleis]

The only remaining failures are caused by a geopandas regression on main https://github.com/geopandas/geopandas/issues/3178.

Ready for review!

[ljwolf]

The test failure looks like geopandas#3180, which should resolve once that lands in geopandas. So, given that the rest of the tests pass, I will merge this now!