How to pack multiple Tetris 2d rectangles?

Question

I have several rectangles of various widths and heights. I have a large rectangular platform to put them on. I want to pack them on one side of the platform so that they extend along the length (X), but keep the size across the width (Y) minimal. That is, place them like a tetris game. There can be no overlap, but there can be spaces. Is there an algorithm there?

Answer 1

Sounds like a Bin Packing option:

In the theory of computational complexity, the problem of packing bins is a combinatorial NP-hard problem. In this, objects of different volumes must be packed in a finite number of hoppers of capacity V in such a way as to minimize the number of drawers used.

There are many variations of this problem, such as 2D packaging, linear packaging, packaging by weight, packaging cost, etc. They have many applications, such as filling containers, forklifts, cargo tanks, backing up files to removable media and routings in the implementation of FPGA custom hardware.

A quote from the same page about possible solutions:

Since it is NP-hard, the most efficient known algorithms use heuristics to achieve results which, although very good in most cases, may not be the optimal solution. For example, the first matching algorithm provides a quick, but often not optimal solution, including placing each item in the first box in which it will fit. This requires time Θ (n log n) where n is the number of elements to be packed. The algorithm can be made much more efficient when first sorting a list of elements to reduce the order (sometimes known as an algorithm with decreasing first order), although this does not guarantee an optimal solution and for longer lists, the algorithm can increase the operating time.

I suggest you follow the links on this page on Wikipedia. In addition, using Google’s Hopper Seal algorithm, you will probably find a lot of relevant information.

Answer 2

This is called 2D Strip Packing, and he worked on Martello. If you are doing a Google search for your paper, their algorithm should be fairly easy to implement. One way to do this is to solve your problem using a branch and a border. First figure out the greedy solution to get the maximum height required by your packaging.

Then your algorithm should first find a set of x-coordinates, which is promising, and then find the y-coordinates for your rectangles. In other words, for each rectangle, answer all possible x coordinates that you can assign. At any time, you can save the sum of the total height occupying any particular x coordinate (this is called the cumulative constraint), and crop if the height exceeds the maximum maximum height. For each complete x-coordinate solution where all the x-coordinates of the rectangles are assigned, now you can try to find the real y-coordinates. You can do this in the same way, branching out each possible y-coordinate for each rectangle, cropping when you know that the two rectangles overlap. At the bottom of the tree you will find the x and y coordinates for your rectangles, at this point you can calculate the required height and update the maximum upper bound.

If you saved the current solution when you updated your upper bound, then when your algorithm completes, you will get the optimal solution.