Pythonで点と線分との最短距離を求めるコードを書く

はじめに

たまに、AtCoderとかで使うのですが、毎回検索して探すのが面倒なので自分用にライブラリを作成しました。

その他のAtCoderに役立つ記事の一覧は以下にあります。

あわせて読みたい

AtCoderで役立つ記事一覧（Python, Go言語）

点と線分の最短距離の求め方

Web検索すると、最短距離の求め方は、線分上のベクトルと点から線分への垂線が交わる点を求めてから計算する方法がメジャーなようです。

ただ、今回は、米田さん（E8さん）の書かれた「アルゴリズム×数学が基礎からしっかり身につく本」のP.135の方法をライブラリ化したいと思います。

詳しいアルゴリズムを知りたい方は書籍を見てください

簡単なアルゴリズムの説明

点をA、線分をBCとする。まず、３つのパターンに分ける

1. $\angle ABC > 90度$
   $\angle ABC$が90度より大きい場合は、点Aと点Bの距離が最短
2. $\angle ACB > 90度$
   $\angle ABC$が90度より大きい場合は、点Aと点Cの距離が最短
3. 上記以外
   点Aと線分BCの最短距離は線分BCのどこか

（１）（２）の判定は、線分BA（CA）,BC（CB）の内積が０より小さいかどうかで判定できます。

（３）の場合の最短距離の求め方ですが、「ベクトルBCとベクトルBAが作る平行四辺形の面積と外積が一致する」という性質を利用します。

平行四辺形の面積Sがわかれば、平行四辺形の面積は底辺×高さなので、底辺をBCとすれば高さはAまでの最短距離に一致します。

（１）（２）（３）のパターンの距離計算方法がわかったので実装します。

Pythonで関数を作成

関数calc_dist(dot, line)

ベクトルを作る計算が結構あるのでcalc_vector関数も用意しました。この関数は、点dotと線分lineの最短距離を求める関数calc_distの中で利用しています。

calc_distの中身は先ほど説明したアルゴリズムをそのまま実装しました。

def calc_vector(x0, y0, x1, y1) :
    return x1-x0, y1-y0

def calc_dist(dot, line):
    ax, ay = dot
    bx, by, cx, cy = line 
    BAx, BAy = calc_vector(bx, by, ax, ay)
    BCx, BCy = calc_vector(bx, by, cx, cy)
    CAx, CAy = calc_vector(cx, cy, ax, ay)
    CBx, CBy = calc_vector(cx, cy, bx, by)

    if BAx * BCx + BAy * BCy < 0 :
        return (BAx * BAx + BAy * BAy)**0.5
    if CAx * CBx + CAy * CBy < 0 :
        return (CAx * CAx + CAy * CAy)**0.5
    
    s = abs(BAx * BCy - BAy * BCx)
    l = (BCx*BCx + BCy * BCy)**0.5
    return s/l

使い方

点(ax, ay)と、線分(bx, by)-(cx, cy)の最短距離を求める場合は、以下のように呼び出します。

点と線分は、()で括って入力しています。この入力にしたのは、x0, y0, x1, y2, x2, y2みたいな引数だと、x0, x1が点だったからx2, y2が点の入力だったかを間違える可能性があるからです（こういうところでミスしたくないので、引数をちょっと工夫しました）

dist = calc_dist((ax, ay), (bx, by, cx, cy))

点がpointじゃなくてdotなのは、なんとなくです。

終わりに

本当にたまにしか使わないけど、使う時には毎回Webで検索して他言語の実装をPythonに書き換えたり、数式から起こしなおしていましたので、今回思い立ったのでライブラリ化してみました。