4

由于浮点精度，我在确定两条线段是否共线时遇到了一些麻烦。如何确定线段是否共线并具有一定的公差？

4

4 回答 4

3

编辑：

如果线段包含两个相同的点，则它们是共线的。如果它们共享一个点并且几乎平行，则它们几乎是共线的。

如果向量之间的角度小于您声明的阈值，则向量实际上是平行的。可能小于 0.000027 度，即十分之一度秒的十进制等值（以纬度距离表示，相当于赤道处的经度距离，相差约 10 英尺；这大约是民用 GPS 的精度）。

您没有告诉我们您使用的是什么语言或库；在 .NET 的 System.Windows.Media.3D 库中有一个 Vector3D 结构，它有一个 AngleBetween() 方法，使这个检查成为一个单行。

“基本”数学（它实际上是向量三角函数，而不是大多数定义的“基本”概念）是 θ=cos -1 ( A*B / |A||B| ); 即，两个向量的标量积除以它们的大小的乘积的反余弦值。

向量 A 和向量 B 的点积（均包含 X、Y 和 Z）为 X A X B + Y A Y B + Z A Z B。向量 A 的大小为 sqrt(X A 2 + Y A 2 + Z A 2 )。

因此，在伪 C-ish 中：

//Vector is a simple immutable class or struct containing integer X, Y and Z components
public bool CloseEnough(Vector a, Vector b, decimal threshold = 0.000027m)
{
   int dotProduct = a.X*b.X + a.Y*b.Y + a.Z*b.Z;
   decimal magA = sqrt(a.X*a.X + a.Y*a.Y + a.Z*a.Z); //sub your own sqrt
   decimal magB = sqrt(b.X*b.X + b.Y*b.Y + b.Z*b.Z); //sub your own sqrt

   decimal angle = acos(dotProduct/(magA*magB)); //sub your own arc-cosine

   if(angle <= threshold
}
于 2012-04-10T22:18:30.923 回答
3

如果两个段接近共线，我需要知道我的应用程序。这是关于从激光扫描中提取线条。我将解释我正在使用的解决方案。它工作得很好。（原谅我的英语！）

我认为KeithS提出的近似共线性的条件是错误的。

如果它们共享一个点并且几乎平行，则它们几乎是共线的。

如果两条线段（或线）平行但很接近，我们可以认为它们接近共线。

我的解决方案在于使用线条的极坐标表示。

y * sin(theta) = rho - x * cos(theta)

通过这种表示，可以使用 theta 和 rho 将一条线表示为一个点。诀窍是，如果这些“点”很近，那么这些线几乎是共线的。您只需要计算欧几里德距离并使用阈值来确定它们是否接近共线。

于 2015-01-07T01:41:40.947 回答
3

根据您对“几乎共线”的定义，几种解决方案似乎是合理的。

通过 4 个点拟合一条线

两条线段由 4 个点定义，您可以通过两条线段的起点和终点拟合一条线。

您可以使用 SVD 通过 4 个点获得一条线的最小二乘拟合，类似于此答案：https ://stackoverflow.com/a/2333251/5069869

使用这种方法，您可以考虑线段的方向以及第一条线段的末端和第二条线段的起点之间的偏移量。

但是，如果两条线段平行但不共线，并且相对于它们之间的距离较短，则拟合线将垂直于两条线段。这对于单元测试来说没有问题，你喜欢“几乎共线到零后面的几个数字”，但对于其他应用程序，这可能是一个问题。

独立使用平均方向和平均位置

或者，您可以使用两条线段的平均方向作为目标线的方向来构造目标线。(v1/|v1|+v2/|v2|)/2如果向量v1和v2指向相同的方向， Tuis 可以通过 计算。然后使用 4 个点的平均值作为目标线的锚点。

最后，您可以计算 4 个点到目标线的各个距离，并将它们用作共线性的度量。

段的长度和段之间的空间的影响

当您找到“几乎共线”的合适定义时，您需要考虑不同长度的线段如何影响结果，正如 Vahid 在评论中指出的那样。此外，您应该考虑两条线段之间的空间的影响。

通过计算 4 个点到目标线的距离，我试图减少不同段长度的影响（每个段只贡献 2 个点），但我不能完全消除它

于 2017-08-22T12:14:17.250 回答
0

我认为，如果两条线近似共线，则应满足以下条件：

  1. 两条线的夹角小于一个阈值
  2. 一个点到两条线段的距离小于一个阈值

我的解决方案：

import math
import numpy as np

def line_to_angle(line, use_abs=True):
    x1, y1, x2, y2 = line[:4]
    if abs(x2 - x1) <= 0.0000001:
        angle_val = 90 if y2 > y1 else -90
    else:
        angle_val = np.degrees(math.atan((y2 - y1) / (x2 - x1)))
    if use_abs:
        angle_val = abs(angle_val)
    return angle_val


def distance_line_point(p, line):
    p1 = np.array(p)
    p2, p3 = np.array(line[:2]), np.array(line[2:4])
    return np.abs(np.cross(p2-p1, p1-p3) / np.linalg.norm(p2-p1))


def near_collinear(linea, lineb, angle_thres=1.5, distance_thres=5):
    pointa = ((linea[0] + lineb[0]) / 2, (linea[1] + lineb[1]) / 2)
    pointb = ((linea[2] + lineb[2]) / 2, (linea[3] + lineb[3]) / 2)
    mid_angle = line_to_angle([*pointa, *pointb], use_abs=False)
    angle_a, angle_b = line_to_angle(linea, use_abs=False), line_to_angle(lineb, use_abs=False)
    angle_diff_a, angle_diff_b = abs(angle_a - mid_angle), abs(angle_b - mid_angle)
    angle_diff_a = min(angle_diff_a, 180 - angle_diff_a)
    angle_diff_b = min(angle_diff_b, 180 - angle_diff_b)
    if angle_diff_a > angle_thres or angle_diff_b > angle_thres:
        return False
    mid_point = ((pointa[0] + pointb[0]) / 2, (pointa[1] + pointb[1]) / 2)
    distance_a = distance_line_point(mid_point, linea)
    distance_b = distance_line_point(mid_point, lineb)
    if distance_a > distance_thres or distance_b > distance_thres:
        return False
    return True
于 2021-06-11T08:01:22.280 回答