線分と点の距離を求めるアルゴリズム
概要
線分 (x0,y0) – (x1,y1) と与えられた点 (px,py)との距離をもとめる。 点から線上に垂線をおろし、その垂線の長さを計れば距離が求まる。
手法
簡単にするため、直線(上の点)は、媒介変数 t を使って (x0+dx*t, y0+dy*t)で表すことにする。 垂線と線分のベクトルの内積が0であることを利用して解をもとめる。
例外
垂線の足 (tx,ty) が線分上になければ、線分の端点(x0,y0) ,(x1,y1)のうち、 垂線の足に近い方の端点から与えられた点までの距離を計れば良い。
手順
dx = x1 - x0; dy = y1 - y0 とする。
-- 線分上の点は (x0+dx*t,y0+dy*t)
線分と垂線のベクトルの内積は .
(dx,dy)・(x0+dx*t-px,y0+dy*t-py)
= (dx^2+dy^2)*t + dx*(x0-px) + dy*(y0-py) である
a = (dx^2+dy^2)
b = dx*(x0-px) + dy*(y0-py)
と置いて
-- a=0 ならば、(x0,y0)-(x1,y1)は線分でなくて点なので、２点間の距離を求めればよい。
t = - b / a
よって垂線の足(tx,ty)は
tx = x0 + dx*t
ty = y0 + dy*t
-- t を 0から1の範囲に丸め込むことにより、
-- 垂線の足が線分からはみ出した時に線分の端点を使用させる事ができる。
点と点の距離 d は
d = √( (px-tx)^2 + (py-ty)^2))
Ruby によるプログラム例
def dist_line_point( x0, y0, x1, y1, px, py)
dx = x1 - x0
dy = y1 - y0
a = dx * dx + dy * dy
return Math.sqrt( (x0-px)*(x0-px) + (y0-py)*(y0-py)) if a == 0.0
b = dx * (x0-px) + dy * (y0-py)
t = - (b / a)
t = 0.0 if t < 0.0
t = 1.0 if t > 1.0
x = t * dx + x0
y = t * dy + y0
return Math.sqrt( (x-px)*(x-px) + (y-py)*(y-py))
end
def do_one( x0, y0, x1, y1, px, py)
d = dist_line_point( x0, y0, x1, y1, px, py)
print "線分(#{x0},#{y0})-(#{x1},#{y1})から点(#{px},#{py})までの距離は#{d}です。\n"
end