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

地図上の距離計算に関する質問です。

注目している地点P0(X0,Y0)とN個の地点P1(X1,Y1), P2(X2,Y2), P3(X3,Y3)‥‥Pn(Xn,Yn)があるとします。Xiは緯度(北緯は正数、南緯は負数)、Yiは経度(東経は正数、西経は負数)です。
地点P0から距離Dだけ離れた地点を抽出するための最適なアルゴリズムを教えてください。
サーバに計算させようとしているのですが、P0とPiの点の距離を逐次計算するのでは負荷がかかりそうな気がするので、それ以外の方式でお願いします。


●質問者: pahoo
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:p2 PN X1 X3 アルゴリズム
○ 状態 :終了
└ 回答数 : 7/7件

▽最新の回答へ

1 ● サディア・ラボン
●15ポイント

天文学関係の計算で、球面座標を傾ける計算があります。

赤道座標を黄道座標に変換するなど。


黄経をλ、黄緯をβ、赤経をα、赤緯をδ、黄道傾斜角をεとして、


εをP0からの距離として、P0を北極として、計算すればいいでしょうか。


cosδ・cosα=cosβ・cosλ

cosδ・sinα=-sinβ・sinε+cosβ・sinλ・cosε

sinδ=sinβ・cosε+cosβ・sinλ・sinε


自分でも何を書いてるか解らなくなりました。

◎質問者からの返答

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

いただいた式から大圏コースの距離(長さ)を計算する方法は知っています。しかし、これを1つ1つの地点に対して計算すると、計算量がN数に比例して大きくなるので、何か計算量を減らす方法は無いかと探しています。


2 ● ita
●100ポイント ベストアンサー

ぱっと思い付くのは、地図を緯度・経度によってある大きさのマスで区切って、そのマスの中にある物件のリストを作っておきます。1km四方くらいがいいでしょうか。

次にP0が与えられたら、そこからDkmの円を書いた時にマスの一部でもその中に入る可能性のあるマスを全てリストアップします。P0を含むマスを中心にした(2D+1)x(2D+1)マスでOKでしょう。

この各マスに含まれる物件について実際に距離を計算し、D以下かどうか判定すればいいです。

あまり広い範囲でやるとマスの長さが緯度によって変わってしまいますが、マスを列挙する時に1マスくらい余分にとればOKでしょう。

◎質問者からの返答

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

場合場合に応じ、適当な大きさの「マス」を切るのは妥当なところかもしれません。

そういえば、国土地理院のデータなどでも「メッシュ」という概念が出てきますね。

他の方からのアイデアもお待ちしています。


3 ● zzz_1980
●80ポイント

2点間の距離を求めるのに、メルカトル投影しておいて補正、というアイデアがあるようです。

三角関数は使わなくてすみますが、距離について全数計算する手間は同じですね。

http://d.hatena.ne.jp/hfu/20080128/1201500677

◎質問者からの返答

有用な情報をありがとうございます。

全数計算は同じとしても、三角関数演算が無くなれば、計算量はだいぶ減るのではないかと思います。

また、PostgreSQLならSQL文だけで計算できそう。


4 ● サディア・ラボン
●5ポイント

zzz_1980さんの答えに補足ですが、

正距円筒図法で、cos緯度とcos経度差を使えば計算の量は減ると思います。(やり方は知りません)




JavaScriptやJavaApletは作れませんが、

ホームページを見ている間だけ、訪問者のパソコンの中にプログラムがあって

自分のパソコンを使うと思うので、サーバに負担はかからないと思います。

◎質問者からの返答

> 正距円筒図法で、cos緯度とcos経度差を使えば

具体的な手法を教えていただけないでしょうか。

> 自分のパソコンを使うと思うので

いいえ。レンタルサーバ(共用サーバ)に実装することを想定しています。


5 ● サディア・ラボン
●5ポイント

こんな式を見つけました。


βはP0と北極の距離、

γはP0とPiの距離、

αとPiと北極の距離、

ΑはP0から見たPiの方角、

ΓはP0とPiの経度差。


cosα=cosβ・cosγ+sinβ・sinγ・cosΑ

cosΓ=(cosγ-cosα・cosβ)/(sinα・sinβ)


一番最初に書いた式よりは、計算量が少ないです。

◎質問者からの返答

情報提供をありがとうございます。

たしかに計算量は減りますが、γを求めるためには、α、β、Α、Γのうちからいずれか3つが定まっていならないような気がします。緯度・経度が分かっているので球面三角法により算出は可能ですが、それをやると結局、#1の回答でいただいた式に帰着するような気がします。

計算量が少ないままでγを求める解法がありましたら、お知らせください。


1-5件表示/7件
4.前の5件|次5件6.
関連質問


●質問をもっと探す●



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