Цепочка полигонов - переход в непересекающийся при сохранении формы?

Question

У меня есть многоугольные цепочки, похожие на следующие ...

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

В частности, в случае цепочки ввода изображения желаемый результат выглядит следующим образом:

A1
A2
Пересекаются между A2 и A3 ,
Пересекаются между A3 и A4 ,
A4
A5
Пересекаются между A3 и A4 ,
A3
Пересекаются между A3 и A2 ,
A6

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

Если есть название для того, что я пытаюсь сделать, было бы очень полезно узнать это.

Спасибо за любую помощь!

Answer 1

Вот простой алгоритм:

for each line segment in the chain:
    Identify any segments which cross this segment
    If crossings > 0
         Follow the branch to the right, if this doesn't lead back to the 
         current intersection follow the branch to the left
    go to the next line segment

Если следование по ветке не приведет к этому пересечению, пока не достигнет конца цепочки, это означает, что вы пропустили цикл, поэтому вам нужно выбрать другую ветвь.

Для вашего примера, запуск этого алгоритма даст

Start at segment A1-A2
No intersections, goto next
Segment A2-A3
Intersection A2-A3/A6-A5 choose right path and store the current intersection somewhere
Segment A6-A5
Intersection A6-A5/A4-A3 choose right path and store intersection
Segment A3-A4
A4-A5
A5-A6
Back at intersection A6-A5/A4-A3, go right again to be back on A4-A3
A3-A2
Back at intersection A2-A3/A6-A5, go right again
Finish