浏览量:88

3.4. 线性对象间的距离

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

3.4. 线性对象间的距离

三维空间下的线性对象间才有距离的概念,三种线性对象中线段可以看成是最特殊的,而Eberly[2]对三维线段与线段的距离计算作了详细的论证。本章节首先分析不同线性对象之间最小距离计算的数学原理,然后分别介绍各种线性对象之间距离计算的方法。

3.4.1. 线性对象间距离的数学原理

线性对象可以表示为\(L(s) = P + s\vec d\),直线、射线和线段之间的差别就在于\(s\)的取值范围,例如,若\(L(s)\)表示直线,则\(s \in ( - \infty , + \infty )\);若\(L(s)\)表示射线,则\(s \in [0, + \infty )\);若\(L(s)\)表示线段,则\(s \in [0,1]\)

2015-3-22 16-03-44

图3.6 两条直线性对象之间的距离

设有两条线性对象\({L_0}(s) = {P_0} + s{\vec d_0}\)\({L_1}(t) = {P_1} + t{\vec d_1}\)\({Q_0}\)在线性对象\({L_0}(s)\)上,\({Q_1}\)在线性对象\({L_1}(t)\)上,如图3.6所示,\({Q_0}\)\({Q_1}\)之间距离的平方,可以用函数\(f(s,t)\)来表示:

\[f(s,t) = {\left\| {{Q_0} - {Q_1}} \right\|^2} = \left[ {({P_0} - {P_1}) + (s{{\vec d}_0} - t{{\vec d}_1})} \right] \cdot \left[ {({P_0} - {P_1}) + (s{{\vec d}_0} - t{{\vec d}_1})} \right] \tag{3.19}\]

2015-3-22 16-03-58

图3.7 \(f(s,t)\)的二次函数的三维空间形状

2015-3-22 16-04-10

图3.8 二次函数的阶层曲线

它是一个关于\(s\)\(t\)的二次函数,形状是一个抛物面,如图3.7所示,从上往下看,函数示意图相当于由中心,向外部扩展的一个个椭圆,称每个椭圆是二次函数的一个阶层曲线,同一个椭圆有相同的阶层值,所谓的阶层值就是指\(f(s,t)\)的值,即线性对象之间距离的平方,越靠外的椭圆的阶层值越大,图3.8表示出了抛物面的阶层曲线。该抛物面中心点,就是极值点,极值点处的阶层值最小。

由微积分的知识可知,可以对\(f(s,t)\)\(s\)\(t\)的偏导数,令偏导数等于0,求出的解就是极值点,设极值点是\(({s_c},{t_c})\),等式表示为:

\(\begin{array}{l}\frac{{\partial f(s,t)}}{{\partial s}} = 2\left[ {({P_0} - {P_1}) + (s{{\vec d}_0} - t{{\vec d}_1})} \right] \cdot {{\vec d}_0} = 0\\\frac{{\partial f(s,t)}}{{\partial t}} = 2\left[ {({P_0} - {P_1}) + (s{{\vec d}_0} - t{{\vec d}_1})} \right] \cdot {{\vec d}_1} = 0\end{array} \tag{3.20}\)

\(a = {\vec d_0} \cdot {\vec d_0},b = {\vec d_0} \cdot {\vec d_1},c = {\vec d_1} \cdot {\vec d_1},d = {\vec d_0} \cdot ({P_0} - {P_1}),e = {\vec d_1} \cdot ({P_0} - {P_1})\),若\(ac - {b^2} = 0\)表示两条线性对象平行,无解;否则,极值点\(({s_c},{t_c})\)表示为:

\[{s_c} = \frac{{be - cd}}{{ac - {b^2}}},{t_c} = \frac{{ae - bd}}{{ac - {b^2}}} \tag{3.21}\]

在直线与直线的距离计算中,由于对\(s\)\(t\),没有限制,所以求出的极值点就是距离最小的两个点。但是在涉及射线与线段的距离计算中,则需要考虑到对参数\(s\)\(t\)的限制。这里只讨论最复杂的一种情况,就是线段与线段的距离计算,其它类型线性对象间的距离计算原理相同。

设两条线段分别是\({L_0}(s) = {P_0} + s{\vec d_0},s \in [0,1]\)\({L_1}(t) = {P_1} + t{\vec d_1},t \in [0,1]\),则线段\({L_0}(s)\)上的两个端点分别是\({P_0}\)\({P_0} + {\vec d_0}\),线段\({L_1}(s)\)上的两个端点分别是\({P_1}\)\({P_1} + {\vec d_1}\)。它们之间距离的计算分为两种情况:平行和不平行。

情况一 不平行的线段之间的距离

\(ac - {b^2} \ne 0\)时,两条线段不平行,可以使用等式(3.21)算出极值点\(({s_c},{t_c})\),若极值点满足条件\(({s_c},{t_c}) \in {[0,1]^2}\),则它们就是所要找的最小距离的位置;若它们不满足条件,如图3.9所示,就得根据极值点落在的不同的区域进行不同的处理。

2015-3-22 16-04-20

图3.9 轴\(s = 0,s = 1,t = 0,t = 1\)把s-t平面分成9个区域[2]

若极值点落在区域1中,一种直观地显示具有最小距离的点出现在边界何处的方法是:将二次函数\(f(s,t)\)的抛物面与平面\(s = 1\)相交,相交得到的曲线是一条抛物线,其图形函数是\(F(t) = f(1,t),t \in [0,1]\),现在就将问题简化为了在一维上求函数\(F(t)\)的最小值问题。若\(F(t)\)的最小值出现在\([0,1]\)上,那么该点一定满足\(F'(t) = f'(1,t) = 0\),或者出现在\(t = 0\)或者\(t = 1\)上。图3.10,显示了最小值出现在\([0,1]\)的情况,存在一条阶层曲线(椭圆形状)与直线\(s = 1\)相切。在位于端点的情形中,即端点\((1,0)\)和端点\((1,1)\),阶层曲线通过端点,但并不一定是相切的。

2015-3-22 16-04-30

图3.10 极值点在区域1时,几种不同的阶层曲线[2]

现在讨论下,什么情况位于\([0,1]\)区间上,什么情况位于端点。\(t\)轴上的区间\([0,1]\)可以把直线分成三段:\(( - \infty ,0),[0,1],(1, + \infty )\)。令\(F'(t) = f'(1,t) = 0\),解得\(t = \bar t\)。若\(\bar t \prec 0\),则\(F(t)\)\([0,1]\)区间上是一个递增函数,则\(f(s,t)\)最小值取\(({s_{\min }},{t_{\min }}) = (1,0)\);若\(\bar t \succ 1\),则\(F(t)\)\([0,1]\)区间上是一个递减函数,则\(f(s,t)\)最小值取\(({s_{\min }},{t_{\min }}) = (1,1)\);若\(0 \le \bar t \le 1\),则\(F(t)\)\(\bar t\)处取得最小值,则\(f(s,t)\)最小值取\(({s_{\min }},{t_{\min }}) = (1,\bar t)\),这就是图3.10所示的相切的情况。

极值点位于区域3、5或者7内的处理方法与极值点出现在区域1内的相似,不再赘述。

若极值点落在区域2上,那么\(f(s,t)\)的阶层曲线与单位正方形的第一个接触点可能出现在轴线\(s = 1\)或者轴线\(t = 1\)上。设\(\partial f/ds = {f_s}'(s,t)\)\(\partial f/dt = {f_t}'(s,t)\)分别表示二次函数\(f(s,t)\)\(s\)\(t\)方向上的偏导数,如果\(({d_x},{d_y}) \cdot \left( {{f_s}'(s,t),{f_t}'(s,t)} \right) \succ 0\),则函数\(f(s,t)\)在位置\((s,t)\),沿着\(({d_x},{d_y})\)方向上是递增的,如果\(({d_x},{d_y}) \cdot \left( {{f_s}'(s,t),{f_t}'(s,t)} \right) \prec 0\),则函数\(f(s,t)\)在位置\((s,t)\),沿着\(({d_x},{d_y})\)方向上是递减的。由于极值点落在区域2上,第一个与正方形相切的阶层曲线,只能在轴线\(s = 1\)或者轴线\(t = 1\)上,所以函数\(f(s,t)\)在位置\((1,1)\)上,方向是\((1,1)\)和方向\((1,0)\)上的偏微分不可能都是负数,即\((0,1) \cdot \left( {{f_s}'(1,1),{f_t}'(1,1)} \right) = {f_t}'(1,1)\)\((1,0) \cdot \left( {{f_s}'(1,1),{f_t}'(1,1)} \right) = {f_s}'(1,1)\)不可能都是负数。若\({f_s}'(1,1) > 0\),最小值出现在\(t = 1\)的轴线上,因为对于所有\(s \prec 1\),有\(f(s,1) < f(1,1)\);类似的,如果\({f_t}'(1,1) > 0\),最小值将出现在\(s = 1\)的轴线上。

极值点位于区域4、6或者8内的处理方法与极值点出现在区域2内的相似,不再赘述。

情况二 平行的线段之间的距离

\(ac - {b^2} = 0\)时,两条线段互相平行。如图3.11所示,把线段\({L_1}(t)\)上的端点\({P_1}\)投影到经过线段\({L_0}(t)\)的直线上,可以表示为

\[{P_1} = {P_0} + {\sigma _0}{\vec d_0} + {r_1}\vec n \tag{3.22}\]

其中\(\vec n\)与直线的方向\({\vec d_0}\)互相垂直,等式两边都点积上\({\vec d_0}\),可以解得系数\({\sigma _0}\)

\[{\sigma _0} = \frac{{\left( {{P_1} - {P_0}} \right) \cdot {{\vec d}_0}}}{{{{\vec d}_0} \cdot {{\vec d}_0}}} \tag{3.23}\]

把线段\({L_1}(t)\)上的另一个端点\({P_1} + {\vec d_1}\)投影到线段\({L_0}(t)\)所在的直线上,可以表示为

\[{P_1} + {\vec d_1} = {P_0} + {\sigma _1}{\vec d_0} + {r_2}\vec n \tag{3.24}\]

等式两边都点积上\({\vec d_0}\),可以解得

\[{\sigma _1} = \frac{{\left( {{P_1} - {P_0}} \right) \cdot {{\vec d}_0} + {{\vec d}_1} \cdot {{\vec d}_0}}}{{{{\vec d}_0} \cdot {{\vec d}_0}}} \tag{3.25}\]

2015-3-22 16-04-43

图3.11 把线段\({L_1}(t)\)上的端点投影到包含线段\({L_0}(t)\)的直线上

现在的问题就简化为确定区间\([\min ({\sigma _0},{\sigma _1}),\max ({\sigma _0},{\sigma _1})]\)和区间\([0,1]\)的关系。如果两个区间无重叠区域,则最小距离出现在两条三维线段的端点上,设\({\sigma _0} \prec {\sigma _1}\),若\({\sigma _1} \prec 0\),则距离最近的两个端点是\({P_0}\)\({P_1} + {\vec d_1}\),若\({\sigma _1} \succ 1\),则距离最近的两个端点是\({P_0} + {\vec d_0}\)\({P_1}\);如果两个区间重叠,那么存在许多的点对,在这些点对上具有最小距离,如图3.11所示,则可以取点对\({P_0} + {\sigma _0}{\vec d_0}\)\({P_1}\)之间的距离。

 

3.4.2. 直线与直线的距离

直线与直线之间距离的计算是最简单的情况,该算法伪码表示为:

计算直线\({L_0}(s) = {P_0} + s{\vec d_0}\)\({L_1}(t) = {P_1} + t{\vec d_1}\)之间的最小距离,其中\(s,t \in \left( { - \infty , + \infty } \right)\)
return (距离)
1.    \(a = {\vec d_0} \cdot {\vec d_0},b = {\vec d_0} \cdot {\vec d_1},c = {\vec d_1} \cdot {\vec d_1},d = {\vec d_0} \cdot ({P_0} - {P_1}),e = {\vec d_1} \cdot ({P_0} - {P_1})\)
2.    \(\Delta = ac - {b^2}\)
3.    if \(\Delta = = 0\),then
4.           取\(s = 0\),得\(t = d/b\)\(t = e/c\)(或取\(t = 0\),计算出\(s = - e/b\)\(s = - d/a\));
5.    else
6.           \(s = \left( {be - cd} \right)/\Delta \)\(t = \left( {ae - bd} \right)/\Delta \)
7.    end if;
8.    \(s\)\(t\)的值代入线性对象的参数方程,计算出距离最近的点\({Q_0}\)\({Q_1}\);
9.    return\(\left\| {{Q_0} - {Q_1}} \right\|\);

3.4.3. 线段与线段的距离

Eberly[2](1999)采用分区域的方法,解决了计算线段与线段之间距离的问题,但是它提出的方法,实现起来比较麻烦,需要把平面分成9个区域,不同的区域按照不同的方法来计算,Eberly也在它的文章中,提供了详细的伪码表述。Schneider et al[3](2002)描述了另外一种更为简单的实现方法,它依据上面的数学原理,通过重复的判定\(s\)\(t\)限定条件,来最终确定最小距离点,下面将分别介绍由Schneider描述的,各种线性对象之间距离计算的算法。

线段与线段之间距离的计算,算法的伪码如下所示:

计算线段\({L_0}(s) = {P_0} + s{\vec d_0}\)\({L_1}(t) = {P_1} + t{\vec d_1}\)之间的最小距离,线段\({L_0}(s)\)的两个端点是\({P_0}\)\({P_0} + {\vec d_0}\),线段\({L_1}(t)\)\({P_1}\)\({P_1} + {\vec d_1}\),其中\(s \in \left[ {0,1} \right],t \in \left[ {0,1} \right]\)
return (距离)
1.    \(a = {\vec d_0} \cdot {\vec d_0},b = {\vec d_0} \cdot {\vec d_1},c = {\vec d_1} \cdot {\vec d_1},d = {\vec d_0} \cdot ({P_0} - {P_1}),e = {\vec d_1} \cdot ({P_0} - {P_1})\)
2.    \(\Delta = ac - {b^2}\)
3.    \({t_{den}} = {s_{den}} = \Delta \);
4.    if\(\Delta = = 0\),then
5.           \({t_{num}} = 0,{s_{num}} = - e,{s_{den}} = b\)\({t_{num}} = 0,{s_{num}} = - d,{s_{den}} = a\)\({s_{num}} = 0,{t_{num}} = d,{t_{den}} = b\)\({s_{num}} = 0,{t_{num}} = e,{t_{den}} = c\));
6.    else
7.           \({s_{num}} = be - cd,{t_{num}} = ae - bd\);
8.    end if ;
9.    if\({s_{num}} \prec 0\),then
10.          \({s_{num}} = 0,{t_{num}} = d,{t_{den}} = b\)(或\({s_{num}} = 0,{t_{num}} = e,{t_{den}} = c\));
11.   else if \({s_{num}} \succ {s_{den}}\), then
12.          \({s_{num}} = {s_{den}},{t_{num}} = \left( {a + d} \right),{t_{den}} = b\) (或\({s_{num}} = {s_{den}},{t_{num}} = \left( {b + e} \right),{t_{den}} = c\));
13.   end if;
14.   if\({t_{num}} \prec 0\), then
15.          \({t_{num}} = 0,{s_{num}} = - d,{s_{den}} = a\)(或\({t_{num}} = 0,{s_{num}} = - e,{s_{den}} = b\));
16.          if \({s_{num}} \prec 0\), then
17.                 \({s_{num}} = 0\);
18.          else if \({s_{num}} \succ {s_{den}}\) , then
19.                 \({s_{num}} = {s_{den}} = 1\);
20.          end if;
21.   else if\({t_{num}} \succ {t_{den}}\), then
22.          \({t_{num}} = {t_{den}},{s_{num}} = \left( {c - e} \right),{s_{den}} = b\) (或\({t_{num}} = {t_{den}},{s_{num}} = \left( {b - d} \right),{s_{den}} = a\));
23.          if \({s_{num}} \prec 0\), then
24.                 \({s_{num}} = 0\);
25.          if \({s_{num}} \succ {s_{den}}\), then
26.                 \({s_{num}} = {s_{den}} = 1\);
27.          end if;
28. end if;
29.   \(t = s = 0\);
30.   if \({s_{den}} \ne 0\), then
31.          \(s = {s_{num}}/{s_{den}}\);
32.   end if;
33.   if \({t_{den}} \ne 0\), then
34.          \(t = {t_{num}}/{t_{den}}\);
35.   end if;
36.   \(s\)\(t\)的值代入线性对象的参数方程,计算出距离最近的点\({Q_0}\)\({Q_1}\);
37.   return\(\left\| {{Q_0} - {Q_1}} \right\|\);

如图3.9所示,如果点\(({s_c},{t_c})\)在区域0中,算法第9~28步,if测试全部失效,\(({s_c},{t_c})\)就最小距离点对;如果\({s_c} \prec 0\),则点\(({s_c},{t_c})\)可能在区域4、5、6,那么最近距离的\((s,t)\)必然在\(s = 0\),\(t = 0\),\(t = 1\)上,算法第9~13步,令\(s = 0\),计算出\(t\)值,若\(0 \le t \le 1\),则最小距离点对就是\(\left( {0,t} \right)\),若\(t \prec 0\),则最小距离点对在\(t = 0\)上,算法第14~28步,计算出点对\((s,t)\),相反,若\(t \succ 0\),则最小距离点对在\(t = 1\),然后计算出点对\((s,t)\)。通过重复判定\((s,t)\)的限定条件,求出最小距离的点对\((s,t)\)。 同理,对于两条线段平行的情况下,也可以通过这种方法来得出最小距离点对。

3.4.4. 直线与射线的距离

直线与射线之间距离的计算,需要增加对射线条件的判断,算法的伪码表示为:

计算直线\({L_0}(s) = {P_0} + s{\vec d_0}\)和射线\({L_1}(t) = {P_1} + t{\vec d_1}\)间的最小距离,其中\(s \in \left( { - \infty , + \infty } \right),t \in \left[ {0, + \infty } \right)\)
return (距离)
1.    \(a = {\vec d_0} \cdot {\vec d_0},b = {\vec d_0} \cdot {\vec d_1},c = {\vec d_1} \cdot {\vec d_1},d = {\vec d_0} \cdot ({P_0} - {P_1}),e = {\vec d_1} \cdot ({P_0} - {P_1})\)
2.    \(\Delta = ac - {b^2}\)
3.    \({t_{den}} = {s_{den}} = \Delta \);
4.    if \(ac - {b^2} = = 0\),then
5.           \({t_{num}} = 0,{s_{num}} = - e,{s_{den}} = b\)(或\({t_{num}} = 0,{s_{num}} = - d,{s_{den}} = a\)\({s_{num}} = 0,{t_{num}} = d,{t_{den}} = b\)\({s_{num}} = 0,{t_{num}} = e,{t_{den}} = c\));
7.    else
8.           \({s_{num}} = be - cd,{t_{num}} = ae - bd\);
9.    end if;
10.   if \({t_{num}} \prec 0\),then
11.          \({t_{num}} = 0,{s_{num}} = - d,{s_{den}} = a\) (或\({t_{num}} = 0,{s_{num}} = - e,{s_{den}} = b\));
12.   end if;
13.   \(t = s = 0\);
14.   if \({s_{den}} \ne 0\), then
15.          \(s = {s_{num}}/{s_{den}}\);
16.   end if;
17.   if \({t_{den}} \ne 0\), then
18.          \(t = {t_{num}}/{t_{den}}\);
19.   end if;
20.   \(s\)\(t\)的值代入线性对象的参数方程,计算出距离最近的点\({Q_0}\)\({Q_1}\);
21.   return \(\left\| {{Q_0} - {Q_1}} \right\|\);

3.4.5. 直线与线段的距离

直线与线段之间距离的计算,算法的伪码如下所示:

计算直线\({L_0}(s) = {P_0} + s{\vec d_0}\)和线段\({L_1}(t) = {P_1} + t{\vec d_1}\)之间的最小距离,则线段的两个端点是\({P_1}\)\({P_1} + {\vec d_1}\),其中\(s \in \left( { - \infty , + \infty } \right),t \in \left[ {0,1} \right]\)
return (距离)
1.    \(a = {\vec d_0} \cdot {\vec d_0},b = {\vec d_0} \cdot {\vec d_1},c = {\vec d_1} \cdot {\vec d_1},d = {\vec d_0} \cdot ({P_0} - {P_1}),e = {\vec d_1} \cdot ({P_0} - {P_1})\)
2.    \(\Delta = ac - {b^2}\)
3.    \({t_{den}} = {s_{den}} = \Delta \);
4.    if \(\Delta = = 0\),then
5.           \({t_{num}} = 0,{s_{num}} = - e,{s_{den}} = b\)(或\({t_{num}} = 0,{s_{num}} = - d,{s_{den}} = a\)\({s_{num}} = 0,{t_{num}} = d,{t_{den}} = b\)\({s_{num}} = 0,{t_{num}} = e,{t_{den}} = c\));
6.    else
7.           \({s_{num}} = be - cd,{t_{num}} = ae - bd\);
8.    end if;
9.    if \({t_{num}} \prec 0\),then
10.          \({t_{num}} = 0,{s_{num}} = - d,{s_{den}} = a\) (或\({t_{num}} = 0,{s_{num}} = - e,{s_{den}} = b\));
11.   else if \({t_{num}} \succ {t_{den}}\), then
12.          \({t_{num}} = {t_{den}},{s_{num}} = \left( {c - e} \right),{s_{den}} = b\) (或\({t_{num}} = {t_{den}},{s_{num}} = \left( {b - d} \right),{s_{den}} = a\));
13.   end if;
14.   \(t = s = 0\);
15.   if \({s_{den}} \ne 0\), then
16.          \(s = {s_{num}}/{s_{den}}\);
17.   end if;
18.   if \({t_{den}} \ne 0\), then
19.          \(t = {t_{num}}/{t_{den}}\);
20.   end if;
21.   \(s\)\(t\)的值代入线性对象的参数方程,计算出距离最近的点\({Q_0}\)\({Q_1}\);
22.   return \(\left\| {{Q_0} - {Q_1}} \right\|\);

3.4.6. 射线与射线的距离

射线与射线之间距离的计算,算法的伪码如下所示:

计算射线\({L_0}(s) = {P_0} + s{\vec d_0}\)和射线\({L_1}(t) = {P_1} + t{\vec d_1}\)之间的最小距离,其中\(s,t \in \left[ {0, + \infty } \right)\)
return (距离)
1.    \(a = {\vec d_0} \cdot {\vec d_0},b = {\vec d_0} \cdot {\vec d_1},c = {\vec d_1} \cdot {\vec d_1},d = {\vec d_0} \cdot ({P_0} - {P_1}),e = {\vec d_1} \cdot ({P_0} - {P_1})\)
2.    \(\Delta = ac - {b^2}\)
3.    \({t_{den}} = {s_{den}} = \Delta \);
4.    if \(\Delta = = 0\),then
5.           \({t_{num}} = 0,{s_{num}} = - e,{s_{den}} = b\)(或\({t_{num}} = 0,{s_{num}} = - d,{s_{den}} = a\)\({s_{num}} = 0,{t_{num}} = d,{t_{den}} = b\)\({s_{num}} = 0,{t_{num}} = e,{t_{den}} = c\));
6.    else
7.           \({s_{num}} = be - cd,{t_{num}} = ae - bd\);
8.    end if;
9.    if \({s_{num}} \prec 0\),then
10.          \({s_{num}} = 0,{t_{num}} = d,{t_{den}} = b\)(或\({s_{num}} = 0,{t_{num}} = e,{t_{den}} = c\));
11.   end if;
12.   if\({t_{num}} \prec 0\), then
13.          \({t_{num}} = 0,{s_{num}} = - d,{s_{den}} = a\) (或\({t_{num}} = 0,{s_{num}} = - e,{s_{den}} = b\));
14.          if \({s_{num}} \prec 0\) , then
15.                 \({s_{num}} = 0\);
16.          end if;
17.   end if;
18.   \(t = s = 0\);
19.   if \({s_{den}} \ne 0\), then
20.          \(s = {s_{num}}/{s_{den}}\);
21.   end if;
22.   if \({t_{den}} \ne 0\), then
23.          \(t = {t_{num}}/{t_{den}}\);
24.   end if;
25.   \(s\)\(t\)的值代入线性对象的参数方程,计算出距离最近的点\({Q_0}\)\({Q_1}\);
26.   return \(\left\| {{Q_0} - {Q_1}} \right\|\);

3.4.7. 射线与线段的距离

射线与线段之间距离的计算,算法的伪码如下所示:

计算射线\({L_0}(s) = {P_0} + s{\vec d_0}\)和线段\({L_1}(t) = {P_1} + t{\vec d_1}\)之间的最小距离,线段\({L_1}(t)\)的两个端点是\({P_1}\)\({P_1} + {\vec d_1}\),其中\(s \in \left[ {0, + \infty } \right),t \in \left[ {0,1} \right]\)
return (距离)
1.    \(a = {\vec d_0} \cdot {\vec d_0},b = {\vec d_0} \cdot {\vec d_1},c = {\vec d_1} \cdot {\vec d_1},d = {\vec d_0} \cdot ({P_0} - {P_1}),e = {\vec d_1} \cdot ({P_0} - {P_1})\)
2.    \(\Delta = ac - {b^2}\)
3.    \({t_{den}} = {s_{den}} = \Delta \);
4.    if \(\Delta = = 0\),then
5.           \({t_{num}} = 0,{s_{num}} = - e,{s_{den}} = b\)(或\({t_{num}} = 0,{s_{num}} = - d,{s_{den}} = a\)\({s_{num}} = 0,{t_{num}} = d,{t_{den}} = b\)\({s_{num}} = 0,{t_{num}} = e,{t_{den}} = c\));
6.    else
7.           \({s_{num}} = be - cd,{t_{num}} = ae - bd\);
8.    end if;
9.    if \({s_{num}} \prec 0\),then
10.          \({s_{num}} = 0,{t_{num}} = d,{t_{den}} = b\)(或\({s_{num}} = 0,{t_{num}} = e,{t_{den}} = c\));
11.   end if;
12.   if\({t_{num}} \prec 0\), then
13.          \({t_{num}} = 0,{s_{num}} = - d,{s_{den}} = a\) (或\({t_{num}} = 0,{s_{num}} = - e,{s_{den}} = b\));
14.          if \({s_{num}} \prec 0\) , then
15.                 \({s_{num}} = 0\);
16.          end if;
17.   else if \({t_{num}} \succ {t_{den}}\), then
18.          \({t_{num}} = {t_{den}},{s_{num}} = \left( {c - e} \right),{s_{den}} = b\) (或\({t_{num}} = {t_{den}},{s_{num}} = \left( {b - d} \right),{s_{den}} = a\));
19.          if \({s_{num}} \prec 0\), then
20.                 \({s_{num}} = 0\);
21.          end if;
22.   end if;
23.   \(t = s = 0\);
24.   if \({s_{den}} \ne 0\), then
25.          \(s = {s_{num}}/{s_{den}}\);
26.   end if;
27.   if \({t_{den}} \ne 0\), then
28.          \(t = {t_{num}}/{t_{den}}\);
29.   end if;
30.   \(s\)\(t\)的值代入线性对象的参数方程,计算出距离最近的点\({Q_0}\)\({Q_1}\);
31. return \(\left\| {{Q_0} - {Q_1}} \right\|\);

spacer

Leave a reply