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

  • $\begingroup$ I suspect there are some constraints that haven't been stated. Can paths overlap? Can one shape be wholly inside another shape? Can paths be rotated? Can they be deformed? $\endgroup$
    – D.W.
    Jun 14 '20 at 21:23
  • $\begingroup$ @D.W. Deformation and overlap: no. Each shape is an exclusive volume in 2D. As for rotation, yes, I wouldn't mind rotating the shapes to pack. $\endgroup$
    – Hackstaar
    Jun 15 '20 at 3:30
  • $\begingroup$ OK. Can you edit the question to clarify the constraints? We'd prefer that the question be self-contained and read well for someone who encounters it for the first time, and that people not need to read the comments to understand what is being asked. Thank you! $\endgroup$
    – D.W.
    Jun 15 '20 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.