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

Question

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

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

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

Спасибо.

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

Этот тип задачи очень сложен для геометрического решения.

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

Вы рисуете (растеризуете) полигон границы в одно изображение в памяти, а полигон заливки - в другое изображение в памяти.

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

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

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

Answer 4

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

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