人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

それぞれ異なる地点(緯度・経度)がおよそ5000あります(点A群とします)。
この時、点A群の中から任意に指定された地点に最も近い地点を求めるにはどのような方法が最も効率的か教えてください(数学的概念を用いて説明される場合は数学IIBレベルを履修した程度の人にもわかるように説明してください)

なお、提示した方法を実現するプログラムコード、もしくはそれが書かれたURLを示していただければなお助かります。

●質問者: leva
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:URL コード プログラム レベル 数学
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● zzz_1980
●50ポイント

任意に指定された点から、すべての点(点A群)に対する距離を球面三角法の余弦定理を利用して計算し結果の中からもっとも差分(距離)が小さいものを選択する。

球面三角法余弦定理の実装は、以下に。(説明は非ユークリッド幾何学の世界なので数?Bでは無理)

「小さいものを選択」は単純にソートすればいいのでそのアルゴリズムについては省略。

ようは、全数計算が必要、ということです。

#include <math.h>

#define deg2rad(x) (2.0*M_PI*x/360.0)

#define XXXX (40064.5)

double distance(x1,y1,x2,y2)

double x1,y1,x2,y2;

{

return XXXX/2/M_PI*acos(sin(deg2rad(x1))*sin(deg2rad(x2))+cos(deg2rad(x1))*cos(deg2rad(x2))*cos(deg2rad(y1)-deg2rad(y2)));

}

参考 http://q.hatena.ne.jp/1224295223

◎質問者からの返答

参考リンク先も含め、理解できるところまで読んでみました。

同じ質問をされている方がいたのですね(http://q.hatena.ne.jp/1224295014)

2点間の大圏距離を求める方法は公式として掴んではいたのですが、

やはり全数計算が必要なのですか。

今回はquestion:1224295014のように方法そのものよりもサーバ上で動作させるにあたって、いかに負荷を減らしてレスポンスを早めるかかという点に着目しています。

ですが、試しに球面三角法で大圏距離を求める方法をPHPとして実装しているページがありましたので、こちらを参考に全数計算してみたところ(緯度・経度は乱数生成)

およそ0.05秒程度で実行できました。

http://www.yamareco.com/weblog/archives/2007/02/gps2.html

全数計算は負荷が高いかと思っていましたが、案外実用的で安心しました。

緯度・経度を引き算したり、メッシュで分けたりして候補を絞り込むことも

考えていましたが、テスト段階ではまだそこまですることもなさそうです。

http://www.kanzaki.com/docs/sw/geoinfo.html#geo-dist


2 ● m&M
●10ポイント

なぜかと聞かれると答えられませんが、それは、最短シュタイナー問題の解ではないでしょうか?

『最短シュタイナー問題』解答

http://web2.incl.ne.jp/yaoki/ams.htm

◎質問者からの返答

読みました、でも今回求めているものとは違うのではないかと。

仰っている最短シュタイナー問題の解は「正n角形の中に点を取り、各点と各頂点の距離の総和が最短になるような点に対する解」であると理解しましたが、それと今回の問いとはどうもかみ合いません。

私の理解不足であるようでしたら、コメントでお返事をください。


3 ● jo_30
●50ポイント ベストアンサー

点がある偏りを示す(たとえばA群の点が、その存在範囲の周縁部分に偏っているとか、あるいは存在範囲の全体が帯状である、など)であれば、全数計算する他無いと思いますが、その場合は『平面上の二点間の距離』の公式に基づき『(始点A(x1,y1)から終点B(x2,y2)間の距離ABは)AB=√(x2-x1)^2+(y2-y1)^2』で数値を出せば良いのでは。遅くても、シンプルな操作で常に100%正確な結果が必要なら、これで。


で、点が偏っていない場合、効率化を考えるなら単純に座標で絞り込みをかけるのはどうですか?


まずA群に属する全ての点は、緯度経度によって座標化されていると考えて良いですね。で、とりあえず点A群がある場所を100×100の正方形に入れてみると、(つまり存在範囲を仮想的に10000に分割すると)5000個の点が理想的にばらけている場合、仮想の面積1に対して点がある確率は1/2と考えられ、実用を考えれば面積が10あれば99%以上の確率でその中に一つは点があることを期待出来ます。ここでたとえば半径2の円を想定すると、面積は12を越えます。そしてその円は当然ながら4×4の正方形の中にすっぽり収まりますね。つまり100分割した場合1単位がいくつになるか計算して、その2倍の数値をx軸、y軸方向に+?で延長した範囲内の正方形内を調べれば実用上は充分ということです(半径2の円内に点がない確率は、約4000分の1)。


従って、A群に属する点が理想的にばらけていると期待出来るなら、点A群(A0?A5000)の存在する範囲を100×100に割って、点Bを中心にした半径2の円が最低スッポリと入る正方形…すなわち点Bの座標からX,Yともにその前後2程度の差の範囲内にある点をあらかじめ探し、その後範囲内のいくつかの点Anと任意の点Bの距離をざっと計算させ、その結果を出力すれば良いのではないかと思います。実際にはA群の点の存在場所に偏りがあるでしょうし、円と正方形の形のズレからそのパラメータを自由に指定出来るようにプログラムした方がよいでしょうけれども。


具体的には

・変数定義

・点Bの座標を入力

・パラメータCを入力(1から5まで。デフォルト値は2とする。1だと計算が速いが、見つからなかったり不正確である可能性も考慮する必要がある。)


・A群データから点BのX座標の前後Cの値(×1単位)の範囲のデータを抽出(D群)

・D群データから点BのY座標の前後Cの値(×1単位)の範囲のデータを抽出(E群)

・E群が=φ(データがない)ならばパラメータ入力(3行目)に戻る。あれば次へ。

--------------------------------------------------------------

・E群の全データに対して値e√(x2-x1)^2+(y2-y1)^2を計算


・E群を値e基準で並べ替え、先頭(最小)のデータAnを返す。

・Anを結果として表示し、Anの値eを併せて表示

・終了

みたいな流れで処理すれば、それなりに効率化できると思います。


あるいは、少し複雑になりますが、パラメータ入力を省略しかつ100%正確な値を自動で出すなら、パラメータを0.5あたりから自動でスタートしてAnを探すようにし、見つかればそのe値(≠0)を求め、次にその際のパラメータを√2倍して結果を求め、それでもe値(≠0)が変わらなければそれを最終結果として出力、変わった場合は変わった後の方の値を最終結果として出力、という風にすればよいと思います。

(理由は、上の方法だとe値を求める範囲が円でなく正方形なので、その正方形(α)に外接する円(β)の中に正方形(α)の端よりも中心に近い点Anが存在する可能性を否定できないからです。それを確認するためにその円(β)にさらに外接する正方形(γ)を想定し、上の手順を繰り返すわけです。この場合、新たな正方形γの一辺は最初の正方形αの辺の√2倍の長さを持つので(説明は略します)パラメータを√2倍してやればよいということになります。その結果新たにより近い点が見つかればそちらの方が正解と特定できます。)

◎質問者からの返答

実に論理的に丁寧な回答で感服いたしました。おかげさまで非常にわかりやすかったです。

全区域を10000分割し、A群の各点に0-10000の区域番号をつけた上で、任意の点の近似区域を求めることで候補を絞り込むというわけですか。なるほど、確かにこれだとほとんど計算を行わずにすみますね。

なんとなく考えてはいましたが、ここまで詳しく書いていただければ実装まで持っていけそうです。現在の所、球面三角法による全数計算でもなんとかなりそうですが(ただ、質問の意図からするとこの絞り込みが最も的確かと思います)、この場合は点A群の数に比例して処理時間が延びてしまうので、スケーラビリティを考えて、この解決策を採ることも考えておこうと思います。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ