12

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

enter image description here

arshajii
  • 127,459
  • 24
  • 238
  • 287
user2821655
  • 121
  • 1
  • 3

4 Answers4

6

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.

Community
  • 1
  • 1
brainjam
  • 18,863
  • 8
  • 57
  • 82
  • This is clearly the correct answer. The best illustration I've found for how/why it works is [here](http://www.youtube.com/watch?v=8gwq40ozFSk). The "basic" elements in the explanation give some justification for the cost alterations throughout the algorithm. – Speed8ump Sep 30 '13 at 14:25
  • @SpeedBump, I'm less sure that this is the best answer because it is "overkill". My understanding is that the Hungarian method is O(n^4) or O(n^3). My other answer here (http://stackoverflow.com/a/19073770/242848) gives what I believe is a faster method that yields a matching without trying to minimize total edge length. – brainjam Sep 30 '13 at 22:56
  • All of the algorithms I've seen mentioned are n^3 or worse, and this one has the benefit of being provably correct. My suggestion relies on the postulate that there is always a set subdivision which can divide the problem (which is difficult to prove). Your other suggestion requires that the swapping process you describe never yield a loop of repeating swaps (which seems possible). Given that the Hungarian Algorithm is also O(n^3) and provably correct it's the one I'd take...Unless I was looking to get published somewhere :) – Speed8ump Oct 07 '13 at 14:48
  • @Speed8ump, thanks for pointing this out (I updated my answer). 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). – brainjam Oct 07 '13 at 19:03
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).

Community
  • 1
  • 1
brainjam
  • 18,863
  • 8
  • 57
  • 82
  • There's a potential problem with this method, as swapping 2 pairs of points may create more crossing segments – NightRa Dec 27 '14 at 21:32
  • @NightRa, the algorithm takes this into account. See the 2nd paragraph. – brainjam Dec 27 '14 at 21:52
  • Right. The termination condition has nothing to do with the amount of intersection, but only on distances from the ponints in the pair, and as the total distance can't go further below the minimum, it terminates. – NightRa Dec 28 '14 at 13:28
  • What I'm interested to know is what's the time complexity of this algorithm. – NightRa Dec 28 '14 at 13:29
1

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.

Speed8ump
  • 1,307
  • 10
  • 25
  • I agrees to your idea. my first thought was to remove line (in the outer line) one by one using convex hull. but if convex hull has the same type of outer points, it will fail. look at this pic "http://s22.postimg.org/ce109t15t/image.png". and then, I have tried like you, divide-and-conquer method However, as a result, I haven't been able to find an efficient point which can be split. – user2821655 Sep 28 '13 at 04:36
  • finding the subdividing pair can be done in O(nlogn) actually. – user2782067 Nov 07 '17 at 02:11
0

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!

Community
  • 1
  • 1
Wagner Patriota
  • 5,494
  • 26
  • 49