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

[urschrei]

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]

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