Эффективное размещение 2D-фигур в прямоугольнике. Как подойти к этому?

Question

Я искал повсюду семь интернетов, но безрезультатно.Наиболее близким к тому, что мне нужно, кажется проблема режущего материала , только в 2D (что разочаровывает, поскольку Википедия не дает никаких указаний о том, как ее решить).Еще одна похожая проблема - развертывание ультрафиолета .Там есть решения, но только те, которые вы получаете из надстроек различных 3D-программ.

Сокращение длинного разговора - я хочу вот что: учитывая прямоугольник известной ширины и высоты, я долженузнайте, сколько фигур (многоугольников) известных размеров (которые могут вращаться по желанию) я могу уместить внутри этого прямоугольника.

Например, я мог бы выбрать Т-образную фигуру и в том же прямоугольнике, который мог быупакуйте его оба эффективными способами, в результате чего получится 4 фигуры на прямоугольник

, а также мозаичные элементы на основе их ограничивающих прямоугольников, в случае которых я смог уместить только 3

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

Answer 1

рассмотрите то, что сказал другой ответ, поместив буквы t в квадрат, но вместо того, чтобы просто оставить его в виде квадрата, задайте фигуры в списке. Затем используйте True и False, чтобы заполнить вложенный список как форму, т. Е. [[True, True, True], [False, True, False]] для вашей T-формы. Затем используйте функцию для размещения фигур на сетке. Чтобы оптимизировать результаты, создайте трекер, который будет обращать внимание на то, сколько ложных значений в новой фигуре перекрываются с истинными значениями, которые уже есть в сетке из предыдущих фигур. Функция поместит фигуру в место с наибольшим количеством наложений. Потребуются модификации для создания все более высоких оптимизаций, но это общая предпосылка, которую вы ищете.

Answer 2

Кто-нибудь хочет поиграть в Тетрис (часть вашей проблемы)?

Это известно как проблема с упаковкой .Не зная, с какими формами вы, вероятно, столкнетесь раньше времени, может быть очень трудно, если не невозможно, придумать алгоритм, который даст вам лучший ответ.Скорее всего, если ваши полигоны не являются «хорошими» полигонами (кружками, квадратами, равносторонними треугольниками и т. Д.), Вам, вероятно, придется согласиться на эвристику, которая в большинстве случаев дает вам примерное наилучшее решение.Общая эвристика (хотя далеко не оптимальная в зависимости от формы входного многоугольника) будет заключаться в том, чтобы упростить задачу, нарисовав прямоугольник вокруг многоугольника так, чтобы прямоугольник был достаточно большим, чтобы покрыть многоугольник.(В качестве примера на диаграмме ниже мы рисуем красный прямоугольник вокруг синего многоугольника.)

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

Эффективный подход рекурсивного разбиения для упаковки одинаковых прямоугольников в прямоугольник .

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

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

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