什么是判断两条线段是否在一个容差范围内属于同一线段的最有效方法？

Question

编辑：修改了标题。我对两个线段是否相同不是很感兴趣，而是如果它们与彼此共线且在一定容差内，则应将这些线段聚集在一起作为单个线段。

编辑：我想简短地说：我正在尝试以有效的方式将相似的线段聚类在一起。

假设我有线段f (fx0, fy0)和(fx1, fy1)以及g (gx0, gy0) 和 (gx1, gy1)

这些来自像计算机视觉算法边缘检测器之类的东西，某些情况下，两条线段基本上相同，但由于像素容差而被视为两条不同的线段。

有几种情况

• f和g共享完全相同的端点，例如：f = (0,0), (10,10) g = (0,0), (10,10)
• f和g大致共享相同的端点，并且长度大致相同，例如：f = (0,0.01), (9.95,10) g = (0,0), (10,10)
• f是g的子集，意味着它的端点落在g段内并且与g段具有相同的斜率。想象一下粗略地画了一条线，在这条线上钢笔来回移动以使其变得更加粗壮。例如：f = (4.00, 4.02), (9.01, 9.02) g = (0,0), (10,10)

以下不会被视为相同：

• f和g具有大于某个容差的斜率差异
• f和g可能具有相同的斜率，但相隔超出容差的距离，即平行线
• f和g在同一平面和相同斜率上，但根本不重叠...即虚线内的一组线段。

最简单的方法是检查gx1 - fx1 <= 容差（对其他三个点重复此操作），但在某些情况下，线段f可能比线段g短（再次由于像素差异和/或照片扫描质量不佳）。

所以，把这两个线段转换成极坐标然后比较角度，是不是更好？这种情况下，这两个rho值将在一个公差内。但是，接下来你必须确保这两个线段具有相同的“方向”，这在笛卡尔或极坐标中计算是微不足道的。

所以，这很容易想出一种方法，但我只是想知道是否有一种更加简洁的方法，基于我早已忘记的线性代数？

- Zando

---

我认为你需要更清晰明了。指定一条线段需要四个数字，分别是线段起点和终点的坐标，而你似乎为每条线段给出了两个数字。此外，你是否认为从（0,0）到（1,1）的直线与从（0,0）到（10,10）的直线是“相同”的？显然它们都是朝着同一个方向，但其中一条比另一条长得多。 - Chris Taylor

好的，干得漂亮。我添加了一些澄清术语和通过/失败情况。谢谢。是的，对于这个练习，我会认为(0,0)到(1,1)(或稍微变化，比如[0,0]到[1,1.02])与(0,0)到(10,10)相同。 - Zando

Answer 1

您能使用坐标定义线的方程吗？如果可以，那么您可以在一个方程组中使用这两个方程，解决该方程组，并找出线是否相交以及相交的位置。如果这些线根本不相交，但它们之间的距离非常小，或者在公差范围内，则可以将它们视为一条线。

- Christopher W. Szabo

---

在交点的情况下，关键在于斜率是否不同，如果它们不同且差异足够大，那么可能会有一个else分支，如果斜率相同，则查看两点之间的距离？但是，在一个线段只是另一个线段的一小部分的情况下，应该选择哪两个点？我可以想出通过/失败的条件，但我不知道与某个矩阵操作相比，它是否有效，这将给我一个单一值来判断容差。 - Zando

Answer 2

您的问题有两个方面：您想比较长度差异和角度差异。要计算长度差异，您可以取第一条线的长度并将其除以第二条线的长度。

要计算角度差异，您可以使用atan或者我的最爱： angle = acos(abs((u点积v)/(u.长度*v.长度))) 希望这能帮到您。对之前错误的答案表示抱歉。 旧答案： 这里有一个建议：为什么不将两个线段的起始点和结束点之间的差异与其中一条线的总长度进行比较呢？然后您的差异函数会看起来像这样：

def difference(Line l1, Line l2):
    # Distance between first point on first line and first point on second line
    first_point_diff = (Line(l1.x1, l2.x1, l1.y1, l2.y1).length())

    # Distance between first point on first line and first point on second line
    second_point_diff = (Line(l1.x2, l2.x2, l1.y2, l2.y2).length())

    return (first_point_diff + second_point_diff)/l1.length()

此函数将返回两行之间的“差异”作为第一行总长度的分数。

- Richard Ye

---

我认为比较角度的想法更安全，因为可能存在y2-y1 = 0的情况。 atan2（y，x）将处理该情况。 - Andrew Morton

Answer 3

如果你只是想知道它们是否朝着同一个方向，那么你可以考虑将点积除以大小。越接近1，两条线之间的对齐度就越高。

- bigbenbt