Как расположить N прямоугольников, чтобы покрыть минимальную площадь

Возможный дубликат:
Алгоритм, необходимый для достаточно оптимальной упаковки прямоугольников

У меня есть N прямоугольников, каждый случайного размера (случайная ширина и высота). Все прямоугольники параллельны осям X и Y. Я ищу алгоритм, который поможет мне расположить эти прямоугольники бок о бок таким образом, чтобы результирующий ограничивающий прямоугольник имел минимальную площадь, а потенциальные зазоры вокруг / между входными прямоугольниками были как можно меньше. Прямоугольники нельзя вращать, и они не могут перекрывать друг друга.

(Мне они нужны для автоматизации размещения игровых спрайтов, чтобы я мог создавать листы спрайтов и сохранять местоположения спрайтов из различных изображений, которые я получаю от аниматоров.)

Например:

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

                                       Unused: 8                 Unused: 18

Неиспользуемое пространство отмечено на чертеже точками (.). Поскольку первый результат имеет ограничивающий прямоугольник с меньшим неиспользуемым пространством, было бы предпочтительнее найти такое расположение входных прямоугольников.

Есть ли уже алгоритм, помогающий в этом? Я много гуглил, но большинство результатов связано с поиском минимального ограничивающего прямоугольника или с тем, чтобы определить, покрывают ли N прямоугольников заранее заданную область.


area algorithm math rectangles
person xxbbcc    schedule 11.01.2013    source источник
comment
См. Алгоритм stackoverflow.com/questions/1213394/   -  person wich    schedule 11.01.2013
comment
Это похоже (менее ограниченно) на проблему размещения интегральной схемы. Для этого вам нужен простой инструмент, и я не знаю, где его найти.   -  person Potatoswatter    schedule 11.01.2013
comment
Вы видели это: stackoverflow.com/questions/251488/? Это может помочь.   -  person Ajoy    schedule 11.01.2013
comment
@Potatoswatter - инструмент, который был бы хорош, но я также считаю эту проблему интересной и хочу посмотреть, как ее решить программно.   -  person xxbbcc    schedule 11.01.2013
comment
@wich Спасибо, я проверю. Не видел этого в результатах поиска, которые я получил.   -  person xxbbcc    schedule 11.01.2013

Ответы (1)


arrow_upward
3
arrow_downward

Решение, предложенное на странице Какой алгоритм можно использовать для упаковки прямоугольников различных размеров в наименьший возможный прямоугольник довольно оптимальным образом? выглядит неплохо, но я бы немного его изменил: вместо того, чтобы жадно расширять ограничивающую рамку на наименьшую область, жадно расширяйте ее до наименьшей области оставляя пространство больше, чем площадь, занятая оставшимися прямоугольниками. Также выберите следующий прямоугольник по наибольшему размеру, а не по наибольшей площади.

Это должно дать ему больше места на раннем этапе и предотвратить его постоянную нехватку места в последнюю минуту и ​​оставить в основном пустые поля.

person Potatoswatter    schedule 11.01.2013