I would like to design an algorithm to pack closed paths into a rectangle. An example of one of these paths is below:
The rectangle will have a fixed width, but the height will expand to accommodate the paths.
A Simple Approach I Already Tried:
Calculate the smallest rectangle that inscribes the path. (Results were later improved by rotating the path until its width was as small as possible). Pack the paths left to right, and if the remaining width is too small, expand the height and pack on the next row. This approach, however, loses optimizations with concavity. I want optimizations like this to be made:
But with the current approach I get this:
What type of algorithms can be used to optimize both concave and convex shape packing?
Paths cannot overlap, be warped, or contain other paths (like a square in a square), but they can be rotated for optimal packing