ENH: reimplement tessellation using shapely

[martinfleis]

WIP but f****ing hell how the time has changed what is possible now.

Performance comparison on 10k buildings - newWall time: 35 s, old Wall time: 47.7 s

Still space for improvements I think. What is great is that GEOS gives us directly polygons which we know are topologically clean.

[martinfleis]

Got it down to Wall time: 10.6 s in 2ca9832 :)

[codecov[bot]]

Codecov Report

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

Comparison is base (29c0e5d) 97.5% compared to head (9de5899) 97.1%. Report is 1 commits behind head on main.

Additional details and impacted files

[](https://app.codecov.io/gh/pysal/momepy/pull/538?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal) ```diff @@ Coverage Diff @@ ## main #538 +/- ## ======================================= - Coverage 97.5% 97.1% -0.5% ======================================= Files 26 27 +1 Lines 4189 4210 +21 ======================================= Hits 4086 4086 - Misses 103 124 +21 ``` | [Files](https://app.codecov.io/gh/pysal/momepy/pull/538?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal) | Coverage Δ | | |---|---|---| | [momepy/functional/\_elements.py](https://app.codecov.io/gh/pysal/momepy/pull/538?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal#diff-bW9tZXB5L2Z1bmN0aW9uYWwvX2VsZW1lbnRzLnB5) | `0.0% <0.0%> (ø)` | |

[martinfleis]

Squeezed it under 10s to 9.77, 5x times faster than before with cleaner geometry (it resolves #537).

It is at the moment less robust in terms of input data. Original tessellation does not error on overlapping polygons and similar issues. It produces erroneous geometry but produces something. This fails on GEOSException. I am not sure which way is better but I tend to say that geometries should be cleaned before running tessellation. We can probably provide some tooling for that, maybe on top of @sjsrey's geoplanar.

Still missing support of LineString tessellation (edge points conflict) and enclosed tessellation.

[martinfleis]

I'm thinking that since this is fairly generic polygon-based Voronoi tessellation it may be better to have it in libpysal.cg, no? Rather than hidden in momepy.

[martinfleis]

When passing a limit, the main bottleneck becomes clip. See the profiling below. Might be worth looking in https://github.com/geopandas/geopandas/issues/1803#issuecomment-778637626 but the issue is not union here but a ton of intersections that is essentially void since the whole geom is within the limit. I might need to look into clip in geopandas and try to fix this over there.

[martinfleis]

Will be superseded by https://github.com/pysal/libpysal/pull/678

[martinfleis]

Superseded by https://github.com/pysal/libpysal/pull/678 and #559