線分と点の距離

=== 線分と点との距離を求めるアルゴリズム。
あ
( * は乗算 ^ はべき乗とする)

==== 概要
線分 (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

do_one( 0.0, 0.0, 10.0, 20.0,   10.0, 0.0)



=== ご意見

== please don't delete this line. ==