search

georust / geo

Geospatial primitives and algorithms for Rust
https://crates.io/crates/geo
Other
1.47k stars 190 forks source link

Algorithm to partition a polygon (convex decomposition) using the Hertel-Mehlhorn algorithm #1171

Open urschrei opened 2 months ago

urschrei commented 2 months ago

Parry has an implementation here that should be straightforward to port.

Explanation: https://bjpcjp.github.io/pdfs/math/polygon-partitions-ADM.pdf

it’s worth noting that this algorithm, though widely used, has painful time complexity (at least O(n^4)), though the linked explanation notes that monotone polygon decomposition may be an alternative, faster approach. Geo has some monotone polygon functionality already, but it’s under-documented so I’m not sure whether it’s useful here (cc @rmanoka)

rmanoka commented 2 months ago

Yes, we currently have a monotone decomposition algorithm; if that could be used black-box, we can build on top of it.