点と折れ線との間の距離を求める

質問

点と折れ線との間の最短距離を求めたいのですが、そういうライブラリ（できればソースの読めるもの）やアルゴリズムなど何処かにないでしょうか？

回答No.7

kabaokaba

線分と直線の違いは数学的には結構本質．
(0,0)と(1,0)を両端とする線分Lとx軸と
点A(2,0)を考える．
さて，AからLまでの距離，Aからx軸までの距離
どう考えます？

線分を相手にするときには「直線相手の公式」は使えないから
もっと根本にもどって，AからL上の点まで「距離」の中から
最小の値をとる点を探すことになります．

(a,b),(c,d)を両端とする線分上の任意の点(x,y)は
(x,y)=(1-t)(a,b)+t(c,d) (0<=t<=1)で表せる．
今点(A,B)をとって(A,B)からその線分の点までの距離d(t)を考えると
d(t)^2 = ((1-t)a+tc-A)^2 + ((1-t)b+td-B)^2だから
これの最小値を求めればよい．
ただし「0<=t<=1」で．これがめんどくさい．
＃数学的には高校一年生程度の問題だが計算が面倒

じゃどうするか．今度は
(a,b),(c,d)を両端とする「直線」を相手にして
一度，その直線まで(A,B)から垂線を下ろし，その垂線の足をHとする．
Hが線分上にあれば(A,B)とHまでの距離が線分までの距離
Hが線分上になければ，
・Hを(1-t)(a,b)+t(c,d)の表記で書いたときに t>1であれば(A,B)と(c,d)の距離が求める距離
・t<0であれば(A,B)と(a,b)の距離が求める距離
くらいの手数になるか．

＞その点が移動するたびに最短距離を計算しなければならない場合に、再計算の大半が無駄な計算をしているような気がしたということです。

さて。。なぜ無駄と思います？
点を移動したら当然値が変わるのだから再計算は必要です．
どこまで「正確さ」を求めるか，計算コストなどとの
トレードオフも当然あります．
その移動量や線分の形態などいろいろな条件があります．
もちろんいくつかの「節約方法」はあります．

・「解像度」を粗く考える方法
本来ならば1ピクセル単位で考えるのを例えば，16x16ピクセル
（これはわざと大きくしてますよ，念のため）を
一点だと思って，その範囲でのマウス移動は無視する

・各点ごとの結果をキャッシュしておく．
同じ点の値を複数回計算しないように
一度計算したらその値を保存しておき，
二回目以降は同じ計算をしない
折れ線も変化するならば折れ線の情報も考慮しないと当然だめ

・折れ線を構成する各線分の位置関係を考慮しておき，
ある点からの距離が分かり，
移動した後の点がそれほど離れていないならば
遠くの線分を再計算対象には含めない

これくらいの工夫は考慮すべきでしょう．

お礼

その後改良しまして、ABとACとの内積と、BAとBCとの内積とを調べ、必要な場合のみ垂点との距離を求めることにしました。

補足

回答有難うございます。
>・折れ線を構成する各線分の位置関係を考慮しておき，...
　この最後の点の具体的方法を知りたい、というのが質問の趣旨でした。
　こだわっている方がいらっしゃるようなので念のため、線分ABと点Cとの距離を求めるアルゴリズムは自分としては以下のように実装しました。
　1) 直線ABへCから下ろした垂線との交点をDとすると、ベクトルADは
ベクトルABのスカラー倍となるからこの倍数をαとする。
　2) 0<α<1の場合、最短距離はCとDとの距離
　3) それ以外の場合、線分ABの両端点とCとの距離をそれぞれに求めて近い方 を最短距離とする。