我如何将两种类型的点不相交的线？ [英] How do I connect points of two types with lines without intersect?

问题描述

如何连接点的两组坐标与线不相交的任何交叉的线？

我有两个类型的点（A1，A2，...，一，B1，B2，......，BN），其（X，Y）坐标。

在

每个一点 A 键，点 B 必须用一条直线连接一次，使得没有该线相交。

如何才能做到这一点？

输入（式中，x，y）的

 一λY B X Y一λY B X Y
 

输出（AX，AY，BX，BY）：

  AX AY BX用斧头AY BX，由
 

在图论<股利类=h2_lin>解决方案

欧几里德偶匹配（EBM）的问题（谷歌它）寻求匹配蓝色和红色点，以便最小化所有的边缘长度的总和。它可以通过使用匈牙利算法的解决。一看就知道这是一个穿越无图，只需考虑你的坏和好的景象。边长度之和是在好的画面总是少。 （这里是一个稍微详细的论证。）

下面是另一个 SO回答，让更多的细节。

这里是<一个href="http://www.troodon-software.com/algorithms/android/2010/06/20/euclidean-bipartite-matching-multi-touch-and-android/"相对=nofollow>有关如何EBM用于在Android上跟踪多点触控一篇有趣的文章。

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

解决方案

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.

这篇关于我如何将两种类型的点不相交的线？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！