点と線分との最短距離

こんにちは。
与えた点 $\boldsymbol{p}$ と線分 $\boldsymbol{a}\boldsymbol{b}$ との間の最短距離を数学的に求めます ^{1 2 3}。求める解は線分 $\boldsymbol{a}\boldsymbol{b}$ 上の最短距離点 $\boldsymbol{q}_{\min}$ 、最短距離は $\left|\boldsymbol{p}-\boldsymbol{q}_{\min}\right|$ です。

(1) 一般に線分 $\boldsymbol{a}\boldsymbol{b}$ 上の任意の点 $\boldsymbol{q}$ については下記が成立します。

\begin{align}
\boldsymbol{q} &= s\,\boldsymbol{a} + t\,\boldsymbol{b} \\
1 &= s + t\\
0 &\le s \le 1
\end{align}

上式を変形すると $s,\ t$ と $\boldsymbol{q}$ との関係は下記を満たします^{4 5}。

\begin{align}
s &= \frac{\left(\boldsymbol{q}-\boldsymbol{b}\right) \cdot \left(\boldsymbol{a}-\boldsymbol{b}\right)}{\left(\boldsymbol{a}-\boldsymbol{b}\right) \cdot \left(\boldsymbol{a}-\boldsymbol{b}\right)}\\
t &= \frac{\left(\boldsymbol{a}-\boldsymbol{q}\right) \cdot \left(\boldsymbol{a}-\boldsymbol{b}\right)}{\left(\boldsymbol{a}-\boldsymbol{b}\right) \cdot \left(\boldsymbol{a}-\boldsymbol{b}\right)}
\end{align}

(2) ここで $\boldsymbol{q}=\boldsymbol{q}_{\min}$ という条件を使って⁶、その場合の $s,\ t$ の値を求めることを考えると、上記式の中で $\boldsymbol{q}$ を $\boldsymbol{p}$ へ置き換えても不変となるので、$\boldsymbol{p}$ を使って決まることとなります。

$s,\ t$ が決まれば⁷、求める最短距離点 $\boldsymbol{q}_{\min}$ は第一式を用いて得られます。

最短距離の計算

$0 \le s \le 1$ の条件下で、上記にしたがって最短距離の値を計算してみると、

\begin{align}
\left| \boldsymbol{p} - \boldsymbol{q}_{\min} \right| &= \sqrt{\tilde{u}-\frac{\tilde{s}^2}{\tilde{s}+\tilde{t}}}=\sqrt{\tilde{v}-\frac{\tilde{t}^2}{\tilde{s}+\tilde{t}}} \\
\tilde{s} &= \left(\boldsymbol{p}-\boldsymbol{b}\right) \cdot \left(\boldsymbol{a}-\boldsymbol{b}\right)\\
\tilde{t} &= \left(\boldsymbol{a}-\boldsymbol{p}\right) \cdot \left(\boldsymbol{a}-\boldsymbol{b}\right)\\
\tilde{u} &= \left(\boldsymbol{p}-\boldsymbol{b}\right) \cdot \left(\boldsymbol{p}-\boldsymbol{b}\right)\\
\tilde{v} &= \left(\boldsymbol{p}-\boldsymbol{a}\right) \cdot \left(\boldsymbol{p}-\boldsymbol{a}\right)
\end{align}

まとめて表すと、

\left| \boldsymbol{p} - \boldsymbol{q}_{\min} \right| = \sqrt{\frac{\left(\left(\boldsymbol{p}-\boldsymbol{a}\right)\cdot\left(\boldsymbol{p}-\boldsymbol{a}\right)\right) \left(\left(\boldsymbol{a}-\boldsymbol{b}\right)\cdot\left(\boldsymbol{a}-\boldsymbol{b}\right)\right) - \left(\left(\boldsymbol{p}-\boldsymbol{a}\right)\cdot\left(\boldsymbol{a}-\boldsymbol{b}\right)\right)^2}{\left(\boldsymbol{a}-\boldsymbol{b}\right)\cdot\left(\boldsymbol{a}-\boldsymbol{b}\right)}}

また Cross product （$\times$）を用いて書き換えると^{8 9}、

\left| \boldsymbol{p} - \boldsymbol{q}_{\min} \right| = \frac{\left\| \left(\boldsymbol{p}-\boldsymbol{a}\right) \times \left(\boldsymbol{a}-\boldsymbol{b}\right) \right\|}{\left\|\boldsymbol{a}-\boldsymbol{b}\right\|}

2次元平面の場合

これを2次元平面の場合に成分で書くと、

\frac{|\left(p_\mathrm{x}-a_\mathrm{x}\right)\left(a_\mathrm{y}-b_\mathrm{y}\right)-\left(p_\mathrm{y}-a_\mathrm{y}\right)\left(a_\mathrm{x}-b_\mathrm{x}\right)|}{\sqrt{\left(a_\mathrm{x}-b_\mathrm{x}\right)\left(a_\mathrm{x}-b_\mathrm{x}\right)+\left(a_\mathrm{y}-b_\mathrm{y}\right)\left(a_\mathrm{y}-b_\mathrm{y}\right)}}

1. これは、「点と多角形の辺との最短距離」の中の pointToLineSegment() で行った計算の説明です。 ↩

2. 「点と直線の距離」（Wikipedia）の中にも、ベクトルを用いた公式の説明があります。 ↩

3. ただし $\boldsymbol{a} = \boldsymbol{b}$ の場合を除くとします。この場合は、求める最短距離点も $\boldsymbol{a}$ (= $\boldsymbol{b}$) そのものです。 ↩

4. これらは、$\boldsymbol{q} - \boldsymbol{b} = s \left(\boldsymbol{a} - \boldsymbol{b}\right)$ などと変形して行けば得られます。 ↩

5. なお、$1 = s + t$ を変形すると、$\left(\boldsymbol{a}-\boldsymbol{b}\right) \cdot \left(\boldsymbol{a}-\boldsymbol{b}\right) = \left(\boldsymbol{q}-\boldsymbol{b}\right) \cdot \left(\boldsymbol{a}-\boldsymbol{b}\right) + \left(\boldsymbol{a}-\boldsymbol{q}\right) \cdot \left(\boldsymbol{a}-\boldsymbol{b}\right) $ ↩

6. この条件から、$\left(\boldsymbol{p}-\boldsymbol{q}_{\min}\right) \cdot \left(\boldsymbol{a}-\boldsymbol{b}\right)=0$ （$\boldsymbol{p}\boldsymbol{q}$ が垂線であること）が成立し利用できます。 ↩

7. なお、$s,\ t$ の分子（すなわち $\tilde{s},,\tilde{t}$）を $\boldsymbol{p}$ を用いて先に計算し、$0 \lt s \lt 1$ かどうか（点 $\boldsymbol{q}$ が線分 $\boldsymbol{a}\boldsymbol{b}$ 内かどうか）を判定すると計算の無駄が少なく、$s,\ t$ がこの範囲外ならば、$\boldsymbol{a}$（もしくは $\boldsymbol{b}$ ）自身が最短距離点です。 ↩

8. Cross_product についての関係式は、$\left|\boldsymbol{a}\times\boldsymbol{b} \right| = \sqrt{\left|\boldsymbol{a}\right|^2 \left|\boldsymbol{b}\right|^2 - \left(\boldsymbol{a}\cdot\boldsymbol{b}\right)^2}$ ↩

9. これは三角形の面積を求める式とも等価です（「三角形#直交座標による式」 (Wikipedia)） ↩