😀

点と線分の距離を求める

2020/10/27に公開約3,000字2件のコメント

はじめに

任意の点と任意の線分との距離を求めてみましょう。
無限遠に延長されている直線の場合には、直線と直行してかつ指定された点を通る直線との交点を求める方法(指定された点を中心として直線と接する円を求めるのも結局は同じ)で十分ですが、線分の場合には交点が線分内にあるとは限らないので、もうちょっとややこしくなります。

そこで、媒介変数を使った方法を検討してみました。

距離ではなく距離の2乗を求めています

ご指摘を頂くまで気付かなかったのですが、最後にお示ししたスクリプトは距離の2乗を求めるものです。

距離は0以上の数なので、距離の比較と、距離の2乗の比較と同じになりますし、平方根を使うと遅くなる(JavaScriptではあまり遅くないかも知れません、調べていません)ので距離の2乗で計算した方がいいと考えてのことです。

なお、距離の2乗でなく距離そのものが欲しい時には、お示ししたスクリプトで距離の2乗を得て、そこから平方根を計算して距離を得ます。

線分と点との距離

P_1=(x_1,y_1)と点P_2(x_2,y_2)を端点とする線分と点P_0=(x_0,y_0)との距離の二乗を求めます。

線分上の点をP_tとすると、P_t=(at+x_1, bt+y_1) となります。ただし、媒介変数 t0 \le t \le 1 をとります。また、a=x_2-x_1, b=y_2-y_1 です。

P_tP_0との距離の2乗は、tの関数となります。

d2(t) = (at+x_1-x_0)^2 + (bt+y_1-y_0)^2

ここで

\begin{matrix} x_1' &=& x_1 - x_0 \\ y_1' &=& y_1 - y_0 \end{matrix}

とすると、d2(t)は次のようになります。

\begin{matrix} d2(t) &=& (at+x_1')^2 + (bt+y_1')^2 \\ &=& (a^2+b^2)t^2 + 2(ax_1'+by_1')t + (x'^2_1+y'^2_1) \\ &=& (a^2+b^2)(t^2 + 2\frac{ax_1'+by_1'}{a^2+b^2}t) + (x'^2_1+y'^2_1) \\ &=& (a^2+b^2)(t + \frac{ax_1'+by_1'}{a^2+b^2})^2 - \frac{(ax_1'+by_1')^2}{a^2+b^2} + (x'^2_1+y'^2_1) \\ &=& (a^2+b^2)(t + \frac{ax_1'+by_1'}{a^2+b^2})^2 + \frac{-(ax_1'+by_1')^2 + (x'^2_1+y'^2_1)(a^2+b^2)}{a^2+b^2} \\ &=& (a^2+b^2)(t + \frac{ax_1'+by_1'}{a^2+b^2})^2 + \frac{(ay_1'-bx_1')^2}{a^2+b^2} \\ &=& (a^2+b^2)(t + \frac{ax_1'+by_1'}{a^2+b^2})^2 + \frac{(ay_1'-bx_1')^2}{a^2+b^2} \end{matrix}

これをx1, y1で表すと、

d2(t) = (a^2+b^2)(t + \frac{a(x_1-x_0)+b(y_1-y_0)}{a^2+b^2})^2 + \frac{(a(y_1-y_0)-b(x_1-x_0))^2}{a^2+b^2}

最短点をとるときを\overline{t}とすると、

\begin{matrix} \overline{t} &=& -\frac{a(x1-x0)+b(y1-y0)}{a^2+b^2} \\ d2(\overline{t}) &=& \frac{(a(y1-y0)-b(x1-x0))^2}{a^2+b^2} \end{matrix}

となります。

0 \le t \le 1であるので、\overline{t}がこの範囲内に無い場合は、線分を無限遠まで延長した直線上のどこかに最短点が存在することになります。線分を考慮する際、d2(t)は下に凸の二次関数であるので、\overline{t} < 0の時はd2(0)が、\overline{t} > 1の時はd2(1)が、それぞれの距離となります。

\begin{matrix} d2(0) &=& (x_1-x_0)^2 + (y_1-y_0)^2 \\ d2(1) &=& (x_2-x_0)^2 + (y_2-y_0)^2 \end{matrix}

除算を減らす

@kkdd さんからコメントを頂きました。除算を減らした方がベターですので、そのようにします。

\begin{matrix} \overline{t} = -\frac{a(x1-x0)+b(y1-y0)}{a^2+b^2} \\ 0 \le \overline{t} \le 1 \end{matrix}

は、a^2+b^2 \gt 0から、

\begin{matrix} \overline{t'} = -(a(x1-x0)+b(y1-y0)) \\ 0 \le \overline{t'} \le a^2+b^2 \end{matrix}

と置き換えられます。

JavaScriptで書いてみる

function min_d2(x0, y0, x1, y1, x2, y2) {
  var a = x2 - x1;
  var b = y2 - y1;
  var a2 = a * a;
  var b2 = b * b;
  var r2 = a2 + b2;
  var tt = -(a*(x1-x0)+b*(y1-y0));
  if( tt < 0 ) {
    return (x1-x0)*(x1-x0) + (y1-y0)*(y1-y0);
  }
  if( tt > r2 ) {
    return (x2-x0)*(x2-x0) + (y2-y0)*(y2-y0);
  }
  var f1 = a*(y1-y0)-b*(x1-x0);
  return (f1*f1)/r2;
}

本記事のライセンス

クリエイティブ・コモンズ・ライセンス
この記事は クリエイティブ・コモンズ 表示 4.0 国際 ライセンス の下に提供されています。

Discussion

記事について参考にさせていただきました。ありがとうございます。
JavaScriptのコードですが、端点が最短距離になる場合について、最短距離の二乗の値をそのまま返してしまっているように見受けられます。以下がsuggestionです。

if( tt < 0 ) {
  return Math.sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));
}
if( tt > r2 ) {
  return Math.sqrt((x2-x0)*(x2-x0) + (y2-y0)*(y2-y0));
}

コメントありがとうございます。
説明不足でごめんなさい。最後にお示ししているスクリプトは、距離の2乗を返す関数です。
その旨追加しました。

ログインするとコメントできます