如何将两组坐标中的点与线连接起来而不与任何相交的线相交？
我有两种类型的点 (a1, a2, ..., an, b1, b2, ..., bn)，以及它们的 (x,y)坐标。
a 和点 b 中的每个点必须同时由一条直线连接，这样任何直线都不相交。
如何做到这一点？
输入(类型，x，y):
a x y b x y a x y b x y
输出(ax, ay, bx, by):
ax ay bx by ax ay bx, by
最佳答案
图论 (Google it) 中的欧几里德二分匹配 (EBM) 问题旨在匹配蓝色点和红色点，以最小化所有边长的总和。可以使用 Hungarian Algorithm 来解决.要看出这是一个无交叉图，只需考虑您的“坏”和“好”图片。 “好”图片中边长的总和总是较小。 (这里是 a slightly more detailed argument 。)
这是另一个 SO answer这提供了更多细节。
这里是 an interesting article about how EBM is used on Android to track multi-touch .
关于algorithm - 如何用不相交的线连接两种类型的点？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19041140/