Алгоритм определения (x, y) координат для прямоугольников, чтобы площадь окружающего прямоугольника была минимальной?

Question

Надеюсь, мой титул имеет смысл, но вот что я пытаюсь сделать:

У меня есть n прямоугольников, каждый с шириной W _n и высотой H _n , которые мне нужно расположить на двухмерной (x, y) плоскости прямоугольник, в который они все помещаются, занимает наименьшую площадь. Мне также нужно иметь возможность установить, что (x, y) соответствует какому прямоугольнику.

Я бы предпочел что-то в псевдо-коде, но могу работать со многими языками.

Спасибо за помощь.

Answer 1

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

Answer 2

Это вариант упаковки 2D бункера. Тот факт, что ваш контейнер является гибким, позволяет оптимизировать и сделать его более сложным (как в случае с трудностями). Drools Planner (с открытым исходным кодом Java) может справиться с этим. Существует по крайней мере одна реализация (см. Список рассылки пользователя) с Drools Planner (не с открытым исходным кодом). Если вам нужен пример с открытым исходным кодом, вероятно, хороший баланс для облачного баланса в drools-planner-examples.

Обзор алгоритмов, которые вы можете использовать, см. мой ответ на аналогичный вопрос .

Answer 3

Звучит NP-полный для меня. Вроде как проблема с рюкзаком. Что означает, что нет реального решения. Только хорошие приближения.

Answer 4

Ваша проблема известна как проблема упаковки 2D. Даже 1D проблема NP-трудна. См. здесь для хорошей статьи о некоторых подходах вместе с примером кода C #.

Также смотрите следующие вопросы:

• Как программно определить, как поместить небольшие коробки в большую упаковку?
• Где я могу найти алгоритмы упаковки 2d бина с открытым исходным кодом?