Разложение многоугольника с самопересечениями

Question

Как разложить многоугольник с самопересечениями на множество простых многоугольников?

Входной многоугольник P = {p1, ... pn} задается набором из n вершин с ориентацией против часовой стрелки.Я хотел бы выполнить склонение для набора из m многоугольников P1, ..., Pm.

Простая прогулка по отрезкам отпересечение с соседним не дает никакого эффекта;есть 2 сегмента с одной и той же начальной точкой, представленной точкой пересечения.

Возможно, поможет лексикографический вид ребер ...

Answer 1

Рассчитайте все пересечения, создайте новые узлы и разделите ребра на пересечениях, для каждого узла создайте список смежных ребер.

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

Повторите с первой вершины, у которой еще есть ребра.