点と線分との最短距離

こんにちは。
与えた点 $\boldsymbol{p}$ と[線分](https://ja.wikipedia.org/wiki/線分) $\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}$ については下記が成立します。

```math
\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]。

```math
\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}$ という条件を使って[^6]、その場合の $s,\ t$ の値を求めることを考えると、上記式の中で $\boldsymbol{q}$ を $\boldsymbol{p}$ へ置き換えても不変となるので、$\boldsymbol{p}$ を使って決まることとなります。

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

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

```math
\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}
```

まとめて表すと、

```math
\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]、

```math
\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次元平面の場合に成分で書くと、

```math
\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]: これは、「[点と多角形の辺との最短距離](https://qiita.com/kkdd/items/0ba836107ba778ed1014)」の中の ```pointToLineSegment()``` で行った計算の説明です。
[^2]: 「[点と直線の距離](https://ja.wikipedia.org/wiki/点と直線の距離#ベクトルを用いた公式)」（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](https://en.wikipedia.org/wiki/Cross_product#Alternative_formulation) についての関係式は、$\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]: これは三角形の面積を求める式とも等価です（「[三角形#直交座標による式](https://ja.wikipedia.org/wiki/三角形#直交座標による式)」 (Wikipedia)）