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

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, 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!

-
This may belong in stackoverflow - apologies if this is so. –  Monte Jun 4 '10 at 4:23

In practice, Jason Dyer's suggestion of using a sweep line algorithm is a good one. In theory, there are better algorithms: for $n$ line segments with $k$ crossing points, the sweep line gives you time $O((n + k)\log n)$, and some other methods lead to $O(n\log n+k)$ running times; see e.g. Clarkson and Shor, Discrete Comput. Geom. 1989.
When the line segments themselves form a connected nonplanar graph (as in your case, where they form a path graph) even faster algorithms are possible (at most an iterated log factor away from linear time, and linear whenever $k$ is not too close to $n$): see my paper "Linear-time algorithms for geometric graphs with sublinearly many crossings" and its references. But I think these methods are too complicated to be practically useful.