Есть ли алгоритм покрытия вогнутого многоугольника (содержащего дыры) выпуклыми многоугольниками?

К этому можно подойти двумя способами:

i) разбив данный многоугольник на выпуклые многоугольники так, чтобы между выпуклыми многоугольниками не было перекрытия

ii) покрывая данный многоугольник выпуклыми многоугольниками так, что их объединение дает исходный многоугольник. В этом случае между выпуклыми многоугольниками может быть перекрытие.

Хотя разбиение охватывает весь многоугольник, количество выпуклых многоугольников можно уменьшить с помощью второго подхода. Также известно, что покрытие вогнутого многоугольника (второй подход) минимальным числом выпуклых многоугольников является NP-трудным.

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


algorithm computational-geometry polygons
person Kvsn Raju    schedule 24.11.2017    source источник
comment
Нет, он не должен перекрывать данный полигон не более чем !!   -  person Kvsn Raju    schedule 24.11.2017
comment
Вы ищете polygon decomposition на выпуклые части. Самые простые способы - polygon triangulation и trapezoidal decomposition   -  person MBo    schedule 24.11.2017
comment
Спасибо за ответ. Я ищу алгоритмы, отличные от триангуляции, поскольку она дает мне много выпуклых многоугольников.   -  person Kvsn Raju    schedule 24.11.2017
comment
@KvsnRaju: легко найти случаи, требующие линейного числа многоугольников (что делает как триангуляцию, так и трапециевидное разложение асимптотически оптимальным в худшем случае). Поэтому вам следует уточнить приемлемое число.   -  person Yves Daoust    schedule 24.11.2017

Ответы (1)


arrow_upward
0
arrow_downward

Как уже писали MBo и Yves Daoust в комментариях к вашим вопросам. Разложение многоугольника на выпуклые многоугольники может быть выполнено с помощью триангуляции (или трапецеидального разбиения). Это приведет к тому, что простой многоугольник P с n вершинами и n-2 (внутренними) треугольниками будет линейным по количеству вершин.

Другой способ построить выпуклое разложение - использовать обобщенный граф мотоцикла. Я предполагаю, что должен быть способ попроще! Основная идея состоит в том, чтобы запустить мотоцикл m для каждой рефлексной вершины r в P. Каждый мотоцикл m движется с заданной скоростью в заданном направлении и оставляет за собой след. Если другой мотоцикл встречает такой след, он разбивается, т. Е. Останавливается, но оставляет след. Обобщенное относится к встраиванию в P и к тому, что границы многоугольника функционируют как стены, где мотоциклы также разбиваются. Кроме того, если два мотоцикла встречаются в одной точке, мы должны запустить другой, или в этом случае просто продолжить движение с одного и остановить другой. После того, как все мотоциклы разбились, есть график следов, который на самом деле представляет собой выпуклую мозаику P. Есть несколько статей (one here), но реализация будет сложной. В результате получается O (r) выпуклых многоугольников, покрывающих внутренность P.

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

Также упоминается в комментариях: можно создать ввод, который заставит O (n) полигонов. Просто представьте себе многоугольник в форме звезды, у которого n / 2 рефлексных вершин (внутренний угол> pi).

person gue    schedule 06.12.2017