在没有for循环的情况下，在Python中计算点数组到线段之间的欧几里得距离 [英] Calculate the euclidian distance between an array of points to a line segment in Python without for loop

问题描述

我正在寻找一个函数来计算具有两个坐标(x，y)和线段的点的numpy点数组之间的欧几里得距离.我的目标是在0.01秒内得到线段和10k点的结果.

I'm looking for a function to compute the euclidian distance between a numpy array of points with two coordinates (x, y) and a line segment. My goal is to have a result in under 0.01 sec for a line segment and 10k points.

我已经找到了单点功能.但是运行for循环效率很低.

I already found a function for a single point. But running a for loop is very inefficient.

我还发现此函数可计算到无限线的距离:

I also found this function that calculates the distance to the infinite line:

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))

这非常有效，我想对有界线也采用类似的方法.

It is very efficient and I would like to have a similar approach for a bounded line.

谢谢您的帮助.

推荐答案

设置–测试点P，端点A和B:

Setup – test point P, endpoints A and B:

• 取P - A与normalize(A - B)的点积，以从A获得带符号平行距离分量s. B和t也是如此.

• Take the dot-product of P - A with normalize(A - B) to obtain the signed parallel distance component s from A. Likewise with B and t.

取这两个数字的最大值和零，以获取钳位的平行距离分量.仅当该点在线段的边界"( Voronoi地区?)之外时，该值才会为非零.

Take the maximum of these two numbers and zero to get the clamped parallel distance component. This will only be non-zero if the point is outside the "boundary" (Voronoi region?) of the segment.

使用叉积计算出以前的垂直距离分量.

Calculate the perpendicular distance component as before, using the cross-product.

使用毕达哥拉斯计算所需的最近距离(从P到A的灰色线).

Use Pythagoras to compute the required closest distance (gray line from P to A).

以上内容是无分支的，因此易于使用numpy进行矢量化:

The above is branchless and thus easy to vectorize with numpy:

def lineseg_dists(p, a, b):

    # 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)

这篇关于在没有for循环的情况下，在Python中计算点数组到线段之间的欧几里得距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！