如何在 3d space 中找到线段中的最近点

Question

我正在解决一个听起来像这样的算法问题：

Given a three-dimensional space and segments in it. Find the point with minimal distance to all of the segments. Example input: in the first line N - the number of segments, in the N next lines given the begin and the end of each segment: x1 y1 z1 x2 y2 z2

我知道给定问题的类型（几何中位数）并且我已经知道如何找到点和线段之间的最小距离（Cartesian distance and a nice code provided ），但我需要的是一个点(x, y, z) 在我找到距离的线段上。我需要知道它来近似我的结果。

这是我的代码

# finds distance between point and segment
def lineseg_dist(p, a, b):
    d = np.divide(b - a, np.linalg.norm(b - a))
    s = np.dot(a - p, d)
    t = np.dot(p - b, d)
    h = np.maximum.reduce([s, t, 0])
    c = np.cross(p - a, d)
    return np.hypot(h, np.linalg.norm(c))

#segment 
seg = [[1, 1, 1], [2, 2, 2]]
lineseg_dist([0, 0, 0], np.array(seg[0]), np.array(seg[1])) #1.73205

例如，从 [0, 0, 0] 点到线段的距离是已知的，我们可以说线段离我们最近的点是 [1, 1, 1]。但是在其他情况下我们如何找到最近的点呢？

Answer 1

从你的最后一段我了解到你需要在一个线段中找到一个最接近另一个点的点。

这个函数returns最近点和距离：

def closest_point_and_distance(p, a, b):
    s = b - a
    w = p - a
    ps = np.dot(w, s)
    if ps <= 0:
        return a, np.linalg.norm(w)
    l2 = np.dot(s, s)
    if ps >= l2:
        closest = b
    else:
        closest = a + ps / l2 * s
    return closest, np.linalg.norm(p - closest)

它也比您拥有的代码更快。

如何在 3d space 中找到线段中的最近点

How to find nearest point in segment in a 3d space

python

algorithm

geometry

numpy