2地点間の地理的距離を計算するための迅速な方法

Question

インターネット上のどこかから次の方法を借りました。しかし、2つのGPSポイントの間の距離を見つけることは、まっすぐ進むプロセスを行っている。私は何百万というポイントを超えて走っているので、少し遅いかもしれないことを除いて、それはうまく動作します。 計算コストが安くなる方法を誰かが知っているのだろうかと思いました。

精度は「正しい」一般的な領域にある必要がありますが、100％正確である必要はありません。

private double distFrom(double lat1, double lng1, double lat2, double lng2) { 
    double earthRadius = 3958.75; 
    double dLat = Math.toRadians(lat2-lat1); 
    double dLng = Math.toRadians(lng2-lng1); 
    double a = Math.sin(dLat/2) * Math.sin(dLat/2) + 
      Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) * 
      Math.sin(dLng/2) * Math.sin(dLng/2); 
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
    return earthRadius * c; 
    } 
} 

P.s私は本当に多くの他の関連する質問を見つけましたが、実際には私のスピードの懸念に焦点を当てていません。

Answer 1

あなたは地球のわずかな扁平率を無視してかまわない（とあなたの投稿を半正矢コードはとにかくだけではありません）のすべてを事前変換を検討している場合、あなたの球状（緯度/経度）3D 手段 - 前記座標にその後

http://en.wikipedia.org/wiki/Spherical_coordinate_system

デカルト座標p1と間のあなたの球状の距離：あたりの第一の長さはデカルト座標、は単純である：これは4回の乗算、2つの加算および対ごとに逆トリグ操作に減少単位長さを有するであろう

r * acos(p1 . p2) 

p1のでp2。

また、ドット積の計算は最適化のための理想的な候補です。あなたの目的は、距離によってためペアにある場合など、GPU、MMX拡張、ベクトルライブラリ、経由

さらに、潜在的により遠くのペアを無視して、リストをソートすることにより、式の高価なr*acos()一部を延期することができますあなたはその後、ちょうどあなたが実際に興味を持っている値のacos()を取る

acos(x) < acos(y) if x > y 

再：ちょうど内積値にすべての有効な入力（すなわち範囲[-1, 1]）のためにそれをすることを保証していますので、：ポーacos()を使用した場合の不正確な不正確さを除けば、これらは単精度のfloat変数を使用している場合にのみ重要です。有効数字16桁のdoubleを使用すると、距離が1メートル以内に正確になります。

Answer 2

これはハウバーシンアルゴリズムであり、適切なレベルの精度を提供します。

本当に「何百万」のポイントがある場合は、おそらくあなたが作った計算のキャッシュを実装しています...あなたが距離のあるペアに十分近い、既に計算されている場合は、キャッシュされた値を使用しますか？

また、いくつかの中間ステップをキャッシュしようとします。度をラジアンに変換します。

Answer 3

精度を犠牲にした場合、いくつか改善があります。私が覚えている限り、sin(x)はxのxに等しいapproximatelyです。また、あなたは同じようなことを数回計算しているようです：Math.sin(dLat/2)（実際には上記のようにdLat/2に近似することができます）。

しかし、これらの操作の何百万を行っている場合、私は別の場所にいます。

• アルゴリズムは最適ですか？たぶんあなたはあまりにも多くの簡単な計算をしていますか？

• ポイントがデータベースのものである場合、データベースサーバー側のストアドプロシージャとして計算を実行できますか？

• 最も近いポイントをお探しの場合は、何とかインデックスを作成できますか？

• ジオスペースインデックスは役に立ちますか？

Answer 4

あなたは球面三角法のために余弦定理を試してみてください：

a = sin(lat1) * sin(lat2) 
b = cos(lat1) * cos(lat2) * cos(lon2 - lon1) 
c = arccos(a + b) 
d = R * c 

しかし、それは、（おそらくわずかに速いと）短い距離のために不正確になります。

完全なディスカッションhereがあります。 しかし、haversineの式が最も正しい方法です。だから他の人が示唆していることを除いて、あなたができることはあまりないかもしれません。@アルニタクの答えはうまくいくかもしれませんが、球形からデカルトの変換は必ずしも速いわけではありません。