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.

Matrimonial

What do you mean by 'untangle'? Do you mean translate (along X-Y plane)? For example, you have a bunch of overlapping polygons and you want to move them all so none of them overlap. Or is it something else? – Sawicki

I've added an example image. – Matrimonial

Ah, ok. Makes sense now. :) Very interesting question. – Sawicki

Ya, I referred to it as "untangling" because it looks like a tangled mess when you have a few dozen polygons overlapped. – Matrimonial

This might be of interest: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.2212 (very math-y though) – Sawicki

You need a better definition as the solution is not unique. In the leftmost figure, why didn't you remove the two bottom edges, for example ? From your mid figure to the right figure, why did you create two new edges instead of a single one ? – Phosphoprotein

I've done a little searching. This problem is very widely studied in computer science. See: en.wikipedia.org/wiki/Planarity, en.wikipedia.org/wiki/Planarity_testing – Sawicki

@SimpleCoder that is not really the same problem, as the graph is being modified here, not only visually modified. – Phosphoprotein

@mmgp: What do you mean? – Sawicki

@SimpleCoder: take the left-most image. It is trivial to see it is a planar graph, just move the two disjoint set of edges far away. This is basically what planarity testing is about. Now, again, take his middle image. Edges were created and removed, this is not how planarity testing goes, otherwise any graph would be planar. – Phosphoprotein

@mmgp: I didn't notice that, good point. M C: is the diagram correct? Can nodes really be modified in your problem? – Sawicki

No it it's not planar testing, it's more like planar transformation. The nodes are fixed points, the edges can be moved though. The result should always be a planar graph through, so planar testing might still be useful. – Matrimonial

I'm aware it is not planar testing, it is unrelated to that. I think I'm getting what you want, we are almost there now :) I'm not sure if you are aware, but this is almost just like removing crossing edges as might be done in TSP to reduce the length of a earlier found tour. Or is there any difference from that one ? – Phosphoprotein

That would probably work nicely, don't suppose you where to find the algorithm? Preferably in python. – Matrimonial

It is called 2-Opt, very well known. – Phosphoprotein

2-opt is close but not quite what I need. The issue is that I'm effectively dealing with dozens of tours, and the result isn't expected to be a single planar shape but rather many. Still, if I can find the actual bit of 2-opt that handles swapping crossed edges, it should be helpful. – Matrimonial

Lol I messed up the example. I was wondering why there was only 1 polygon when there should have been 2... third time's the charm I suppose (I redid the example once already before posting it). It's updated now. – Matrimonial

It got worse now. In the first step you merged the polygons, then in the next step you decided to split them again. I have no idea what you are after then. – Phosphoprotein

Third time is not charm, seems I messed up more than I thought... – Matrimonial

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.

Phosphoprotein

Note that if this is really what you are after, then it is at least problematic: i.imgur.com/SbKQ0.png. You need to check for self-intersection too (which is immediately the situation of the 2-Opt algorithm). With this new example it is pretty much clear that Bentley-Ottman will not work after edge-swap. Although even if you run it multiple times, it would already be an improvement over the trivial algorithm. (I forgot to highlight some edges in the mid figure, but it should be clear the ones used based on the image at right.) – Phosphoprotein

Very close. Only two new edges are created. (a,r) and (s,b). The example actually shows two swaps simultaneously. In practice, it would be done in three steps instead of two. The polygon points are layered, so the problematic example you give shouldn't actually occur. I'll modify your example and post it as a second example if you have no issues with me doing so. – Matrimonial

You can't create only those edges, otherwise you don't have proper polygons. – Phosphoprotein

Incrementally. There are two places where edges cross. One creates two new edges the other creates two new edges. So the 4 edges would be removed and 4 would be created. – Matrimonial

That is not what an incremental algorithm is, that is a wrong algorithm. This way that I included here solves the problem of splitting and merging the polygons along the way, so you always have two polygons. Verify that the example included is equivalent to your "incremental" method, but always maintain a good invariant. – Phosphoprotein

Also I was looking at that algorithm, but I had concerns that it indeed would be rendered useless. – Matrimonial

You need to think more carefully about the Bentley-Ottman, specially if this is your first contact with it. – Phosphoprotein

I'll keep that in mind. In which case, that's probably about all there is for this question without me doing a large re-write of the question to make it more accurate. – Matrimonial

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.

Lafontaine

I should have pointed out that the result of a convex hull was purely due to the simplified nature of the example. The result is expected to be a large number of planar polygons, that are unlikely to be convex. – Matrimonial

Sorting and convex hull can be done in O(n log n), just use different algorithms if you are worried about worst-case of quick sort/quickhull. Now, I don't get your solution. What happens when the input vertices are not all on the convex hull ? – Phosphoprotein

Think about the example where the list L is something like (0,0), (1,a_1), (2,a_2), (3,a_3) , . . . , (n,0) where the a_i are any numbers bigger than 0. The set S is precisely the first and the last vertex, so the resulting list is (0,0), (n,0), (n-1,a_{n-1}), (n-2,a_{n-2}), . . . (1,a_1). – Lafontaine

If the OP just wants to form the "zigzag", there is no need to construct the convex hull of the points. Just pick the left-most and right-most points, then trace a virtual line connecting these points. Go from left to right connecting points above this imaginary line, repeat for the bottom part. This requires a sorting only. Now, it might be the case that this simple operation solves the question but I got the impression of something different being asked. – Phosphoprotein