Разделить самопересекающийся многоугольник (код C)

Question

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

Так вот пример. У меня есть связанный список с координатами x, y ребер и точками пересечения многоугольника. В соответствии с полигоном в этом picture это будет: (1) -> (2) -> (3) ... -> (7). То, что я пытаюсь сделать, - это получить края простых полигонов (треугольники здесь). В этом случае :: 1,2,7/3,4,5/5,6,7.

Answer 1

Я думаю, что Bentley-Ottman будет вашим лучшим выбором. Есть приятная интерактивная визуализация here. Еще одно приятное описание here.