Polygon Chain - Conversion to non-crossing while preserving shape?

Question

I have polygon chains similar to the following...

...given the chain in the image, how would I go about calculating a chain that defines the same shape but without crossing paths?

Specifically, in the case of the image's input chain, the result I want looks like this:

A1,
A2,
Intersect between A2 and A3,
Intersect between A3 and A4,
A4,
A5,
Intersect between A3 and A4,
A3,
Intersect between A3 and A2,
A6

I'm looking for an algorithm to accomplish this for any chain, but I'm not sure what I'm trying to do is even called, which makes searching for a solution tricky.

If there's a name for what I'm trying to do it would be of great help to know it.

Thank you for any assistance!

Answer 1

Here's a simple algorithm:

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

If following a branch doesn't lead back to that intersection before getting to the end of the chain that means you have skipped a loop, so you need to choose the other branch.

For your example, running this algorithm would produce

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