それぞれ異なる地点(緯度・経度)がおよそ5000あります(点A群とします)。

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

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

回答の条件
  • 1人3回まで
  • 登録:2008/10/19 21:09:51
  • 終了:2008/10/20 05:00:53

ベストアンサー

id:jo_30 No.3

jo_30回答回数655ベストアンサー獲得回数532008/10/20 03:54:54

ポイント50pt

点がある偏りを示す(たとえば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倍してやればよいということになります。その結果新たにより近い点が見つかればそちらの方が正解と特定できます。)

id:leva

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

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

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

2008/10/20 04:55:16

その他の回答(2件)

id:zzz_1980 No.1

zzz_1980回答回数492ベストアンサー獲得回数642008/10/19 22:42:20

ポイント50pt

任意に指定された点から、すべての点(点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

id:leva

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

同じ質問をされている方がいたのですね(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

2008/10/20 04:43:35
id:mskitta No.2

m&M回答回数25ベストアンサー獲得回数42008/10/19 22:42:31

ポイント10pt

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

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

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

id:leva

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

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

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

2008/10/20 01:45:59
id:jo_30 No.3

jo_30回答回数655ベストアンサー獲得回数532008/10/20 03:54:54ここでベストアンサー

ポイント50pt

点がある偏りを示す(たとえば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倍してやればよいということになります。その結果新たにより近い点が見つかればそちらの方が正解と特定できます。)

id:leva

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

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

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

2008/10/20 04:55:16
  • id:zzz_1980
    何でこっちでも2点間の距離?
  • id:jo_30
    すいません…私の理解の間違いでなければ、要するにたとえば『地図上に5000のコンビニがあるとして、地図の中の任意の場所から一番近いコンビニまでの距離を求める』みたいな問題ではないのでしょうか?
  • id:leva
    >id:jo_30さん
    そうですね。具体的にイメージしているものもそういうものです。
    何か良い解決策はありますかね?
  • id:jo_30
    一応書いてみましたが、所詮私も文系なので実はあまり自信がありません。ご満足いただけない回答だった場合は、開封ポイントお返しさせていただきますm(__;)m
  • id:leva
    参考までに、今回使用したテストプログラム(PHP)を公開しておきます。
    calculateBySphereメソッドはリンク先(http://www.yamareco.com/weblog/archives/2007/02/gps2.html)から拝借したものです。
    急ぎで書いたので汚いですが、ご容赦ください。

    <?php

    $n = 5000;

    for ($i=0; $i<$n; $i++){
    $p1[] = array(rand(20,40).".".sprintf("%06d", rand(1,999999)), rand(90,150).".".sprintf("%06d", rand(1,999999)));
    $p2[] = array(rand(20,40).".".sprintf("%06d", rand(1,999999)), rand(90,150).".".sprintf("%06d", rand(1,999999)));
    }

    $time[] = getmicrotime();
    for ($i=0; $i<$n; $i++){
    calculateBySphere((double)$p1[$i],(double)$p1[$i+1],(double)$p2[$i],(double)$p2[$i+1]);
    }
    $time[] = getmicrotime();

    $time[] = getmicrotime();
    for ($i=0; $i<$n; $i++){
    refine((double)$p1[$i],(double)$p1[$i+1],(double)$p2[$i],(double)$p2[$i+1]);
    }
    $time[] = getmicrotime();

    echo $time[1] - $time[0];
    echo "<br />";
    echo $time[3] - $time[2];

    function calculateBySphere($x1, $y1, $x2, $y2){
    $x1 = pi()*$x1/180;
    $x2 = pi()*$x2/180;
    $y1 = pi()*$y1/180;
    $y2 = pi()*$y2/180;
    $x1 = $x1-((11.55/60)*pi()/180)*sin(2*$x1);
    $x2 = $x2-((11.55/60)*pi()/180)*sin(2*$x2);
    $c = cos($x1)*cos($x2)*cos($y1-$y2)+sin($x1)*sin($x2);
    $s = sqrt(1-$c*$c);
    $t = $s/$c;
    $z = atan($t);
    $z = 6378.137*$z;
    return false;
    }

    function refine($x1, $y1, $x2, $y2){
    $dx = $x2 - $x1;
    $dy = $y2 - $y1;
    return false;
    }

    function getMicrotime(){
    list($msec, $sec) = explode(" ", microtime());
    return ((float)$sec + (float)$msec);
    }

    ?>
  • id:leva
    2点間距離を求める方法自体は回答を参照しつつ、最終的に以下のような関数に落ち着きました。

    <?php

    define("EARTH_RADIUS", 6378.137);
    define("METER_PER_LAT", 110880);
    define("METER_PER_LNG", 90360);

    // 三角球面法より大圏距離(m)を求める(地球=真球として処理)
    function calculateBySphere($x1, $y1, $x2, $y2){

    return 1000 * EARTH_RADIUS *
    acos(sin(deg2rad($x1)) * sin(deg2rad($x2)) +
    cos(deg2rad($x1)) * cos(deg2rad($x2)) *
    cos(deg2rad($y1) - deg2rad($y2)));

    }

    // 三平方の定理より平面上の直線距離(m)を求める
    function calculateByFlat($x1, $y1, $x2, $y2){
    $dx = pow((($x2-$x1)*METER_PER_LAT),2);
    $dy = pow((($y2-$y1)*METER_PER_LNG),2);
    return sqrt($dx+$dy);
    }
    ?>
  • id:yamadakouzi
    yamadakouzi 2008/10/20 22:41:31
    皆さん、難しい事を書いておられますが、全数検査もソートも必要ないじゃありませんか。
    まず、①任意の指定ポイントの緯度、経度に近いポイントだけ候補にします(緯度と経度は少し計算方法が異なりますが、簡易計算で)そして候補ポイントを100分の1くらいにします。②次に候補ポイントと指定ポイントの距離を球面三角法でも(何でも良い)で計算して、変数MINより小さければその値に入れかえる(初期値はありえないほど大きな数値)ついでにそのポイント番号も入れ替える(初期値はポイントに無い番号)
    ③ ②を繰り返し候補ポイントが無くなれば、④ポイント番号とその座標を引き出す。--->終わり

    全数検査(距離を計算)とソート(効率の悪いバブルソート)をした場合、距離計算がN(地点数)に比例、ソートがNxNに比例します。例えば地点数がn倍になった時はn*a0+n^2*b0

    しかし上記に示した方法だと、n*c+n/100*a1+n/100*b1(a0,a1,b0,b1,cは計算速度の係数)となり
    各係数の大きさ、オーダーによりますが、確実に速いと思います。---余計なけいさんはしない!!
  • id:yamadakouzi
    yamadakouzi 2008/10/20 22:53:54
    近い候補ポイントの絞込み、及び実際に近いポイントを求める時は球面三角法を使わなくてもlevaさんの回答のように「三平方の定理』で十分です。それは同一球面上の2点間の距離の大小は直線距離でも同じ関係になる。
    これなら、数学部分は中学生程度で十分でしょう。

    ちなみに「最短シュタイナー問題」とは無関係でしょう。
  • id:leva
    >id:yamadakouziさん
    それも考えていました。しかし、1の候補絞り込みの過程で(小学生レベルの引き算であったとしても)全数計算が必要になると思っていたんです。その過程で球面三角法の1/2程度の時間がかかっていたので、結局そうは変わらないんじゃないかと。

    しかし、よくよく考えてみるとわざわざSQLからデータを引っこ抜いてから計算しなくても、単純にSQL文での数値比較で候補を絞り込めますね。つまり、全点を処理するのではなく、30km以内の地点だけ計算するというような感じでしょうか。

    なるほど、頭がスッキリしました。どうも。
  • id:murakami_tak
    後出しジャンケンですいません。
    点A群がある程度均等に分布しているなら,領域を碁盤の目のようなセルに分割してやる方法を僕ならとります。

    事前に全点間の距離を出しておき,その最大値を MaxDist とします。
    で,点i(iX,iY)のセルの番号は CellXi = int(iX / MaxDist), CellYi = int(iY / MaxDist)とかで求めて,Cell[CellXi][CellYi]にiをプッシュします。この作業を全点で事前にやっておきます。

    任意に指定された点(jX,jY)が与えられれば,セル番号を同じようにCellXj,CellYjとして求めて,X方向はx=CellXj-1~CellXj+1,Y方向はy=CellYj-1~CellYj+1について,Cell[x][y]に入っている点番号のみに対して距離比較をすれば良いと思います。

    点A群がほぼ等間隔で並んでいたら効率よいのですが…。すごく片寄っているとMaxDistが大きくなって,非効率になります。ま,何かの参考になれば。

    あと余談ですが,最近接の点を探すだけなら三平方の定理のsqrtを計算しなくてもルートの中身を比較するだけでOKですよ。

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

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

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

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