How do i pack multiple rectangles in a 2d box tetris style

Question

I have a number of rectangles of various widths and heights. I have a larger rectangular platform to put them on. I want to pack them on one side of the platform so they spread in the lengthwise (X) dimension but keep the widthwise (Y) dimension to a minimal. That is to place them like a tetris game. There can be no overlaps but there can be gaps. Is there an algorithm out there to do this?

Answer 1

Sounds like a variation of Bin Packing:

In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.

There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity, creating file backup in removable media and technology mapping in FPGA implementation of custom hardware.

A quote from the same page about possible solutions:

Since it is NP-hard, the most efficient known algorithms use heuristics to accomplish results which, though very good in most cases, may not be the optimal solution. For example, the first fit algorithm provides a fast but often nonoptimal solution, involving placing each item into the first bin in which it will fit. It requires Θ(n log n) time, where n is the number of elements to be packed. The algorithm can be made much more effective by first sorting the list of elements into decreasing order (sometimes known as the first-fit decreasing algorithm), although this does not guarantee an optimal solution, and for longer lists may increase the running time of the algorithm.

I suggest you follow some links from that Wikipedia page. Also, by Googling "bin packing algorithm" you'll probably find a lot of relevant information.

Answer 2

This is called 2D Strip Packing, and has been worked on by Martello. If you do a google search for their paper, their algorithm should be pretty easy to implement. One way to do it is to solve your problem using branch and bound. First compute a greedy solution to get a maximum height that your packing requires.

Your algorithm should then first find a set of x-coordinates that is promising, and then find the y-coordinates for your rectangles. In other words, for each rectangle, branch on all the possible x-coordinates you can assign it. At any point in time, you can keep a sum of the total height occupying any particular x-coordinate (this is called the cumulative constraint), and prune if the height exceeds your global maximum height. For every complete x-coordinate solution where all rectangles' x-coordinates have been assigned, you can now try to find valid y-coordinates. You can do this in the same way by branching, for every rectangle, on the different possible y-coordinates, pruning when you know two rectangles overlap each other. At the bottom of your tree you will have found both x and y-coordinates for your rectangles at which point you can compute the height required, and update your maximum upper bound.

If you have saved the current solution whenever you updated your upper bound, then when your algorithm terminates, you will have the optimal solution.