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

質問

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

回答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との距離をそれぞれに求めて近い方 を最短距離とする。

回答No.6

asuncion

> 再計算の大半が無駄な計算をしているような気がしたということです。

それは、おそらく気のせいでありましょう。
ところで、「距離」の定義に関する質問にはお答えいただけないのでしょうか？

回答No.5

asuncion

念のため「距離」の定義を確認します。
折れ線を構成する線分のひとつが
(0, 0)と(1, 0)とを結ぶものであるとします。
また、距離を求めたい点の座標を(2, 1)とします。
この場合の距離はいくらですか？

補足

少し言葉が足りなくて申し訳ありませんでした。距離を求める計算が無駄というのではなく、点がそれほど遠くへ一気に移動しないことが多い（マウスポインタのように）ケースで、その点が移動するたびに最短距離を計算しなければならない場合に、再計算の大半が無駄な計算をしているような気がしたということです。
　よろしくお願いします。

回答No.4

asuncion

> 線分との距離をひとつひとつ処理すればできるのは分かっているですが、
> 線分の数が多い場合にその計算の大半が無駄なような気がしまして、

距離をすべて求めなければ、どれが最短距離かはわからないですよね。
ムダな計算は一つもないと思います。
たまたま、計算結果の中から一つだけを選んでいるに過ぎないのです。

回答No.3

asuncion

> 「直線」ではなくって「線分」でしょう＞#1.

用語の使い方が正しくなかった点はお詫びいたします。
今回の問題の本質的なところではないにしても。

# 直線でも線分でも、そんなの関係ねえ。

補足

解答いただき有難うございます。線分との距離をひとつひとつ処理すればできるのは分かっているですが、線分の数が多い場合にその計算の大半が無駄なような気がしまして、もっと計算量を減らすことができるようなうまいアルゴリズムなどないのかなと思って質問させて頂きました。
　よろしくお願いします。

回答No.2

Tacosan

「直線」ではなくって「線分」でしょう＞#1.
「線分」になっている分だけ難しくなりますが, 「点と線分との距離」を求めるルーチンを 1つ作っておくだけです.

回答No.1

asuncion

折れ線ということは、複数の直線群ですね。
１点目と２点目とで１本目の直線、
２点目と３点目とで２本目の直線、以下同様
のような。

まずは、点と１本の直線との距離を求めるところから
始めてみてはいかがでしょうか。
それができたら、２本目、３本目、．．．に拡張して、
最小値を求めれば、問題が解決すると思います。