直線と直線の最短距離 簡易版

直線と直線の最短距離 本気①を書いていたら、あれ？2次元だったらもっと簡単な計算で事足りるのでは？と気づいてしまったので もう少し簡単な方法についてまとめます。

むしろ 直線と直線の最短距離 本気① という記事は不要だった感さえ否めません。(でも頑張ったので本気編として残しておきます)

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

上の図のように2直線が平行な場合、2直線に垂直になる線分(緑の線)の長さとなります。

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

上の図のように2直線が平行ではない場合、2次元では直線は必ず交差するので、最短距離は0です。(計算するまでもありませんね)

最短距離の求め方だけであればこれで終了なんですが、本題はここからです。

上記の方法で最短距離は求まるのですが、直線に関する衝突判定をする場合には最短距離だけではなく、もう少し追加で欲しい情報があったりします。

この追加で欲しい情報とは何か、またどうやって求めるのかについて記載していきます。

追加で欲しい情報は $t_{1}$ と $t_{2}$

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

また2直線の交点を $Q$ とします。

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

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

$Q$ は以下の式で表す事ができます。
$Q = P_{1} + t_{1}\vec{v_{1}}$
$Q = P_{2} + t_{2}\vec{v_{2}}$

この $t_{1}, t_{2}$ を求める事ができれば 直線の交点 $Q$ の位置もわかりますし、また線分やカプセルといった形状の衝突判定もできるようになったりします。

例えば、$\vec{v_{1}}$ と $\vec{v_{2}}$ が交差するような関係だった場合 $t_{1}, t_{2}$ は 0 ～ 1の間に収まります。

これは線分同士の衝突で使えますし、このように、$t_{1}, t_{2}$ の値から様々な情報を得る事ができます。

また $t_{1}, t_{2}$ のように、値が決まるとベクトルの長さが決まり最終的な位置($xy$) を決定する変数を 媒介変数というそうです。

本記事の主題は直線と直線の最短距離というより、この媒介変数 $t_{1}, t_{2}$ を求める事にあります。

$t_{1}, t_{2}$ の求め方については直線と直線の最短距離 本気①の方でもまとめていたのですが こちらの計算がとてつもなく長く、更に難しいんです。

そして、2次元ならもっと簡単な計算で求められるのでは？と気づき、この記事ではその簡易版の計算方法を紹介します。

$t_{1}, t_{2}$ を求める計算式

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

また$P_{2}からP_{1}$ に向かうベクトルを $\vec{v}$ とします。

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

としたとき、$t_{1}$ か $t_{2}$ がわかれば $Q$ の位置がきまります。

そして、この $t_{1}, t_{2}$ はベクトルの外積を使って、以下の式で求められます。

$t1 = \frac {\vec{v} \times \vec{v_{2}}} {\vec{v_{2}} \times \vec{v_{1}}} $
$t2 = \frac {-\vec{v} \times \vec{v_{1}}} {\vec{v_{1}} \times \vec{v_{2}}} $

※2直線が平行な場合は分母が0(平行なベクトル同士の外積は0)になってしまうので、この式は使えません。

このように、2直線が持っている情報から 媒介変数 $t_{1}, t_{2}$ を求めることができ、この $t_{1}, t_{2}$ は衝突判定を行う上で重要な情報として利用できるので存在に慣れておきましょう。

なぜ、この式で$t_{1}, t_{2}$ が求められる？

$t_{1}$ の求め方

$\vec{P_{2}P_{1}}$ を $\vec{v}$、$\vec{P_{2}Q}$ を $\vec{v'_{2}}$ と表します。

$\vec{v'_{2}}$ は以下のようにあらわせます。

$\vec{v'_{2}} = \vec{v} + t_{1}\vec{v_{1}}$

また $\vec{v_{2}}$ と $\vec{v'_{2}}$ は平行なので、外積は0になります。

これを式で表し解いていきます。

$\vec{v_{2}} \times \vec{v'_{2}} = 0$
$\vec{v_{2}} \times (\vec{v} + t_{1}\vec{v_{1}}) = 0$
$\vec{v_{2}} \times \vec{v} + \vec{v_{2}} \times(t_{1}\vec{v_{1}}) = 0$　※外積は分配法則が使える
$\vec{v_{2}} \times \vec{v} + t_{1} (\vec{v_{2}} \times \vec{v_{1}}) = 0$　※定数倍は抜き出せる
$t_{1} (\vec{v_{2}} \times \vec{v_{1}}) = -\vec{v_{2}} \times \vec{v}$
$t_{1} (\vec{v_{2}} \times \vec{v_{1}}) = \vec{v} \times \vec{v_{2}}$　　　※外積は入れ替えると符号が変わる
$t_{1} = \frac{\vec{v} \times \vec{v_{2}}}{\vec{v_{2}} \times \vec{v_{1}}}$

$t_{2}$ の求め方

基本的に $t_{1}$ の求め方と同様です。

$\vec{P_{2}P_{1}}$ を $\vec{v}$、$\vec{P_{1}Q}$ を $\vec{v'_{1}}$ と表します。

$\vec{v'_{1}}$ は以下のようにあらわせます。

$\vec{v'_{1}} = -\vec{v} + t_{2}\vec{v_{2}}$

また $\vec{v_{1}}$ と $\vec{v'_{1}}$ は平行なので、外積は0になります。

これを式で表し解いていきます。

$\vec{v_{1}} \times \vec{v'_{1}} = 0$
$\vec{v_{1}} \times (-\vec{v} + t_{2}\vec{v_{2}}) = 0$
$-\vec{v_{1}} \times \vec{v} + \vec{v_{1}} \times(t_{2}\vec{v_{2}}) = 0$　※外積は分配法則が使える
$-\vec{v_{1}} \times \vec{v} + t_{2} (\vec{v_{1}} \times \vec{v_{2}}) = 0$　※定数倍は抜き出せる
$t_{2} (\vec{v_{1}} \times \vec{v_{2}}) = \vec{v_{1}} \times \vec{v}$
$t_{2} (\vec{v_{1}} \times \vec{v_{2}}) = -\vec{v} \times \vec{v_{1}}$　　　※外積は入れ替えると符号が変わる
$t_{2} = \frac{-\vec{v} \times \vec{v_{1}}}{\vec{v_{1}} \times \vec{v_{2}}}$

まとめ

$t_{1}, t_{2}$ を求める理屈は以上となります。

サンプルコード

/**
  * ２直線の最短距離を求める関数の戻り値を定義
  */
 interface IResultDistance {
   distance:number, /** 直線間の距離 */
   p1:Vector2, /** 交点(実質p2と同じ) */
   p2:Vector2, /** 交点(実質p1と同じ) */
   t1:number,  /** 直線１側の媒介変数 */
   t2:number,  /** 直線２側の媒介変数 */
 }
 
 /**
  * 2直線の最短距離を求める
  * @param l1 直線１
  * @param l2 直線２
  */
 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,
     }
   }
 
   const v1 = l1.v;
   const v2 = l2.v;
   const v = Vector2.sub(l1.p, l2.p);
 
   const t1 = v.cross(v2) / v2.cross(v1);
   const t2 = v.times(-1).cross(v1) / v1.cross(v2);  
 
   const p1 = Vector2.add(l1.p, Vector2.times(l1.v, t1));
   const p2 = Vector2.add(l2.p, Vector2.times(l2.v, t2));
 
   return {
     distance: Vector2.sub(p1, p2).magnitude,
     p1, p2, t1, t2
   };
 }