Fast algorithm to uncross any crossing edges in a set of polygons

Question

I have a number of polygons each represented as a list of points. I'm looking for a fast algorithm to go through the list of polygons and uncross all of the crossed edges until no crossed edges remain.

Psudocode for current version:

While True:
    For each pair of polygons:
         for edge1 in first_polygon:
             for edge2 in second_polygon:
                 if edges_cross(edge1,edge2): # Uses a line segment intersection test
                     uncross_edges(first_polygon,second_polygon,edge1,edge2)
    If no edges have been uncrossed:
        break

This can be improved a fair bit by replacing the while loop with recursion. However, it's still rather poor in terms of performance.

Below is a simple example of the untangling*. The there'll actually be a large number of polygons and a fair number of points per polygon (around 10-500). The red line shows which two edges are being uncrossed. The result should always be a series of planar graphs, although not sure if there are multiple valid outcomes or just one.

Edit: This time I added the lines first then added the points, and used a bit more complex of a shape. Pretend the points are fixed.

Answer 1

First, let us illustrate what you want (if I got it right). Suppose you have two polygons, one of them has an edge (a, b) which intersects with an edge (s, r) of the other one. These polygons also have a clock-wise orientation, so you know the next vertex after b, and the next vertex after r. Since the edges crosses, you remove them both, and add four new ones. The new ones you add are: (a, r), (r, next(b)); (s, b), (b, next(r)). So you again have two polygons. This is illustrated in the following figure. Note that by initially removing only two edges (one from each polygon), all the crossing were resolved.

Speeding the trivial implementation of O(n^2) per iteration is not entirely easy, and 500 points per polygon is a very small amount to be worried about. If you decide that you need to improve this time, my initial suggestion would be to use the Bentley-Otmann algorithm in some smart way. The smart way involves running the algorithm, then when you find an intersection, you do the procedure above to eliminate the intersection, and then you update the events that guide the algorithm. Hopefully, the events to be handled can be updated without rendering the algorithm useless for this situation, but I don't have a proof for that.