Учитывая количество прямоугольников, которые можно повернуть, найдите вмещающий прямоугольник минимальной площади

Question

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

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

Есть предложения?

-Edit-

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

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

Answer 1

Я получил хорошие результаты, используя этот алгоритм:

http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy

Редактировать:

Алгоритм, описанный в предоставленной мной ссылкедаст вам ответ «Да» или «Нет» относительно того, может ли данный набор прямоугольников быть упакован в определенный вмещающий прямоугольник.Чтобы найти минимальный вмещающий прямоугольник, вы можете запустить алгоритм несколько раз.По сути, вычислите нижнюю границу и верхнюю границу для охватывающего прямоугольника, затем выполните бинарный поиск, чтобы найти минимальное решение, которое попадает в эти границы.Я предполагаю, что вмещающий прямоугольник имеет фиксированный размер в одном измерении (т. Е. Ширина постоянна, ищет минимальную длину или наоборот).Если разрешено варьировать ширину и длину окружающего прямоугольника, то это более сложно, и это может не сработать.

Простой (но наивный) подход к вычислению нижней и верхней границ будет следующим::

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

Верхние границы - Худший случай, когда каждый прямоугольник должен быть упакован в отдельную «строку», поэтому для каждого вводапрямоугольник, вычислите min(width, height) и суммируйте их (т. е. притворные входные прямоугольники накладываются друг на друга, используя минимальную ширину или высоту каждого входного значения, так чтобы другой размер входного значения не превышал ширину окружающего прямоугольника).

Если вы работаете немного усерднее, вы можете значительно улучшить нижнюю и верхнюю границы, чтобы сократить пространство поиска, но это должно дать вам отправную точку.