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.

[Hrsh-Venket]

I would like to tackle this issue.

As I understand it, the implementation of the monotone decomposition algorithm that you are referring to is called monotone_subdivision

The alternative approach, just as implemented parry, invlolves monotone decomposition then removing all diagonals that do not create concave polygons.

I could also work on documenting not only this new function but also the pre-existing monotone decomposition function.

@urschrei and @rmanoka I am eager to get your remarks on the same.