11

如何将两组坐标中的点与线连接，而不与任何相交的线相交？

我有两种类型的点(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

在此处输入图像描述

4

4 回答 4

5

图论中的欧几里得二分匹配 (EBM) 问题 (Google it) 旨在匹配蓝点和红点，以最小化所有边长的总和。它可以通过使用匈牙利算法来解决。要查看这是一个无交叉图，只需考虑您的“坏”和“好”图片。在“好”图片中，边缘长度的总和总是较小。（这里有一个更详细的论点。）

这是另一个提供更多详细信息的SO 答案。

这是一篇有趣的文章，关于如何在 Android 上使用 EBM 来跟踪多点触控。

于 2013-09-28T16:57:04.507 回答
2

这是一种我认为很有前途的方法。创建一对红色和蓝色点 (R1,B1), (R2,B2), .. (Rn,Bn)。然后遍历列表，为每个 (Rj,Bj) 画一条直线 Rj--Bj。如果这条线与已绘制的任何其他线 Ri--Bi 交叉，则通过将它们替换为 Ri--Bj 和 Rj--Bi 来“取消交叉”这些线（实际上将您的“坏”图片更改为“好”图片）。

您必须检查这些新线是否与任何其他现有线交叉，在这种情况下，您重复执行相同的“交换”和“交叉检查”，直到不再有交叉线。然后在 (Rj,Bj) 之后继续加入该对，依此类推，直到完成。

正如我在另一个答案中所指出的那样，最小化总边长的一对红点和蓝点也将是无交叉的。在此答案中给出的方法中，请注意，每次“不交叉”边缘时，都会减少所有边缘长度的总和。该算法很可能不会达到具有最小边长总和的配对配置。然而，总边长随着每次交换而减少的事实意味着算法将始终终止（即您不会进入重复的边交换序列）。

于 2013-09-29T02:22:43.817 回答
1

我不确定如何证明这一点，但感觉正确的是，必须始终存在至少一对点 (ax1,ay1)->(bx1,by1) 定义一条将空间细分为两个不同部分的线。每一半有相同数量的未配对的 a 和 b 点。我无法想出一个不是这种情况的点布局。

一旦找到这个细分，这两个点就被标记为已连接，并且再次处理两侧的两个半空间。重复此过程，直到两个半空间都包含零点。

找到细分对并非易事，但可以通过详尽的搜索来完成。希望有人会提出一种计算量较小的方法，但这应该可行。

于 2013-09-27T14:28:34.533 回答
0

这里已经间接回答了：你如何检测两条线段相交的位置？

您可以轻松测试任何连接点的组合并检查它们是否相交！

于 2013-09-27T01:51:49.500 回答