3
$\begingroup$

Imagine you have a number of 2-dimensional objects. The question is how to fit them all in a rectangular space in such a way that this rectangle takes the smallest area possible.

On the below image you can see (more or less) what I mean: enter image description here

The objects are packed quite efficiently (there is little empty space).

What I am after eventually is doing the same in 3D, but 2D is easier to start with. Of course all translate/rotate operations can be applied to those objects.

My quick research online did not bring any meaningful answers, but my first thought was to find longest edges of given objects and to position them along these edges to minimize space. Do you have any other ideas on how to approach this? Or maybe there already are some papers concerning this problem?

$\endgroup$
  • $\begingroup$ The topics of 2D bin packing and 3D bin packing and the cutting stock problem might be relevant here. I know it has been studied for rectangular shapes, but I don't know what's known about arbitrary shapes. Perhaps you can find something in the literature with these search phrases. $\endgroup$ – D.W. Dec 18 '17 at 18:55
  • $\begingroup$ @D.W. Thanks for input, knowing how to name the problem actually helps a lot. $\endgroup$ – alex Dec 18 '17 at 19:00

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.