Title: Polygon Chain - Conversion to non-crossing while preserving shape?
Tags: c++;c;geometry;computational-geometry
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!

Comment: Your question is not very clear. Can you please provide a figure for what you expect the output to be? Also what exactly is meant by _same shape_? Shape does not seem well defined for paths...

Comment: @Moron, but I listed the *exact* output I'm looking for - the image I linked to gives the output I listed context.

Comment: Thanks for the edit Nick! I should have known I could just embed the image.

Comment: @Moron, "Also what exactly is meant by same shape?" - The best way I can explain it is, if you played "connect the dots" with the results chain you'd draw the exact same shape. You'd just be connecting the dots such that your pen never crossed a line it had already drawn (although it could stop at a single point more than once).

Here is the accepted answer: Here's a simple algorithm:

```for each line segment in the chain:
    Identify any segments which cross this segment
    If crossings &gt; 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
```

Comment for this answer: great visual explanation! Would +2 if I could.
Comment for this answer: @Monte You're right, it looks like it's possible for the algorithm to return to a previous path. If it does this however it must be the case that there is more than one bad intersection (else the other path would be traversable), so a record can be made of which intersections you've already tried, eg http://img526.imageshack.us/img526/3117/path.png
Comment for this answer: But wouldn't that break down if the intersects got complicated? As in this image: http://imgur.com/hBLwz.jpg


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 1, 'CommentCount': 4, 'ContentLicense': 'CC BY-SA 2.5', 'CreationDate': '2010:00:06/04/10', 'FavoriteCount': 0.0, 'PostTypeId': 1, 'Tags': '<c++><c><geometry><computational-geometry>', 'Title': 'Polygon Chain - Conversion to non-crossing while preserving shape?', 'ViewCount': 401, 'id': 2971518, 'user_AboutMe': '<blockquote>\n  <p>"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." - Brian Kernighan</p>\n</blockquote>\n', 'user_AccountId': 45924.0, 'user_DisplayName': 'Monte Hurd', 'user_Reputation': 4189.0, 'user_Views': 991.0, 'user_id': 135557.0}}