3.4. 线性对象间的距离

3.4. 线性对象间的距离

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

$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}$

$$\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}$$

${s_c} = \frac{{be – cd}}{{ac – {b^2}}},{t_c} = \frac{{ae – bd}}{{ac – {b^2}}} \tag{3.21}$

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

${\sigma _0} = \frac{{\left( {{P_1} – {P_0}} \right) \cdot {{\vec d}_0}}}{{{{\vec d}_0} \cdot {{\vec d}_0}}} \tag{3.23}$

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

${\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}$

3.4.2. 直线与直线的距离

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描述的，各种线性对象之间距离计算的算法。

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.4.4. 直线与射线的距离

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. 直线与线段的距离

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. 射线与射线的距离

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. 射线与线段的距离

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\|$$;