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.

Answer 2

It seems that you want to end up with an embedded planar polygon whose vertices are exactly a given collection of points. The desired "order" on the points is what you get by going around the boundary of the polygon and enumerating the vertices in the order they appear.

For a given collection of points in general there will be more than one embedded polygon with this property; for an example, consider the following list of points:

(-1,-1), (0,0), (1,0), (1,1), (0,1)

This list defines a polygon meeting your criteria (if I understand it correctly). But so does the following ordering of this list:

(-1,-1), (1,0), (0,0), (1,1), (0,1)

Here is one algorithm that will work (I don't know about fast).

First, sort your points by x-coordinate (eg with quicksort) in increasing order (call this list L).

Second, find the convex hull (eg with quickhull); the boundary of the convex hull will contain the leftmost and rightmost points in the sorted list L (call these L[1] and L[n]); let S be the subset of points on the boundary between L[1] and L[n].

The list you want is S in the order it appears in L (which will also be the order it appears in the boundary of the convex hull) followed by the other elements L-S in the reverse of the order they appear in L.

The first two operations should usually take time O(n log n) (worst case O(n^2)); the last will take time O(n). The polygon you get will be the lower boundary of the convex hull (from left to right, say), together with the rest of the points in a "zigzag" above them going from right to left.