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

The Euclidean Bipartite Matching (EBM) problem in graph theory (Google it) seeks to match blue and red points so as to minimize the sum of all the edge lengths. It can be solved by using the Hungarian Algorithm. To see that this is a crossing-free graph, just consider your "bad" and "good" picture. The sum of the edge lengths is always less in the "good" picture. (Here is a slightly more detailed argument.)

Here is another SO answer that gives more detail.

And here is an interesting article about how EBM is used on Android to track multi-touch.

Answer 2

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).

Answer 3

I'm not sure how to prove it, but it feels correct that there must always exist at least one pair of points (ax1,ay1)->(bx1,by1) which define a line that subdivides the space into two distinct halves. Each half having the same number of unpaired a and b points. I can't come up with a layout of points for which this isn't the case.

Once this subdivision is found the two points are marked as connected and the two half spaces on either side are processed again. This repeats until both half spaces contain zero points.

Finding the subdividing pair isn't trivial, but it can be done by an exhaustive search. Hopefully someone will come up with a less computationally intensive method, but this should work.

Answer 4

It's already been answer indirectly here: How do you detect where two line segments intersect?

It's easy for you to test any combination of points connected and check if they intersect or not!