Approximate Convex Decomposition in O(n) with the Hertel/Mehlhorn algorithm

[mrehayden1]

I'm thinking about tacking this for some work on navigation meshes.

I was wondering, should we allow the user to choose an arbitrary triangulation and pass that to the decomposition algorithm?

[noinia]

Cool! Briefly looking at the Hertel/Mehlhorn paper the algorithm is essentially this right?:

Observe that OPT ~ r/2 + 1 since one partitioning edge is necessary for each concave angle. We shall partition P into at most 2r + I convex subpolygons.
To do this, scan the n-3 triangulation edges one by one. Drop an edge if it divides two convex angles. Call edge e essential for point p if it cannot be dropped because it divides a concave angle at point p. It is easy to show that not more than two triangulation edges are essen- tial for each point with concave angle.

In that case, I think its probably easiest to just expose a function with type "PlaneGraph s point PolygonEdgeType PolygonFaceData -> PlaneGraph s point PolygonEdgeType PolygonFaceData "

and directly use the input PlaneGraph from the result of triangulate. E.g. so that someone can indeed use whatever way the triangulation was constructed. The above function should not be too hard to write I think; since it involves just filtering the edges and calling a function to reconstruct the planeGraph.