algorithm - 计算3D中两条线(线段)之间的最短距离

Question

我有两条线段:X1,Y1,Z1 - X2,Y2,Z2 和 X3,Y3,Z3 - X4,Y4,Z4

我试图找到两个线段之间的最短距离。

几个小时以来，我一直在寻找解决方案，但所有这些解决方案似乎都适用于线而不是线段。

关于如何解决这个问题的任何想法，或任何 furmulae 的来源？

Answer 1

我会用 matlab 来回答这个问题，但也可以使用其他编程环境。我要补充一点，此解决方案可有效解决任意数量维度 (>= 3) 的问题。

假设我们在空间中有两条线段，PQ 和 RS。这里有一些随机的点集。

> P = randn(1,3)
P =
     -0.43256      -1.6656      0.12533

> Q = randn(1,3)
Q =
      0.28768      -1.1465       1.1909

> R = randn(1,3)
R =
       1.1892    -0.037633      0.32729

> S = randn(1,3)
S =
      0.17464     -0.18671      0.72579

无限直线 PQ(t) 很容易定义为

PQ(u) = P + u*(Q-P)

同样，我们有

RS(v) = R + v*(S-R)

看到对于每一行，当参数为 0 或 1 时，我们得到返回行上的原始端点之一。因此，我们知道 PQ(0) == P，PQ(1) == Q，RS(0) == R，RS(1) == S。

这种参数化定义直线的方式在许多情况下都非常有用。

接下来，假设我们沿着 PQ 线向下看。我们能找到从线段RS到无限直线PQ的距离最小的点吗？这最容易通过投影到线 PQ 的零空间来完成。

> N = null(P-Q)
N =
     -0.37428     -0.76828
       0.9078     -0.18927
     -0.18927      0.61149

因此，null(P-Q) 是一对跨越与直线 PQ 正交的二维子空间的基向量。

> r = (R-P)*N
r =
      0.83265      -1.4306

> s = (S-P)*N
s =
       1.0016     -0.37923

本质上，我们所做的是将向量 RS 投影到与直线 PQ 正交的二维子空间(平面)中。通过减去 P(直线 PQ 上的一个点)得到 r 和 s，我们确保无限直线通过该投影平面中的原点。

实际上，我们已经将其简化为找到投影平面中从线 rs(v) 到原点 (0,0) 的最小距离。回想一下，rs(v) 行由参数 v 定义为:

rs(v) = r + v*(s-r)

线 rs(v) 的法向量将为我们提供我们所需要的。由于原始空间是 3 维的，因此我们已将其降低为 2 维，因此我们可以简单地做到这一点。否则，我只会再次使用 null。这个小技巧适用于二维:

> n = (s - r)*[0 -1;1 0];
> n = n/norm(n);

n 现在是一个具有单位长度的向量。无限直线rs(v)到原点的距离很简单。

> d = dot(n,r)
d =
       1.0491

看到我也可以使用 s 来获得相同的距离。实际距离是 abs(d)，但事实证明，这里的 d 无论如何都是正的。

> d = dot(n,s)
d =
       1.0491

我们可以由此确定v吗？是的。回想一下，原点距离连接点 r 和 s 的直线有 d 个单位的距离。因此我们可以写 dn = r + v(s-r)，对于标量 v 的某个值。用向量 (s-r) 形成这个等式每边的点积，并求解 v .

> v = dot(s-r,d*n-r)/dot(s-r,s-r)
v =
       1.2024

这告诉我们，线段 rs 最接近原点的位置发生在线段端点之外。所以实际上 rs 上离原点最近的点是点 rs(1) = s。

从投影中退出，这告诉我们线段 RS 上离无限直线 PQ 最近的点是点 S。

分析中还有一步要走。线段 PQ 上最近的点是什么？这个点是落在线段内，还是落在端点之外？

我们将点 S 投影到直线 PQ 上。 (u 的这个表达式很容易从与我之前所做的类似逻辑中导出。请注意，这里我使用\来完成这项工作。)

> u = (Q-P)'\((S - (S*N)*N') - P)'
u =
      0.95903

看到 u 位于区间 [0,1] 内。我们已经解决了这个问题。 PQ线上的点是

> P + u*(Q-P)
ans =
      0.25817      -1.1677       1.1473

并且，两条线段上最近点之间的距离为

> norm(P + u*(Q-P) - S)
ans =
        1.071

当然，所有这些都可以压缩成短短的几行代码。但它有助于将其全部扩展以了解其工作原理。