Заполнить произвольную 2D фигуру заданным набором прямоугольников

Question

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

Звучит очень похоже на проблема упаковки и проблема покрытия, но область покрытия не прямоугольная ...

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

Обновление: Одна мысль только что пришла мне в голову, но я не уверен, стоит ли ее исследовать.Что, если мы рассматриваем ограничивающую форму как физическую форму, заполненную водой.Каждый прямоугольник рассматривается как положительно заряженная частица с размером.Теперь бросьте наименьший прямоугольник к нему.Затем бросьте следующий по размеру в случайной точке.Если прямоугольники слишком близко, они отталкиваются друг от друга.Продолжайте добавлять прямоугольники, пока все не будут использованы.Может ли этот метод работать?

Answer 1

Я думаю, вы могли бы искать упаковку и алгоритмы автоматической генерации макета.Алгоритмам автоматической генерации макетов VLSI могут потребоваться аналогичные вещи, точно так же, как и вопросы текстильного макета ...

В этой статье Hegedüs: Алгоритмы покрытия полигонов прямоугольниками , кажется, решают аналогичную проблему.А поскольку эта статья написана в 1982 году, было бы интересно взглянуть на статьи , в которых цитируется эта статья .Кроме того, на этой встрече , похоже, обсуждаются проблемы исследования, связанные с этим, поэтому может быть отправной точкой для ключевых слов или имен, которые исследуют эту идею.

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

Сформулируйте это как задачу оптимизации.У вас есть дискретные переменные, из которых вы выбираете прямоугольники (да или нет) и непрерывные переменные (расположение и ориентация треугольников).Теперь вы можете настроить две независимые оптимизации: дискретную оптимизацию, которая выбирает прямоугольники;и непрерывный, который оптимизирует местоположение и ориентацию, как только даны прямоугольники.Чередуйте эти две оптимизации.Конечно, сложность заключается в формулировании оптимизаций и разработке энергии ошибки таким образом, чтобы она не застревала в некоторых странных конфигурациях (локальных минимумах).Я бы попытался получить непрерывную задачу как задачу наименьших квадратов , чтобы я мог использовать стандартные библиотеки оптимизации.

Answer 2

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

Так что, если вы будете использовать такой подход - закодируйте в поле хромосом:

• x координата
• yкоордината
• угол

Затем попытайтесь минимизировать такую ​​функцию пригодности -

y = w1 * box_intersection_area + w2 * box_area_out_of_shape + w3 * среднего_цирка_радиуса_in_free_space

Выберите веса w1, w2, w3, чтобы они влияли на важность факторов.Когда генетический алгоритм найдет частичное решение - уберите прямоугольники, которые все еще накладываются друг на друга или имеют неправильную форму - и у вас будет хотя бы законное (но не обязательно оптимальное) решение.

удачи в этой интересной задаче!

Answer 3

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

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

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

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

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

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

Этого должно быть достаточно для первых 2 лет или исследования: -)