点と直線の最短距離

点と直線の最短距離は点から直線におろした垂線(緑の線)の長さです。

点と垂線の足の位置 $H$ がわかれば、垂線の長さがわかりますので、点と直線の最短距離は $H$ を求める問題ということになります。

また $H$ は、点と直線の最近傍点で解説した方法で求める事もできるのですが、今回は少し違った方法で求めていきます。

そして、この少し違った方法というのが他の衝突判定でも重要なキーポイントとなっている事に気づきましたので、その旨についても記載しておきたいと思います。

$H$ を求めて $t$ と出逢う

点を$P_{1}$、直線上の一点を$P_{2}$、方向ベクトルを$\vec{v_{2}}$、$P_{1}$ から直線に下した垂線の足を$H$ とします。

このとき、$H$ の座標は $P_{2} から {\vec{v_{2}}}$ を伸ばした先にあります。

このどれだけ伸ばせばいいかの値を $t$ とすると、$H$ は以下の式で表せます。($t$ の登場です！)

$H = P_{2} + t\vec{v_{2}}$

$P_{2}$ も $\vec{v{2}}$ も初めからわかっているので、$t$ さえ決まれば、$H$ は決まります。

言い換えれば、$t$ が決まれば $xy$ 座標($H$の)が決まるということです。

また、このように $t$ が決まれば $xy$ が決まるような $t$ を媒介変数というそうです。

この記事では、この $t$ を一発で求めてしまう計算式を導き出します。

$t$ のこと、もっと知りたい

$t$ についてもっと知るために、まず $H$ から $P_{1}$ に向かうベクトル $\vec{HP_{1}}$ を考えます。

$\vec{HP_{1}}$ は $P_{1}$ から $H$ を引き算する事で求められます。

$\vec{HP_{1}} = P_{1} - H$

$\vec{HP_{1}}$ は直線に対して垂直なので、直線の方向を表す $\vec{v_{2}}$ との内積は 0 になります。 (垂直なベクトル同士の内積は0)

$\vec{v_{2}} \cdot \vec{HP_{1}} = 0$

この式を展開していきます

$\vec{v_{2}} \cdot \vec{HP_{1}} = 0$
$\vec{v_{2}} \cdot (P_{1} - H) = 0$
$\vec{v_{2}} \cdot (P_{1} - (P_{2} + t\vec{v_{2}})) = 0$
$\vec{v_{2}} \cdot (P_{1} - P_{2} - t\vec{v_{2}}) = 0$
$\vec{v_{2}} \cdot P_{1} - \vec{v_{2}} \cdot P_{2} - \vec{v_{2}} \cdot t\vec{v_{2}} = 0$
$\vec{v_{2}} \cdot P_{1} - \vec{v_{2}} \cdot P_{2} - t(\vec{v_{2}} \cdot \vec{v_{2}}) = 0$
$t(\vec{v_{2}} \cdot \vec{v_{2}}) = \vec{v_{2}} \cdot P_{1} - \vec{v_{2}} \cdot P_{2}$
$t(\vec{v_{2}} \cdot \vec{v_{2}}) = \vec{v_{2}} \cdot (P_{1} - P_{2})$
$t = \frac{\vec{v_{2}} \cdot (P_{1} - P_{2})}{\vec{v_{2}} \cdot \vec{v_{2}}}$

$t$ が一発で求まる計算式が手に入りました！

$t = \frac{\vec{v_{2}} \cdot (P_{1} - P_{2})}{\vec{v_{2}} \cdot \vec{v_{2}}}$

$t$ の事は $\vec{v_{2}} と P_{1} と P_{2}$ が教えてくれるのです。

本記事のメインディッシュは $H$ を求めるというよりも、この $t$ を一発で求める方が重要でした。

$t$ が求まれば $H$ は $P_{2}$ に $\vec{v_{2}}$ を $t$ 倍した $t\vec{v_{2}}$ を足すだけですし、$H$ が求まれば $P_{1}$ と $H$ の距離 ($|\vec{P_{1}H}|$) も求まります。

$H = P_{2} + t\vec{v_{2}}$
$t = \frac{\vec{v_{2}} \cdot (P_{1} - P_{2})}{\vec{v_{2}} \cdot \vec{v_{2}}}$

点と直線の最短距離は $|\vec{P_{1}H}|$

$t$ が教えてくれること

$t$ の値を観察すると面白い事がわかります。

グラフ右の Controls で $xy$を操作すると点が移動します。またリアルタイムに $t$ の値も表示されます。

$H$ が $\vec{v_{2}}$ の矢印の範囲内にあるとき、$t$ が 0 ～ 1 の値に収まる事が分かるかと思います。

これは $t$ の値を見る事で、${P_{1}}$ と $\vec{v_{2}}$ の関係がわかるということになります。

この記事では、「で？これがなんなの？」にしかならないかもしれませんが、この情報は半直線や線分、またカプセルといった形状の衝突判定で有力な情報源となります。

サンプルコード

点と直線から、距離、垂線の足、媒介変数$t$ を取得するサンプルコードを示します。

/**
  * 点と直線の最短距離を求める関数の戻り値
  */
 interface IResultNearestDistance {
   distance: number;  /** 距離 */
   h: Vector2;        /** 点から直線におろした垂線の足 */
   t: number;         /** ベクトルの媒介変数 t */
 }
 
 /**
  * 点と直線の最短距離
  * @param point 点
  * @param line 直線
  */
 function getNearestDistance(point:Vector2, line:Line) 
 {
   const result:IResultNearestDistance = {
     distance: 0,
     h: Vector2.zero,
     t: 0,
   };
 
   // 点の位置を p1とする
   const p1 = point;
 
   // 線の基点を p2、方向ベクトルをv2 とする
   const p2 = line.p;
   const v2 = line.v;
 
   // 方向ベクトルが 0ベクトルの場合は0除算になるので判定している
   // 0ベクトルの場合は t = 0 のまま(p2の位置を基点)にする
   if (Vector2.isZero(v2) == false) 
   {
     // p1から線に垂線を落とした時の衝突点を H とすると
     // H は v2 を t倍した位置にくる
     // この t(ベクトル係数) は以下の計算で求まる    
     result.t = Vector2.dot(v2, Vector2.sub(p1, p2)) / v2.sqrMagnitude;
   }
   
   // 最短距離は p1 と h の間の距離を求めればよい
   const tv2 = Vector2.times(v2, result.t);
   result.h   = Vector2.add(p2, tv2);
   result.distance = Vector2.sub(result.h, p1).magnitude;
 
   return result;
 };

補足

同じベクトル同士の内積は、そのベクトルの長さの二乗になります。

$\vec{v_{2}} \cdot \vec{v_{2}} = |\vec{v_{2}}|^2$