Упаковка произвольных многоугольников в произвольной границе

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

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

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

Спасибо.

Ответ 1

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

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

Ответ 2

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

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

Начните свой счетчик формы в точке N.
Добавьте самую большую "форму упаковки", которую вы можете полностью разместить внутри полигональной границы, не накладывая никаких других форм упаковки.
Уменьшите свой счетчик формы.
Если ваш счетчик формы > 0, перейдите к шагу 2.

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

EDIT: Шаг 2 сам по себе является трудным. Разумной стратегией было бы выбрать произвольную точку внутри полигона как центр и "раздуть" диск, пока он не коснется границы или другого диска (или обоих), а затем "сдвиньте" диск, продолжая надувать так, чтобы он оставался внутри границы без перекрытия каких-либо других дисков, пока он не "заперт" - по крайней мере с двумя точками контакта с границей и/или с другими дисками. Но формализовать этот "скользящий процесс" непросто. И даже если вы правильно выполняете скользящий процесс, эта стратегия не гарантирует, что вы найдете самый большой "дискриптивный диск" - ваш "локально максимальный" диск может быть захвачен "лепестком" интерьера, который соединен узкой "шеей" свободного пространства до более крупного "лепестка", где будет больший диск.

Ответ 3

Этот тип проблемы очень сложно решать геометрически.

Если вы можете принять хорошее решение вместо 100% оптимального решение, то вы можете решить его с помощью растрового алгоритма.

Вы рисуете (растеризуете) граничный многоугольник в одну в памяти изображение и заполняющий многоугольник в другое изображение в памяти.

Затем вы можете более легко найти место, где будет заполняться полигон вписывается в граничный многоугольник, накладывая два изображения на различные (X, Y) смещения для заполнения многоугольника и проверки значения пикселей.

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

Ключевыми словами для поиска google являются: растеризация, оверлей, алгоритм

Ответ 4

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

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