I'm in search for an algorithm that takes the left side of the following graphic as an input and outputs a minimal amount of convex polygons as seen on the right side of the graphic.
The input mesh can be very complex and could contain several holes. The position of the vertices are not constrained to a grid.
The use case for this is the creation of multiple polygon shapes for the Box2D physics engine.
- The result does not need to be deterministic.
- The result does not need to be vertically striped.
- As trichoplax noted, the right part of the picture does not resemble the minimal polygon count that can be achieved. It's just an example.
- It's not necessary that it will find the absolute minimum of convex polygons. A fast algorithm is preferred over a "best solution" one.