点Qから最短距離の点Piを効率的に求めたい

質問

平面上にP1,P2,...,Pnが与えられています。
このとき、任意の点Ｑを与えると、Ｑからの距離の最短の点（等距離の点が複数あれば、そのうちの任意の１点）を返す関数（任意といった時点で数学的には関数でなくなっていますが）が欲しいのです。

単純に考えれば、forループで、全てのPiとの距離を求め、最短のPiを返せば良いのですが、点Ｑが移動する場合、直前のＱに対応するPiである可能性が高いので、もう少し賢いアルゴリズムがある気がします。しかし、具体的なアルゴリズムが思いつきませんので、お知恵をお貸しください。

プログラミングはＣを想定しています。

回答No.4

Situgyosya · ベストアンサー

>確認ですが、求めた最近点が求める点であることを保障するには、
>その最近点とＱの距離が矩形の横幅、縦幅以上の場合には、再度
>矩形を取り直す必要がありますよね。必要ないのかしら？

この場合は、アプリケーションの仕様によると思います。
マウスカーソル等の最近傍をとりたい場合などには、
最長近傍距離LMaxを指定してそれより近い点が無い場合
は「対象点無し」という結果にするのが一般的です。
この場合、矩形の幅と高さはLMax×２にすれば十分です。
どうしてもLMaxを超える点をとりたい場合は、順次矩形
を拡大してやりなおします。

お礼

再度回答ありがとうございます。

私の望むアプリケーションでは、「対象点無し」はなく、少なくとも１点P1は定義されているという条件なので、必ず、最近点を返す必要があります。

点Ｑが原点(0,0)、P1(2,2),P2(3,0)があった場合、最近点はP2ですが、矩形の横幅、縦幅を２で検索する(LMax=2)とP1しか見つかりませんよね。P2を見つけるには、見つかったP1までの距離２√２を矩形の横幅、縦幅にして(LMax =距離QP1) 再度矩形を取りなおす必要があると思い、確認させてもらいました。逆に、P1迄の距離がはじめの矩形の２以下であれば、再確認の必要がないと考えました。これで合ってますよね？

回答No.3

Interest

最短経路計画のアルゴリズムは、調べればたくさん出てくると思いますよ。
グラフ理論を少しかじるといろいろ出てきます。代表的なところでは、

- 深さ優先探索（バックトラック法）：超有名どころ
- ダイクストラ法：経路計画の定番
- A*（えーすたー）アルゴリズム：ダイクストラ法の拡張版

などがあります。これらはすべて数学的に最短経路であることを保証できるアルゴリズムです。あとはググればアルゴリズムそのものが出てると思いますので、ご自身で検索してみてください。

お礼

回答ありがとうございます。
最短距離の点Pi（１点）を求めたいだけですが、これも最短経路計画のアルゴリズムが使えるのでしょうか？
お恥ずかしい話、どうやって使ってよいのかわかりません。
ダイクストラ法を使うとして、使い方が思いつきません。よろしかったら、もう少し具体的に、教えてくださるとうれしいです。

回答No.2

Tacosan

アルゴリズムの立場から言えば, P1～Pn があらかじめ固定されているならそれらのボロノイ図を作っておくのが普通. オーダーは忘れた. ボロノイ図を作るのに O(n log n), 点Q が与えられたときの探索に O(log n) くらいだっけ.

お礼

回答ありがとうございます。
ボロノイ図って言うのですね、勉強不足ではじめて聞きました。
欲しい関数は、ボロノイ図をつくり、領域に番号を振り、点Ｑを与えると点Ｑの属する領域番号を返す関数ということになります。
お陰様で、概念としては整理されましたが、具体的なプログラミングをどうしたらよいのか、やはり判りません。つまり、
・どうやってボロノイ図を作成するのか、
・ボロノイ図はどのような形で記憶させるのか
・関数はそのボロノイ図をどうやって扱って点Ｑの属する領域番号を得るのか
が判らないとプログラミングできません。何かヒントや、参考図書ありましたらご紹介お願いいたします。
もちろん、ボロノイ図で検索しましたが・・・

回答No.1

Situgyosya

Ｑの近傍以外を最初から排除するのが適当だと思います。
距離計算は高コストですが、Ｑを中点とする矩形内に
Piが含まれるかどうかの算定は低コストですみます。
矩形内に見つかった点に対して距離計算し、最近点を
算定します。

別の方法として、Pi群を座標でソートしておくのも
頭のよいやり方です。Ｑ点が移動した場合、直前の
最近点Pnの近くにあるPiをこのソート結果を参考にし
て推定します。
ただし、Ｑの位置が跳躍するとあまり意味がありません。

お礼

回答ありがとうございます。
なるほど、矩形を決めて、その中に入るPiだけ距離計算してその中から最近点を求めるのですね。

確認ですが、求めた最近点が求める点であることを保障するには、その最近点とＱの距離が矩形の横幅、縦幅以上の場合には、再度矩形を取り直す必要がありますよね。必要ないのかしら？

また、ソートする方法も使えそうです。
直面する事例では２次元ですが、将来は３次元以上も考えているのですが、教示いただいた手法は３次元以上でも使えそうで助かります。
ありがとうございます。