Я пытаюсь покрыть простой вогнутый многоугольник с минимумом прямоугольников. Мои прямоугольники могут быть любой длины, но они имеют максимальную ширину, и у многоугольника никогда не будет острого угла.
Я думал о попытке разложить мой вогнутый многоугольник на треугольники, которые создают набор минимально перекрывающихся прямоугольников, минимально ограничивающих каждый треугольник, а затем объединяют эти прямоугольники в более крупные. Тем не менее, я не думаю, что это будет работать для небольших надрезов по краям многоугольника. Треугольники, созданные рефлекторными вершинами на этих выемках, создадут неправильные прямоугольники. Я ищу прямоугольники, которые будут охватывать / игнорировать выемки.
Я действительно ничего не знаю о вычислительной геометрии, поэтому я не совсем уверен, как начать задавать вопрос.
Я нашел другие посты, которые были похожи, но не то, что мне нужно:
- разбить многоугольник на минимальное количество прямоугольников и треугольников
- Покрытие произвольного многоугольника с минимальным количеством квадратов
- Найдите прямоугольников, чтобы они покрывали максимальное количество точек
- Алгоритм нахождения наименьшего количества прямоугольников для покрытия набора прямоугольников
Несколько примеров: черный - вход. Красный - приемлемый результат.
Еще один пример: второй выход является предпочтительным. Тем не менее, генерация обоих выходов и использование другого фактора для определения предпочтения, вероятно, необходимы и не являются обязанностью этого алгоритма.
Полигоны, имитирующие кривые, встречаются крайне редко. В этом сценарии большая часть площади прямоугольников теряется. Однако это приемлемо, потому что каждый прямоугольник подчиняется ограничению максимальной ширины.
Кроме того, я обнаружил, что эта статья близка к тому, что мне нужно:
- Покрытие прямоугольными кусочками Пола Якоба, Даниэлы Маринеску и Кристины Луки
Может быть, лучше спросить: «Как я могу идентифицировать прямоугольные части вогнутого многоугольника?»
Вот изображение, показывающее желаемую реализацию:
Зеленый - фактическое использование материала. Красные прямоугольники - это макеты. Синий - это MBR всего многоугольника. Я думаю, что я должен попытаться получить маленькие MBR и заполнить их. 2-3 зеленых прямоугольника в верхнем левом углу, которые заканчиваются в середине многоугольника, дороги. Это то, что я хочу минимизировать. Зеленые прямоугольники имеют минимальную и максимальную ширину и высоту, но я могу использовать столько строк и столбцов, сколько необходимо для покрытия области. Опять же, я должен минимизировать количество прямоугольников, которые не охватывают входные данные. Я также могу изменить форму зеленого прямоугольника, чтобы он подходил для небольших мест, что также очень дорого. Другими словами, идеальное получение максимально возможного количества прямоугольников.
источник
Ответы:
Это вариант геометрического набора обложки. В зависимости от точных настроек, вы можете сделать хорошее приближение. Проблема, конечно, NP-Hard. Естественный прием состоит в том, чтобы использовать жадный алгоритм (всегда выбирайте прямоугольник / полосу, которая покрывает большую часть еще не покрытой области. Альтернативный метод заключается в использовании повторного взвешивания. Есть некоторые интересные теоретические результаты, но, честно говоря, ничего, что не должно быть слишком полезным на практике Один интересный улов, который вы, возможно, захотите попробовать, - это сначала разложить ваш многоугольник на минимальное количество выпуклых фигур (используя алгоритм динамического программирования Keil), а затем покрыть каждый выпуклый многоугольник отдельно ...
источник
Я думаю, что эта статья может помочь. Очевидно, что это не та же проблема - на самом деле это обратная проблема, покрывающая прямоугольник многоугольниками, - но некоторые идеи могут быть отправной точкой. В частности, эта обратная проблема является NP-сложной, и я подозреваю, что ваша проблема также может быть (хотя, насколько я могу судить, очевидного расширения сокращения нет).
Э. Аркин, А. Эфрат, Г. Харт, И. Костицына, А. Кроллер, Дж. Митчелл и В. Полищук. Скандинавские тонкие блюда на верхней части торта: на самой маленькой универсальной коробке. Веселье с алгоритмами . pg.16-27. 2012
источник