Заполнить произвольную 2D-фигуру заданным набором прямоугольников
У меня есть набор прямоугольников и произвольной формы в 2D-пространстве. В форме не обязательно многоугольника (это может быть круг), а прямоугольники имеют разную ширину и высоту. Задача состоит в том, чтобы приблизить форму прямоугольниками как можно ближе. Я не могу изменить размеры прямоугольников, но вращение разрешено.
Это звучит очень похоже на проблему упаковки и проблему покрытия, но площадь покрытия не является прямоугольной ...
Я думаю, это проблема NP, и я' Я уверен, что должны быть какие-то статьи, которые показывают хорошую эвристику, чтобы решить эту проблему, но я не знаю, что гуглить? С чего мне начать?
Обновление: Одна мысль только что пришла мне в голову, но я не уверен, стоит ли ее исследовать. Что, если мы рассматриваем ограничивающую форму как физическую форму, заполненную водой. Каждый прямоугольник рассматривается как положительно заряженная частица с размером. Теперь бросьте наименьший прямоугольник к нему. Затем бросьте следующий по размеру в случайной точке. Если прямоугольники слишком близко, они отталкиваются друг от друга. Продолжайте добавлять прямоугольники, пока все не будут использованы. Может ли этот метод работать?
3 ответа
Я думаю, вы могли бы поискать алгоритмы упаковки и автоматического создания макетов. Алгоритмы генерации автоматической компоновки VLSI могут нуждаться в подобных вещах, так же как и вопросы компоновки текстиля...
Эта работа Hegedüs: Algorithms for covering polygons by rectangles, похоже, рассматривает схожую проблему. А поскольку эта работа датируется 1982 годом, может быть интересно взглянуть на статьи, которые цитируют эту работу. Кроме того, эта встреча, кажется, обсуждает проблемы исследования, связанные с этим, так что может быть отправной точкой для ключевых слов или имен, которые занимаются исследованиями в этой идее.
Я не знаю, есть ли в исследованиях по вычислительной геометрии алгоритмы для вашей конкретной проблемы, или достаточно ли эти алгоритмы просты/практичны для реализации. Вот как бы я подошел к этому, если бы мне пришлось делать это, не имея возможности посмотреть предыдущие работы. Это только направление, но далеко не решение...
Сформулируйте это как проблему оптимизации. У вас есть дискретные переменные - какие прямоугольники вы выбираете (да или нет) и непрерывные переменные (расположение и ориентация треугольников). Теперь вы можете задать две независимые оптимизации: дискретную, которая выбирает прямоугольники, и непрерывную, которая оптимизирует расположение и ориентацию после того, как прямоугольники даны. Чередуйте эти две оптимизации. Конечно, сложность заключается в формулировке оптимизаций, а также в проектировании энергии ошибки таким образом, чтобы она не застревала в некоторых странных конфигурациях (локальных минимумах). Я бы попытался получить непрерывную задачу в виде задачи наименьших квадратов, чтобы можно было использовать стандартные библиотеки оптимизаций.
Я думаю, что эта проблема подходит для решения с помощью генетического алгоритма и/или алгоритма эволюционной стратегии. Я решил аналогичную задачу упаковки коробок с помощью какого-то алгоритма эволюционной стратегии. Проверьте это в моем блоге.
Так что, если вы будете использовать такой подход - закодируйте в хромосомы поле:
- координата x
- координата y
- угол
Затем попытайтесь минимизировать такую фитнес-функцию-
y = w1 * box_intersection_area + w2 * box_area_out_of_shape + w3 * medium_circle_radius_in_free_space
Выберите веса w1,w2,w3 так, чтобы они влияли на важность факторов. Когда генетический алгоритм найдет частичное решение - удалите прямоугольники, которые все еще пересекаются друг с другом или не имеют формы - и у вас будет по крайней мере правильное (но не обязательно оптимальное) решение.
удачи в решении этой интересной задачи!
Это действительно сложная NP, и, поскольку она имеет высокотехнологичное применение, достаточно эффективные приближенные стратегии не описаны даже в патентах, не говоря уже об опубликованных статьях.
Лучшее, что вы можете сделать с ограниченным бюджетом, — это начать с ограничения проблемы. Предположим, что все прямоугольники абсолютно одинаковы. Предположим, что все прямоугольники, которые являются двоичными подразделениями вашего стандартного прямоугольника, также разрешены, поскольку вы можете эффективно предварительно упаковать их, чтобы они соответствовали вашему основному подразделению. Для дополнительных очков вы также можете сформировать несколько фиксированных схем для склеивания основных прямоугольников, чтобы покрыть несколько более крупных форм с существенно разными пропорциями. Предположим, что вы можете изменить размеры своего стандартного прямоугольника/ячейки, пока остальная часть (схема предварительной упаковки и склеивания) остается неизменной - это дает вам параметры для определения приблизительного размера основного прямоугольника на основе прямоугольников, которые вам даны.
Теперь вы можете поиграть с соотношением сторон, чтобы приблизить ошибку, которую может гарантировать такая ограниченная система. Для первых итераций предположим, что он может иметь 50%-ную ошибку с простой схемой подразделения, а затем изменить схему, чтобы уменьшить ошибку, но без увеличения асимптотической сложности предварительной упаковки. В конце дня вы всегда просто назначаете заданные прямоугольники своей предварительно рассчитанной и теперь фиксированной сетке и двоичным подразделениям - это означает, что вы вообще не пытаетесь сделать макет или вернуться - вы всегда довольны первым приблизительным вписаться в сетку.
Работайте над определением классов прямоугольников, которые хорошо сочетаются с вашей схемой — это опять-таки для того, чтобы весь процесс был инвертирован — вы никогда не пытаетесь на самом деле подогнать то, что вам дано — вы определяете, что вам должно быть дано, чтобы выполнить это хорошо - тогда вы считаете остальное ошибкой, поскольку это приближение.
Затем вы можете попытаться сделать немного больше, но не намного — любой промах в поиске с возвратом или прибивание произвольно небольшой ошибки, и это экспоненциально.
Если вы находитесь в исследовательском центре и можете получить немного времени на суперкомпьютере, запустите там серию исчерпывающих поисков с патологическими смесями, просто чтобы посмотреть, как может выглядеть оптимальная упаковка, и посмотреть, сможете ли вы вывести еще несколько схем подразделений. и/или классы наборов прямоугольников.
Этого должно хватить на первые 2 года исследований :-)