直線と直線の最短距離本気①

直線と直線の最短距離についてまとめていたら、あれ？2次元だったらもっと簡単な計算でよくない？と気づいてしまいました。

簡単な方の計算(といっても簡単ではない)については直線と直線の最短距離簡易版をご覧ください。 (2次元だったら簡易版で事足りる気がしています)

この本気版はざっくり言うと3次元における直線と直線の最短距離の求め方です。

この記事では直線と直線の最短距離とはなんぞや？ということと、理屈は置いといて最短距離の求め方を記載しています。

長くなるので、理屈編については直線と直線の最短距離本気②に分割しました。

直線と直線の最短距離とはなんぞや？

２直線の最短距離となるのは、２つの直線に対して垂直になる線の長さになります。

これは上の図のように、2直線が平行な場合はイメージできるかと思います。

この場合は、直線上のどこか１点と直線の最短距離を求めればいいので、点と直線の最短距離にて解説した方法で求めます。

しかし、2直線が平行ではない場合はどうでしょうか

2直線に垂直な線を実際に書いてみようと思っても、異なる直線の両方に垂直になる線など書けないじゃないかと気づきます。

そもそも平行でない直線は必ず交わるのだから、2直線の最短距離は常に0じゃないの？計算する必要ある？

そのような感じで無職は3日ほど頭を抱えました。

そして閃いたのは、2本の直線に垂直になる線はZ軸という事でした。

そもそも2次元なのでZ軸はないのですが、2次元で考えてもわけがわからない状況から抜け出せません。

そこでいったん頭を柔らかくして、3次元で考えた場合は奥行き(Z軸)があるという事に目を向けます。

このような2直線があるとします。

これは2直線を真横から見た時のイメージです。

一見重なっているように見えた直線も奥行き(Z軸)を考えると、夜空に輝く星たちのように距離が離れているかもしれません。

この記事で求めるのは、このように3次元で考えた時の最短距離になりますが、計算の内容は2次元でも同じになります。

そして先に答えを言ってしまうと２次元の場合、平行でない直線は必ず交わり、Z軸はない(常に0ともいえる)ため、最短距離は常に0です。

では、交わっている直線の最短距離は0なのに、それをわざわざ求めるとはどういうこと？となるのが普通かと思います。

実際、求めたいのは最短距離ではなく、最短距離を求めるうえで手に入るとある素敵な値を手に入れる事が本記事の主題です。

本当に求めたいのは $t_{1}$ と $t_{2}$

直線 $L1, L2$ があり、直線上の1点をそれぞれ $P_{1}, P_{2}$、直線の方向を表すベクトルをそれぞれ $\vec{v_{1}}, \vec{v_{2}}$ とします。

また2つの直線の最短距離を結ぶ線について、$L1$ 上の点を$Q_{1}$、$L2$ 上の点を $Q_{2}$ とします。
(2次元だと奥行きがないため $Q_{1}, Q_{2}$ は同じ座標になりますが便宜上分けて書きます。)

$Q_{1}$ は $\vec{v_{1}}$ を伸ばした先にあります、どれだけ伸ばせば $Q_{1}$ に届くかの値を $t_{1}$ とします。

$Q_{2}$ は $\vec{v_{2}}$ を伸ばした先にあります、どれだけ伸ばせば $Q_{2}$ に届くかの値を $t_{2}$ とします。

式にするとこうなります。

$Q_{1} = P_{1} + t_{1}\vec{v_{1}}$
$Q_{2} = P_{2} + t_{2}\vec{v_{2}}$

$t_{1}, t_{2}$ を求める事ができれば、$Q_{1}, Q_{2}$ がわかり、また$Q_{1}, Q_{2}$ の間の距離が2直線の最短距離となります。

冒頭でふれたとある素敵な値とはこの $t_{1}, t_{2}$ のことです。

そして以下が $t_{1}, t_{2}$ を求める式です。

$D_{11} = \vec{v_{1}} \cdot \vec{v_{1}}$、 $D_{22} = \vec{v_{2}} \cdot \vec{v_{2}}$、 $D_{12} = \vec{v_{1}} \cdot \vec{v_{2}}$ とすると

$ t_{1} = \frac {{D_{12}} \vec{v_{2}} \cdot(P_{1} - P_{2}) - D_{22} \vec{v_{1}} \cdot (P_{1} - P_{2}) } {D_{11} D_{22} - D_{12} D_{12}} $
$Q_{1} = P_{1} + t_{1}\vec{v_{1}}$
$ t_{2} = \frac{\vec{v_{2}} \cdot (Q_{1} - P_{2})}{D_{22}} $
$Q_{2} = P_{2} + t_{2}\vec{v_{2}}$

なぜこの式で $t_{1}, t_{2}$ が求まるのかは直線と直線の最短距離本気②をご覧ください。

$t_{1}, t_{2}$ の値からわかること

$t_{1}, t_{2}$ は $\vec{v_{1}}, \vec{v_{2}}$ をどれだけ伸ばせば $Q_{1}, Q_{2}$ に届くのかという値なので、2次元の場合 $t_{1}, t_{2}$ のどちらかがわかれば直線の交点の位置がわかります。

また $\vec{v_{1}}, \vec{v_{2}}$ が交差しているときは、$t_{1}, t_{2}$ の値が 0 ～ 1の間に収まります。

直線が交差しているかどうかだけでなく、$\vec{v_{1}}, \vec{v_{2}}$ が交差しているかどうかを $t_{1}, t_{2}$ の値を見ることで判断できます。

これは線分が交差しているかどうかの判定として使うことができます。

サンプルプログラム

/**
  * ２直線の最短距離を求める関数の戻り値を定義
  */
 interface IResultDistance {
   distance:number, /** 直線間の距離 */
   p1:Vector2, /** 直線１上の垂線の足 */
   p2:Vector2, /** 直線２上の垂線の足 */
   t1:number,  /** 直線１側の媒介変数 */
   t2:number,  /** 直線２側の媒介変数 */
 }
 
 /**
  * ２直線の最短距離を求める
  */
 function getNearestDistance(l1:Line, l2:Line): IResultDistance 
 {
   // ２直線が平行だったら、点と直線の最短距離に帰結
   if (Vector2.isParallel(l1.v, l2.v)) {
     const res = PointAndLine.getNearestDistance(l1.p, l2);
 
     return {
       distance: res.distance,
       p1: l1.p.clone(),
       p2: res.h,
       t1: 0,
       t2: res.t,
     }
   }
 
   // 2直線が交差しているときの最短距離、及び媒介変数 t を求める計算(最短距離は基本0)
   const p1 = l1.p;
   const p2 = l2.p;
   const v1 = l1.v;
   const v2 = l2.v;
   const D12 = v1.dot(v2);
   const D11 = v1.sqrMagnitude;
   const D22 = v2.sqrMagnitude;
   const P12 = Vector2.sub(p1, p2);
 
   // 媒介変数 t と 衝突点 q1, q2 の算出
   const t1 = (D12 * v2.dot(P12) - D22 * v1.dot(P12)) / (D11 * D22 - D12 * D12);
   const q1 = Vector2.add(p1, Vector2.times(v1, t1));
   const t2 = v2.dot(Vector2.sub(q1, p2)) / D22;
   const q2 = Vector2.add(p2, Vector2.times(v2, t2));
   
   return {
     distance: Vector2.sub(q2, q1).magnitude,
     p1:q1,
     p2:q2,
     t1, 
     t2,
   };
 }

直線と直線の最短距離 本気①

直線と直線の最短距離とはなんぞや？

本当に求めたいのは $t_{1}$ と $t_{2}$

$t_{1}, t_{2}$ の値からわかること

サンプルプログラム

直線と直線の最短距離本気①