在三维空间中，点与直线之间的最短距离

Question

我正在尝试使用numpy或其他Python库找到从点（x0，y0，z0）到由（x1，y1，z1）和（x2，y2，z2）连接的线的最小距离。不幸的是，我在网络上找到的所有内容都与二维空间有关，而我对Python还比较新。任何帮助将不胜感激。提前致谢！

- hello_lel

---

一旦你有一个二维的例子，你只需要再做一次。 - hardillb

Answer 1

由于StackOverflow不支持LaTeX，因此我将略过一些数学内容。一个解决方案来自这样的想法：如果你的线跨越了点p和q，那么该线上的每个点都可以表示为t*(p-q)+q，其中t是一些实数值。然后，您要最小化给定点r与该线上任何一点之间的距离，并且距离恰好是单变量t的函数，因此标准的微积分技巧非常有效。请考虑以下示例，计算r与由p和q跨越的线之间的最小距离。我们手动计算知道答案应该是1。

import numpy as np

p = np.array([0, 0, 0])
q = np.array([0, 0, 1])
r = np.array([0, 1, 1])

def t(p, q, r):
    x = p-q
    return np.dot(r-q, x)/np.dot(x, x)

def d(p, q, r):
    return np.linalg.norm(t(p, q, r)*(p-q)+q-r)

print(d(p, q, r))
# Prints 1.0

这在任意维度中都可以正常工作，包括2、3和10亿。唯一的真正限制是p和q必须是不同的点，以便它们之间有一条唯一的直线。

我在上面的示例中将代码分解为两个不同的步骤，以展示从我数学思考方式中产生的两个步骤（找到t，然后计算距离）。这不一定是最有效的方法，特别是如果您想要知道对于同一条线的各种点和最小距离 - 尤其是如果维数较小。对于更有效的方法，请考虑以下内容：

import numpy as np

p = np.array([0, 0, 0])  # p and q can have shape (n,) for any
q = np.array([0, 0, 1])  # n>0, and rs can have shape (m,n)
rs = np.array([          # for any m,n>0.
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 1],
    [0, 2, 1],
])

def d(p, q, rs):
    x = p-q
    return np.linalg.norm(
        np.outer(np.dot(rs-q, x)/np.dot(x, x), x)+q-rs,
        axis=1)

print(d(p, q, rs))
# Prints array([1.        , 1.        , 1.41421356, 2.        ])

我可能会遗漏一些简化或其他可以加快速度的事情，但至少这应该是一个很好的开始。

- Hans Musgrave

---

你有一种天赋，就是善于把事情复杂化。 - Evgeny

@EvgenyPogrebnyak 对不起，我应该改什么？ - Hans Musgrave

也许，可以给一些提示，d()和t()分别是做什么的以及为什么要这样做？ - Evgeny

我本来想说那是一个非常简洁明了的答案。 - John Powell

将复杂的事情变得简单，实属一种才能。 - matanster

Answer 2

这个方案与@Hans Musgrave的解决方案重复，但是想象一下我们对“标准微积分技巧”一无所知，并且在线性代数上也非常糟糕。

我们所知道的只有：

1. 如何计算两点之间的距离
2. 线上的一个点可以表示为两个点和参数的函数
3. 如何找到函数的最小值

（列表不适用于代码块）

def distance(a, b):
    """Calculate a distance between two points."""
    return np.linalg.norm(a-b)

def line_to_point_distance(p, q, r):
    """Calculate a distance between point r and a line crossing p and q."""
    def foo(t: float):
        # x is point on line, depends on t 
        x = t * (p-q) + q
        # we return a distance, which also depends on t        
        return distance(x, r)
    # which t minimizes distance?
    t0 = sci.optimize.minimize(foo, 0.1).x[0]
    return foo(t0)

# in this example the distance is 5
p = np.array([0, 0, 0])
q = np.array([2, 0, 0])
r = np.array([1, 5, 0])

assert abs(line_to_point_distance(p, q, r) - 5) < 0.00001 

你不应该在实际计算中使用这种方法，因为它使用近似值来代替已知的解析式，但也许可以帮助揭示一些邻近答案背后的逻辑。

- Evgeny