8

私のコードでは、緯度/経度の値のペア間で多くの距離計算を行う必要があります。

コードは次のようになります。

double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) 
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad));

（lat2radは、たとえば緯度をラジアンに変換したものです）。

この機能をアプリケーションのパフォーマンスのボトルネックとして特定しました。これを改善する方法はありますか？

（座標が変化しているため、ルックアップテーブルを使用できません）。グリッドのようなルックアップスキームが提案されているこの質問も調べましたが、これは可能性があるかもしれません。

御時間ありがとうございます！;-)

4

12 に答える 12

5

目標が距離のランク付け (比較)である場合、近似 (sinおよびcosテーブル ルックアップ) により、必要な計算量を大幅に削減できます (クイック リジェクトを実装します)。

目標は、(ランク付けまたは比較される) 近似距離の差が特定のしきい値を下回った場合にのみ、実際の三角法の計算を続行することです。

たとえば、1000 サンプルのルックアップ テーブルを使用すると (つまりsin、cosごとにサンプリングされる2*pi/1000)、ルックアップの不確実性は最大で 0.006284 になります。パラメータ to の不確実性計算を使用するACosと、累積された不確実性は、しきい値の不確実性でもあり、最大で 0.018731 になります。

したがって、 2 つの座標セットのペア (距離) の参照テーブルをMath.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad)使用しsinて評価するとcos、特定のランキングが得られ (近似に基づいて一方の距離が他方よりも大きく表示される)、差のモジュラスが上記のしきい値よりも大きい場合、近似は次のようになります。有効。それ以外の場合は、実際の三角法の計算に進みます。

于 2009-03-05T15:48:44.410 に答える
4

CORDICアルゴリズムは (速度/精度に関して) うまくいきますか?

于 2009-03-05T15:31:31.630 に答える
3

@Brann からのインスピレーションを使用して、計算を少し減らすことができると思います (これを行ってから長い時間がかかるため、検証する必要があることに注意してください)。ただし、事前に計算された値のある種のルックアップはおそらく最速です

あなたが持っている ：

1: ACOS( SIN A SIN B + COS A COS B COS(AB) )

ただし 2: COS(AB) = SIN A SIN B + COS A COS B

SIN A SIN B = COS(AB) - COS A COS B

SIN A SIN B を 1 に置き換えます。

4: ACOS( COS(AB) - COS A COS B + COS A COS B COS(AB) )

X = COS(AB) と Y = COS A COS B を事前に計算し、値を 4 に入れます。

与える：

ACOS( X - Y + XY )

6 ではなく 4 つの三角関数の計算!

于 2009-03-05T15:54:30.497 に答える
2

経度/緯度の保存方法を変更します。

struct LongLat
{
  float
    long,
    lat,
    x,y,z;
}

経度/緯度を作成するときは、原点を中心とする単位球上の同等の位置を表す (x,y,z) 3D ポイントも計算します。

ここで、ポイント B がポイント C よりもポイント A に近いかどうかを判断するには、次の手順を実行します。

// is B nearer to A than C?
bool IsNearer (LongLat A, LongLat B, LongLat C)
{
  return (A.x * B.x + A.y * B.y + A.z * B.z) < (A.x * C.x + A.y * C.y + A.z * C.z);
}

2 点間の距離を取得するには:

float Distance (LongLat A, LongLat B)
{
  // radius is the size of sphere your mapping long/lats onto
  return radius * acos (A.x * B.x + A.y * B.y + A.z * B.z);
}

「半径」という用語を削除して、距離を効果的に正規化できます。

于 2009-03-05T16:05:59.363 に答える
1

sin/cos/acos のルックアップ テーブルに切り替えます。それらを含むc/c++固定小数点ライブラリがたくさんあります。

これは、 Memoizationに関する他の誰かのコードです。使用される実際の値がよりクラスター化されている場合、これは機能する可能性があります。

これはFixed Pointに関する SO の質問です。

于 2009-03-05T15:30:25.190 に答える
1

ボトルネックとは？サイン/コサイン関数呼び出しですか、それともアークサイン呼び出しですか?

サイン/コサイン呼び出しが遅い場合は、次の定理を使用して、呼び出しが多くなるのを防ぐことができます。

1 = sin(x)^2 + cos(x)^2
cos(x) = sqrt(1 - sin(x)^2)

しかし、既に計算した値を再計算する必要がないように、マッピングのアイデアが気に入っています。ただし、マップがすぐに非常に大きくなる可能性があるので注意してください。

于 2009-03-05T15:57:55.543 に答える
0

まあ、lat と lon は特定の範囲内にあることが保証されているので、Math.* メソッドの呼び出しに何らかの形式のルックアップ テーブルを使用してみることができます。言って、Dictionary<double,double>

于 2009-03-05T15:34:18.923 に答える
0

その機能がボトルネックであることがどのように判明したかを再検討することをお勧めします。(IE はアプリケーションのプロファイリングを行いましたか?)

私にとっての方程式は非常に軽量に見え、問題を引き起こすこと はありません。確かに、私はあなたのアプリケーションを知りませんが、あなたはこれらの計算をたくさん行っていると言っています。

それにもかかわらず、それは考慮すべきことです。

于 2009-03-05T16:02:28.857 に答える