Możliwy duplikat:
Algorytm potrzebny do pakowania prostokątów w dość optymalny sposób

mamN prostokąty, każdy o losowym rozmiarze (losowa szerokość i wysokość). Wszystkie prostokąty są równoległe do osi X i Y. Szukam algorytmu, który pomaga mi układać te prostokąty obok siebie w taki sposób, że wynikowy prostokąt ograniczający ma minimalną powierzchnię, a potencjalne przerwy wokół / pomiędzy wejściowymi prostokątami są tak małe, jak to możliwe. Prostokąty nie mogą być obracane i nie mogą się nakładać.

(Potrzebuję ich, aby zautomatyzować aranżację ikonek, dzięki czemu mogę tworzyć arkusze sprite i zapisywać lokalizacje sprite z różnych obrazów, które otrzymuję od animatorów).

Na przykład:

+---+   +----------+
| 1 |   |    2     |
+---+   +----------+                 +----------+..           +---+----------+
                                     |    2     |..           | 1 |    2     |
+--------+                ===>       +--------+-+-+    vs     +---+----+-----+
|        |                           |        | 1 |           |        |......
|    3   |                           |    3   +---+           |    3   |......
+--------+                           +--------+....           +--------+......

                                       Unused: 8                 Unused: 18

Niewykorzystane miejsce jest oznaczone kropkami (.) Na rysunku. Ponieważ pierwszy wynik ma prostokąt ograniczający z mniejszą nieużywaną przestrzenią, lepiej znaleźć ten układ wejściowych prostokątów.

Czy istnieje już algorytm, który w tym pomaga? Zrobiłem dużo googlingu, ale większość wyników wiąże się ze znalezieniem minimalnego prostokąta ograniczającego lub znalezieniem, czy N prostokątów pokrywa wcześniej określony obszar.