1
$\begingroup$

Consider a large rectangle frame, as we want to fill it with small rectangles with variable sizes. How to calculate the best match of inner objects to minimize empty spaces inside the main frame?

Alternatively, consider that the rectangle height is variable, how to re-arrange inner elements to minimize the main frame height.

An example is drawn in the following image. How to re-arrange the order (but not rotate) to fir the rectangle in the frame with minimum height (smallest possible frame).

enter image description here

2 Answers 2

2

This is the 2D version of the bin packing problem, which Wikipedia cites as 2D packing but doesn't have a page for. Certainly it is at least as hard-just make all your rectangles have one dimension as large as the larger dimension of the frame. A search on 2D packing turns up many references.

  • 0
    It was hard to find appropriate keywords for searching. I will follow your tip to explore the problem.2012-06-16
2

The problem is NP-hard, so only approximation algorithms are available. See the web page, Efficient algorithms for 2D rectangle packing, which compares performance on a number of such algorithms.