如何将两种类型的点连接到没有相交的线？
use*_*655 10 algorithm geometry
如何将两组坐标中的点连接到没有相交的任何线相交的线？
我有两种类型的点(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) 问题寻求匹配蓝点和红点，以最小化所有边长度的总和。它可以通过使用匈牙利算法来解决。要查看这是一个无交叉图，只需考虑您的“坏”和“好”图片。在“好”图片中，边缘长度的总和总是较小。（这里有一个稍微更详细的论点。）
这是另一个提供更多细节的SO答案。
这是一篇关于如何在 Android 上使用 EBM 跟踪多点触控的有趣文章。