Разложение многоугольника с самопересечениями
Как разложить многоугольник с самопересечениями на множество простых многоугольников?
Входной многоугольник P = {p1, ... pn} задается набором из n вершин с ориентацией против часовой стрелки. Я хотел бы выполнить декомпозицию для набора из m многоугольников P1, ..., Pm.
Простая прогулка по отрезкам от пересечения до следующего не дает никакого эффекта; Есть 2 сегмента с одинаковой начальной точкой, представленной точкой пересечения.
Возможно, какой-то лексикографический вид краев может помочь...
1 ответ
Рассчитайте все пересечения, создайте новые узлы и разделите ребра на пересечениях, для каждого узла создайте список смежных ребер.
Начните с какого-то момента. Идите, используя наибольшее ребро против часовой стрелки от текущей вершины (относительно последнего ребра). Добавьте пройденные ребра в многоугольник и удалите их (или отметьте). Когда вы вернетесь к той же вершине, закройте полигон.
Повторите с первой вершины, у которой еще есть ребра.