在Python中，计算一组点到线段的欧几里得距离，无需使用for循环。

Question

我正在寻找一个函数来计算一个numpy数组中点（具有两个坐标x，y）与线段之间的欧几里得距离。我的目标是在线段和10k个点的情况下，在0.01秒内得出结果。

我已经找到了单点的函数。但是运行for循环非常低效。

我还找到了这个计算到无限线的距离的函数：

def line_dists(points, start, end):
    if np.all(start == end):
        return np.linalg.norm(points - start, axis=1)

    vec = end - start
    cross = np.cross(vec, start - points)
    return np.divide(abs(cross), np.linalg.norm(vec))

这很高效，我希望能够用类似的方法来处理一个有界线。

谢谢你的帮助。

- Jérôme

---

请分享输入数据，这样回答会更容易。 - yatu

顺便提一下，对于二维向量，你可以通过重写一个计算向量坐标直接得出范数的小函数来节省大量时间。与低维向量的直接计算相比，np.linalg.norm 的速度非常慢。同样的情况也适用于 np.cross。 - Eskapp

Answer 1

设置 - 测试点P，端点A和B：

• 使用normalize(A - B)对P - A进行点积运算，以获得从A到点P的有符号平行距离分量s。同样，对于B和t也是如此。

• 取这两个数字的最大值并将其归零，以获得夹紧的平行距离分量。只有在点在线段的“边界”（Voronoi区域？）之外时，这才是非零的。

• 像以前一样使用叉积计算垂直距离分量。

• 使用勾股定理计算所需的最近距离（从P到A的灰色线）。

以上代码是无分支的，因此可以轻松使用numpy进行矢量化：

def lineseg_dists(p, a, b):
    # Handle case where p is a single point, i.e. 1d array.
    p = np.atleast_2d(p)

    # TODO for you: consider implementing @Eskapp's suggestions
    if np.all(a == b):
        return np.linalg.norm(p - a, axis=1)

    # normalized tangent vector
    d = np.divide(b - a, np.linalg.norm(b - a))

    # signed parallel distance components
    s = np.dot(a - p, d)
    t = np.dot(p - b, d)

    # clamped parallel distance
    h = np.maximum.reduce([s, t, np.zeros(len(p))])

    # perpendicular distance component, as before
    # note that for the 3D case these will be vectors
    c = np.cross(p - a, d)

    # use hypot for Pythagoras to improve accuracy
    return np.hypot(h, c)

- meowgoesthedog

---

非常感谢您快速而详细的解决方案！这似乎按预期工作，并且对于10k个点大约需要1ms。 - Jérôme