How do I connect points of two types with lines without intersect?

Question

How do I connect points from two sets of coordinates with lines without intersect any of the lines intersecting?

I have two types of points (a1, a2, ..., an, b1, b2, ..., bn), and their (x,y) coordinates.

Each one point in a and points b must be connected by a straight line at once such that none of the lines intersect.

How can this be done?

input (type, x, y):

a x y b x y a x y b x y

output (ax, ay, bx, by):

ax ay bx by ax ay bx, by

Answer 1

Here's an approach that I think is promising. Create a pairing of red and blue points (R1,B1), (R2,B2), .. (Rn,Bn). Then go through the list, and for each (Rj,Bj) draw a straight line Rj--Bj. If this line crosses any other line Ri--Bi already drawn, "uncross" these lines by replacing them with Ri--Bj and Rj--Bi (in effect changing your "bad" picture to your "good" picture).

You have to check whether these new lines cross any other existing lines, in which case you repeatedly perform the same "swap" and "crossing check" until there are no more crossing lines. You then go on to joining the pair after (Rj,Bj), and so on until you are done.

As noted in my other answer, a pairing of red and blue points that minimizes total edge length will also be crossing-free. In the approach given in this answer, note that every time you "uncross" edges you reduce the total of all the edge lengths. The algorithm most likely will not reach the pairing configuration with the minimum sum of edge lengths. However, the fact that the total edge lengths decrease with each swap implies that the algorithm will always terminate (i.e. you will not get into a repeating sequence of edge swaps).