![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?8acaa2e)
平面上にP1,P2,...,Pnが与えられています。
このとき、任意の点Qを与えると、Qからの距離の最短の点(等距離の点が複数あれば、そのうちの任意の1点)を返す関数(任意といった時点で数学的には関数でなくなっていますが)が欲しいのです。
単純に考えれば、forループで、全てのPiとの距離を求め、最短のPiを返せば良いのですが、点Qが移動する場合、直前のQに対応するPiである可能性が高いので、もう少し賢いアルゴリズムがある気がします。しかし、具体的なアルゴリズムが思いつきませんので、お知恵をお貸しください。
プログラミングはCを想定しています。
No.4ベストアンサー
- 回答日時:
>確認ですが、求めた最近点が求める点であることを保障するには、
>その最近点とQの距離が矩形の横幅、縦幅以上の場合には、再度
>矩形を取り直す必要がありますよね。必要ないのかしら?
この場合は、アプリケーションの仕様によると思います。
マウスカーソル等の最近傍をとりたい場合などには、
最長近傍距離LMaxを指定してそれより近い点が無い場合
は「対象点無し」という結果にするのが一般的です。
この場合、矩形の幅と高さはLMax×2にすれば十分です。
どうしてもLMaxを超える点をとりたい場合は、順次矩形
を拡大してやりなおします。
再度回答ありがとうございます。
私の望むアプリケーションでは、「対象点無し」はなく、少なくとも1点P1は定義されているという条件なので、必ず、最近点を返す必要があります。
点Qが原点(0,0)、P1(2,2),P2(3,0)があった場合、最近点はP2ですが、矩形の横幅、縦幅を2で検索する(LMax=2)とP1しか見つかりませんよね。P2を見つけるには、見つかったP1までの距離2√2を矩形の横幅、縦幅にして(LMax =距離QP1) 再度矩形を取りなおす必要があると思い、確認させてもらいました。逆に、P1迄の距離がはじめの矩形の2以下であれば、再確認の必要がないと考えました。これで合ってますよね?
No.3
- 回答日時:
最短経路計画のアルゴリズムは、調べればたくさん出てくると思いますよ。
グラフ理論を少しかじるといろいろ出てきます。代表的なところでは、
- 深さ優先探索(バックトラック法):超有名どころ
- ダイクストラ法:経路計画の定番
- A*(えーすたー)アルゴリズム:ダイクストラ法の拡張版
などがあります。これらはすべて数学的に最短経路であることを保証できるアルゴリズムです。あとはググればアルゴリズムそのものが出てると思いますので、ご自身で検索してみてください。
回答ありがとうございます。
最短距離の点Pi(1点)を求めたいだけですが、これも最短経路計画のアルゴリズムが使えるのでしょうか?
お恥ずかしい話、どうやって使ってよいのかわかりません。
ダイクストラ法を使うとして、使い方が思いつきません。よろしかったら、もう少し具体的に、教えてくださるとうれしいです。
No.2
- 回答日時:
アルゴリズムの立場から言えば, P1~Pn があらかじめ固定されているならそれらのボロノイ図を作っておくのが普通. オーダーは忘れ
た. ボロノイ図を作るのに O(n log n), 点Q が与えられたときの探索に O(log n) くらいだっけ.回答ありがとうございます。
ボロノイ図って言うのですね、勉強不足ではじめて聞きました。
欲しい関数は、ボロノイ図をつくり、領域に番号を振り、点Qを与えると点Qの属する領域番号を返す関数ということになります。
お陰様で、概念としては整理されましたが、具体的なプログラミングをどうしたらよいのか、やはり判りません。つまり、
・どうやってボロノイ図を作成するのか、
・ボロノイ図はどのような形で記憶させるのか
・関数はそのボロノイ図をどうやって扱って点Qの属する領域番号を得るのか
が判らないとプログラミングできません。何かヒントや、参考図書ありましたらご紹介お願いいたします。
もちろん、ボロノイ図で検索しましたが・・・
No.1
- 回答日時:
Qの近傍以外を最初から排除するのが適当だと思います。
距離計算は高コストですが、Qを中点とする矩形内に
Piが含まれるかどうかの算定は低コストですみます。
矩形内に見つかった点に対して距離計算し、最近点を
算定します。
別の方法として、Pi群を座標でソートしておくのも
頭のよいやり方です。Q点が移動した場合、直前の
最近点Pnの近くにあるPiをこのソート結果を参考にし
て推定します。
ただし、Qの位置が跳躍するとあまり意味がありません。
回答ありがとうございます。
なるほど、矩形を決めて、その中に入るPiだけ距離計算してその中から最近点を求めるのですね。
確認ですが、求めた最近点が求める点であることを保障するには、その最近点とQの距離が矩形の横幅、縦幅以上の場合には、再度矩形を取り直す必要がありますよね。必要ないのかしら?
また、ソートする方法も使えそうです。
直面する事例では2次元ですが、将来は3次元以上も考えているのですが、教示いただいた手法は3次元以上でも使えそうで助かります。
ありがとうございます。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) Pythonでの不均一なサイコロをつくるプログラミングがわかりません 4 2022/06/07 13:10
- 数学 x軸上にN+1個の点P0, P1, … , PNがある。 P0は0から1の間、PiはP(i-1)と1 2 2023/04/07 16:23
- 高校 数Ⅱの軌跡という単元について質問です。 問題の最後に、逆に、この~上の全ての点は条件を満たすとかく場 3 2023/03/21 16:38
- 数学 数学得意な方教えてください 平面上の任意の点から同一平面上にある多角形の各頂点までの距離の平均は、多 1 2023/08/28 16:36
- 物理学 焦点距離40cmの凸レンズから距離60cm離れた場所に、光軸に対して垂直な高さ10cmの棒が立ってい 2 2022/10/16 21:13
- 統計学 連続型の確率変数について 6 2023/08/25 08:44
- 物理学 写真の問題についての、 写真の赤枠で囲ってある部分の「衝突の時間間隔は公比eの等比数列をなす」と書い 2 2022/08/01 23:23
- その他(悩み相談・人生相談) 数学IIの問題で、 2点(5.0)(-3.0)に対して、距離APが距離BPの3倍である点Pの軌跡を求 3 2023/05/04 11:45
- 数学 数学 軌跡の問題で2点から等しい距離にある点の軌跡を求めるので三平方の定理を使うのですが、求める点の 4 2023/02/10 21:26
- デジタルカメラ レンズの焦点距離(専門家への質問) 3 2022/10/06 11:14
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
アルゴリズムとプロトコールの違い
-
期間重複チェックがわかりません
-
一般的な解法を用いないで魔法...
-
ドロネー三角形のプログラム
-
六曜の自動計算について
-
アルゴリズムの説明について
-
BCDについて
-
フリーのCOBOL作成?ソフト
-
5人のテストの点数を入力すると...
-
連立方程式を解く
-
opencvの関数の中身をみること...
-
点Qから最短距離の点Piを効率的...
-
スキップリスト(データ構造)の...
-
65536は2の何乗なのでしょうか?
-
あるプログラムのコマンドライ...
-
0除算して、落ちるプログラムと...
-
Excelに埋め込んだVBAのプログ...
-
VBAで仕様書は書きますか?
-
CPUが16bitでも32bitOSでコンパ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
アルゴリズムとプロトコールの違い
-
BCDについて
-
[ EXCEL VBA ] 図形を読み込む...
-
Stuck
-
グループを均等に分けるには?...
-
画像から文字を認識してテキス...
-
Dijkstraて
-
期間重複チェックがわかりません
-
多変数関数の最小値を求めるプ...
-
JPEG圧縮で8×8に分割する理由に...
-
OpenCVのライセンスについて
-
データを圧縮したい
-
ルービックキューブを揃えるた...
-
5人のテストの点数を入力すると...
-
C♯で電卓を作成しています。演...
-
ドロネー三角形のプログラム
-
vbaで、連立方程式を解く方法に...
-
動画で間違ったこと言っている
-
オンラインゲームのオートラン...
おすすめ情報