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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

y = w1 * box_intersection_area + w2 * box_area_out_of_shape + w3 * average_circle_radius_in_free_space

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

удачи в этой интересной проблеме!

Ответ 3

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

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

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

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

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

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

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