直線と直線の最短距離 本気②
直線と直線の最短距離 本気①の続編記事となります。
タイトルは直線と直線の最短距離となっていますが、この記事で扱うのは $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}$ は同じ座標になりますが便宜上分けて書きます。)
$\vec{v_{1}}$ をどれだけ伸ばせば $Q_{1}$ に届くかの値を $t_{1}$ とします。
$\vec{v_{2}}$ をどれだけ伸ばせば $Q_{2}$ に届くかの値を $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}$ が求まるのか
点 $Q_{1}, Q_{2}$ を式で表すと以下のようになります。
$Q_{1} = P_{1} + t_{1}\vec{v_{1}}$
$Q_{2} = P_{2} + t_{2}\vec{v_{2}}$
$t_{2}$ から求めていきます
$t_{2}$ は $Q_{1}$ と直線 $L2$ の最短距離を求める方法から以下の式で求まります。
(詳細については 点と直線の最短距離をご覧ください)
$ t_{2} = \frac{\vec{v_{2}} \cdot (Q_{1} - P_{2})}{\vec{v_{2}} \cdot \vec{v_{2}}} = \frac{\vec{v_{2}} \cdot (P_{1} + t_{1}\vec{v_{1}} - P_{2})}{\vec{v_{2}} \cdot \vec{v_{2}}} = \frac{\vec{v_{2}} \cdot (P_{1} - P_{2} + t_{1}\vec{v_{1}})}{\vec{v_{2}} \cdot \vec{v_{2}}} $
$t_{1}$ を求める
$t_{1}$ がわからないと $t_{2}$ が求められないので、次に $t_{1}$ を求めていきます。
2直線の最短距離を結ぶ線分 $\vec{Q_{2}Q_{1}}$ は 直線 $L1$ とも垂直じゃないといけません。
ここから $L1$ の方向を表すベクトル $\vec{v_{1}}$ と $\vec{Q_{2}Q_{1}}$ 内積の結果は0 になることを利用します。(垂直なベクトル同士の内積は0)
その式を計算していきます。
$\vec{v_{1}} \cdot \vec{Q_{2}Q_{1}} = 0$
$\vec{v_{1}} \cdot (Q_{1} - Q_{2}) = 0$
$\vec{v_{1}} \cdot (P_{1} + t_{1}\vec{v_{1}} - (P_{2} + t_{2}\vec{v_{2}})) = 0$
$\vec{v_{1}} \cdot (P_{1} + t_{1}\vec{v_{1}} - P_{2} - t_{2}\vec{v_{2}}) = 0$
内積の分配法則、定数倍の法則に従って、さらに式を展開します。
$\vec{v_{1}} \cdot (P_{1} + t_{1}\vec{v_{1}} - P_{2} - t_{2}\vec{v_{2}}) = 0$
$\vec{v_{1}} \cdot (P_{1} - P_{2} + t_{1}\vec{v_{1}} - t_{2}\vec{v_{2}}) = 0$
$\vec{v_{1}} \cdot (P_{1} - P_{2}) + \vec{v_{1}} \cdot t_{1}\vec{v_{1}} - \vec{v_{1}} \cdot t_{2}\vec{v_{2}} = 0$
$\vec{v_{1}} \cdot (P_{1} - P_{2}) + t_{1}(\vec{v_{1}} \cdot \vec{v_{1}}) - t_{2}(\vec{v_{1}} \cdot \vec{v_{2}}) = 0$
ここで予め求めておいた $t_{2}$ を上の式に代入します。
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+ t_{1}(\vec{v_{1}} \cdot \vec{v_{1}})
- \frac{\vec{v_{2}} \cdot (P_{1} - P_{2} + t_{1}\vec{v_{1}})}{\vec{v_{2}} \cdot \vec{v_{2}}}(\vec{v_{1}} \cdot \vec{v_{2}}) = 0$
式が長くなってきたので一部の値を別の文字に置き換えたいと思います。
$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}}$
上記の式に沿って書き直すと
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+ t_{1}D_{11}
- \frac{\vec{v_{2}} \cdot (P_{1} - P_{2} + t_{1}\vec{v_{1}})}{D_{22}}(D_{12}) = 0$
まだ長いですが頑張って計算を続けていきます
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+ t_{1}D_{11}
- \frac{\vec{v_{2}} \cdot (P_{1} - P_{2} + t_{1}\vec{v_{1}})}{D_{22}}(D_{12}) = 0
$
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+ t_{1}D_{11}
- \frac{\vec{v_{2}} \cdot (t_{1}\vec{v_{1}} + P_{1} - P_{2})}{D_{22}}(D_{12}) = 0
$
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+ t_{1}D_{11}
- \frac{\vec{v_{2}} \cdot (t_{1}\vec{v_{1}}) + \vec{v_{2}} \cdot(P_{1} - P_{2})}{D_{22}}(D_{12}) = 0
$
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+ t_{1}D_{11}
- \frac{t_{1}(\vec{v_{2}} \cdot \vec{v_{1}}) + \vec{v_{2}} \cdot(P_{1} - P_{2})}{D_{22}}(D_{12}) = 0
$
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+ t_{1}D_{11}
- \frac{t_{1}(\vec{v_{1}} \cdot \vec{v_{2}}) + \vec{v_{2}} \cdot(P_{1} - P_{2})}{D_{22}}(D_{12}) = 0
$
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+ t_{1}D_{11}
- \{
\frac
{t_{1}(\vec{v_{1}} \cdot \vec{v_{2}})}
{D_{22}}
+
\frac
{\vec{v_{2}} \cdot(P_{1} - P_{2})}
{D_{22}}
\}
(D_{12}) = 0
$
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+ t_{1}D_{11}
- \{
\frac
{t_{1}(\vec{v_{1}} \cdot \vec{v_{2}})}
{D_{22}}(D_{12})
+
\frac
{\vec{v_{2}} \cdot(P_{1} - P_{2})}
{D_{22}}(D_{12})
\}
= 0
$
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+ t_{1}D_{11}
-
\frac
{t_{1}(\vec{v_{1}} \cdot \vec{v_{2}})}
{D_{22}}(D_{12})
-
\frac
{\vec{v_{2}} \cdot(P_{1} - P_{2})}
{D_{22}}(D_{12})
= 0
$
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+
t_{1}(
D_{11}
-
\frac
{\vec{v_{1}} \cdot \vec{v_{2}}}
{D_{22}}(D_{12})
)
-
\frac
{\vec{v_{2}} \cdot(P_{1} - P_{2})}
{D_{22}}(D_{12})
= 0
$
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+
t_{1}(
D_{11}
-
\frac
{D_{12}}
{D_{22}}(D_{12})
)
-
\frac
{\vec{v_{2}} \cdot(P_{1} - P_{2})}
{D_{22}}(D_{12})
= 0
$
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+
t_{1}(
D_{11}
-
\frac
{D_{12}}
{D_{22}}(D_{12})
)
-
\frac
{D_{12}}
{D_{22}}(\vec{v_{2}} \cdot(P_{1} - P_{2}))
= 0
$
かなり長いですがまだ続きます、今度は $t_{1}$ について解いていきます。
$
\vec{v_{1}} \cdot (P_{1} - P_{2})
+
t_{1}(
D_{11}
-
\frac
{D_{12}}
{D_{22}}(D_{12})
)
-
\frac
{D_{12}}
{D_{22}}(\vec{v_{2}} \cdot(P_{1} - P_{2}))
= 0
$
$
t_{1}(
D_{11}
-
\frac
{D_{12}}
{D_{22}}(D_{12})
)
=
\frac
{D_{12}}
{D_{22}}(\vec{v_{2}} \cdot(P_{1} - P_{2}))
- \vec{v_{1}} \cdot (P_{1} - P_{2})
$
$
t_{1}(
D_{11} D_{22}
-
D_{12} D_{12}
)
=
{D_{12}} \vec{v_{2}} \cdot(P_{1} - P_{2})
- D_{22} \vec{v_{1}} \cdot (P_{1} - P_{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}}
$
ようやく $t1$ が求まりました、$t_{2}$ も $t1$ がわかったので求まります。
最終的な式をまとめておきます。
$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}}$
ほとんどおまけ程度の話ですが、2直線の最短距離を結ぶ線分の始点と終点である $Q_{1}, Q_{2}$ が求まったので、直線と直線の最短距離も求まりますね。
2直線の最短距離 = $|\vec{Q_{1}Q_{2}}|$ (2次元の場合は基本0)