计算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

因此,零(PQ)是跨越与线PQ正交的二维子空间的一对基矢量.

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

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

基本上我们所做的是将矢量RS投影到与线PQ正交的2维子空间(平面)中.通过减去P(线PQ上的点)得到r和s,我们确保无限线穿过该投影平面中的原点.

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

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

线rs(v)的法线向量将为我们提供所需.由于原始空间为3维,我们已将其减少到2维,因此我们可以简单地完成.否则,我只是再次使用null.这个小技巧适用于2-d:

> 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个单位的距离.因此,对于标量v的某个值,我们可以写d n = r + v(sr).用向量(sr)形成该等式每一边的点积,并求解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 = (Q-P)'\((S - (S*N)*N') - P)'
u =
      0.95903

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

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

并且,两个线段上最近点之间的距离是

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

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

Answer 2

一种基本方法与计算两条线之间的最短距离相同,只有一个例外.

如果你查看大多数算法来找到两条线之间的最短距离,你会发现它找到每条线上最接近的点,然后计算它们之间的距离.

将其扩展为段(或光线)的技巧是查看该点是否超出该行的一个终点,如果是,则使用终点而不是无限行上的实际最近点.

有关具体示例,请参阅:

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm

进一步来说:

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm#dist3D_Segment_to_Segment()