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


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

回答の条件
  • 1人5回まで
  • 登録:2008/10/18 10:56:55
  • 終了:2008/10/23 09:40:06

ベストアンサー

id:ita No.2

ita回答回数204ベストアンサー獲得回数482008/10/18 17:55:38

ポイント100pt

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

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

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

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

id:pahoo

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

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

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

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

2008/10/18 19:16:06

その他の回答(6件)

id:Mathusala No.1

サディア・ラボン回答回数259ベストアンサー獲得回数42008/10/18 14:31:09

ポイント15pt

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

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


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


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


cosδ・cosα=cosβ・cosλ

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

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


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

id:pahoo

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

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

2008/10/18 19:13:01
id:ita No.2

ita回答回数204ベストアンサー獲得回数482008/10/18 17:55:38ここでベストアンサー

ポイント100pt

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

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

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

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

id:pahoo

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

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

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

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

2008/10/18 19:16:06
id:zzz_1980 No.3

zzz_1980回答回数492ベストアンサー獲得回数642008/10/18 20:58:58

ポイント80pt

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

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

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

id:pahoo

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

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

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

2008/10/19 08:39:49
id:Mathusala No.4

サディア・ラボン回答回数259ベストアンサー獲得回数42008/10/19 13:16:38

ポイント5pt

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

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




JavaScriptやJavaApletは作れませんが、

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

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

id:pahoo

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

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

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

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

2008/10/19 18:13:28
id:Mathusala No.5

サディア・ラボン回答回数259ベストアンサー獲得回数42008/10/19 23:03:09

ポイント5pt

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


βはP0と北極の距離、

γはP0とPiの距離、

αとPiと北極の距離、

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

ΓはP0とPiの経度差。


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

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


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

id:pahoo

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

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

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

2008/10/20 06:54:40
id:Mathusala No.6

サディア・ラボン回答回数259ベストアンサー獲得回数42008/10/20 16:39:07

ポイント10pt

計算量を減らす方法は思いつきませんでした。



xとyが比例するとして、

最初にxキロメートル以内を入力したら、

P0と緯度差がy以内、経度座がy÷cos(P0の緯度)以内の場所のデータだけを抜き出してから、計算したら、

世界中を計算するよりは遙かに計算量が少なくなります。


四角形の隅の方は無駄になりますし、高緯度だと誤差が大きくなりそうです。

id:pahoo

ありがとうございます。

日本国内で、10km以内の距離という条件だとしたら、有効な最適化手段が出てきそうな予感がします(ita さんのコメント参照)。

2008/10/20 20:45:03
id:Mathusala No.7

サディア・ラボン回答回数259ベストアンサー獲得回数42008/10/20 22:23:49

ポイント40pt

ぼくが答えられるのは今度が最後です。

10キロ程度なら、ほぼ平面と考えていいと思いますので、


P0と緯度差がy以内、経度座がy÷cos(P0の緯度)以内の場所のデータだけを抜き出して作った四角形で

(縦の二乗+横の二乗)の平方根でいいでしょう。

id:pahoo

>10キロ程度なら、ほぼ平面と考えていいと思いますので

そうですね。アドバイスをありがとうございます。

2008/10/23 09:32:20
  • id:zzz_1980
    「距離」は大圏コースでいきますか?
  • id:pahoo
    はい。大圏コースでお願いします。
  • id:webees
    どうもです。(どうやらコメントで確認するのが礼儀になっているようなので、コメント欄で失礼します)

    自分で計算するのも手なのですが、地図情報だったら、Google APIなんかいかがでしょうか。標準化にも役立ちそう。
    http://code.google.com/intl/ja/apis/maps/documentation/reference.html

    ではでは
  • id:pahoo
    GoogleAPIの使い方は承知しています。
    今回はアルゴリズムを探しています。
    標準化していなくても構いません。
  • id:zzz_1980
    どのくらいの精度を要求しているのかわかりませんが、
    マッピングして補正するなら三角関数をテーブルにしてしまえばと思います。
    地球は完全な球体じゃないし。
  • id:pahoo
    テーブル化も有りだとは思うんですが――100メートルの精度を出そうとすると、4万km÷100m=40万で、1象限当たりに絞ったとしても10万個。これがsin, cos の両方に必要として、計20万個になりますかね。64ビット倍精度として1.5Mバイトですか――うん。それほど巨大な代物ではないですね。
  • id:ita
    sin, cos を節約するなら、こういう方法も。
    まずPiを全て球面上の三次元座標Qi=(xi,yi,zi) に変換して持っておきます。

    P0が与えられたらこれも三次元 Q0に変換。
    次にQ0 とQi の距離の二乗を計算。これは単純に三平方。こういう場合の定石としてSqrtはとらない。
    地球の半径をRとすると、距離の二乗が 4R^2 sin^2 (D/2R)以下ならば球面上の距離がD以下。
  • id:pahoo
    > 全て球面上の三次元座標Qi=(xi,yi,zi) に変換して持っておきます
    なるほど。平面法で近似できるほど距離が近ければ、これは現実的かもしれませんね。
  • id:pahoo
    多くのアイデア、アドバイスをありがとうございました。
    次のような手順で計算しようと思います。

    1.あらかじめ地点Piの平面座標(X,Y)をDBに登録しておく。(高度は無視)
    2.地点PiがP0を中心とする範囲円に外接する正方形の中にあるかどうか調べる。(X,Y)の引き算だけで可能。
    3.正方形の中にあるPiについて、
    (a)正方形の大きさが十分に小さければ、ピタゴラスの定理で直線距離を求める。(二乗計算を行う)
    (b)(a)以外については、球面三角法で大圏コースの長さを求める。(三角関数の計算が必要)

    また何か疑問が発生しましたら、よろしくお願いします。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません