Как расположить N прямоугольников, чтобы покрыть минимальную площадь [дубликаты]
Возможный дубликат:
Алгоритм, необходимый для упаковки прямоугольников достаточно оптимальным способом
У меня есть N прямоугольники, каждый из которых имеет произвольный размер рост). Все прямоугольники параллельны X & Оси Y. Я'Я ищу алгоритм, который помогает мне расположить эти прямоугольники бок о бок таким образом, чтобы результирующий ограничивающий прямоугольник имел минимальную площадь, а потенциальные промежутки вокруг / между входными прямоугольниками были как можно меньше. Прямоугольники не могут вращаться и не могут перекрывать друг друга.
(Они нужны мне для автоматизации расстановки игровых спрайтов, чтобы я мог создавать листы спрайтов и сохранять местоположения спрайтов из различных изображений, которые я получаю от аниматоров.)
Например:
+---+ +----------+
| 1 | | 2 |
+---+ +----------+ +----------+.. +---+----------+
| 2 |.. | 1 | 2 |
+--------+ ===> +--------+-+-+ vs +---+----+-----+
| | | | 1 | | |......
| 3 | | 3 +---+ | 3 |......
+--------+ +--------+.... +--------+......
Unused: 8 Unused: 18
Неиспользуемое пространство отмечено точками (.) На чертеже. Поскольку первый результат имеет ограничивающий прямоугольник с меньшим неиспользуемым пространством, он 'Было бы предпочтительнее найти такое расположение входных прямоугольников.
Есть ли алгоритм, который помогает с этим? Я много гуглил, но большинство результатов связано с поиском минимального ограничивающего прямоугольника или с поиском, если N прямоугольников покрывают предварительно определенную область.