距離計算函數的優化

在我的代碼中，我必須在成對的緯度/經度值之間進行大量的距離計算。距離計算函數的優化

代碼看起來是這樣的：

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

（lat2rad例如是緯度轉換爲弧度）。

我已經確定這個函數是我應用程序的性能瓶頸。有什麼辦法可以改善嗎？

（我不能使用查找表，因爲座標是變化的）。我還查看了this question，其中提出了像網格這樣的查找方案，這可能是一種可能性。

謝謝你的時間！ ;-)

來源

2009-03-05 puls200

您應該意識到，如果您認爲地球是一個完美的球體，並且近似值與真實回答之間的差值ca ñ相當重要（至少在我的世界）。 http://en.wikipedia.org/wiki/WGS84 – 2009-03-05 16:38:43

的確如此。你可能真的需要計算大圓圈路線。 – 2009-03-05 20:00:01

是的，我知道，但近似對我的情況是可以的。據我所知，由於地球自轉，赤道附近的偏差最大。 – puls200 2009-03-06 06:59:22

如果你的目標是排名（比較）距離，則近似（sin和cos表查找）能大大減少您所需要的計算（執行快速拒絕）

量如果近似距離（待分級或比較）之間的差異低於某個閾值，則您的目標是隻進行實際的三角計算。

E.g.使用具有1000個樣本的查找表（即，每2*pi/1000採樣sin和cos），查找不確定性最多爲0.006284。使用uncertainty calculation作爲ACos的參數，累積的不確定性也是閾值不確定性，將最多爲0.018731。

所以，如果使用sin和cos查找表兩個座標集對（距離）產生一定的排名評估Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad)（一個距離看起來比基於所述近似的其他更大），並且差模量比越大閾值以上，那麼近似值是有效的。否則，繼續進行實際的三角計算。

來源

2009-03-05 15:48:44 vladr

謝謝，你的回答讓我走上正軌。我相信其他一些答案也是有效的。使用具有50.000個條目精度的查找表仍然足夠好。加速大約是以前的3倍。 – puls200 2009-03-09 16:03:48

你需要的值是多少？

如果你將你的值舍入一點，那麼你可以存儲所有查找的結果並檢查是否每個計算都使用了？

來源

2009-03-05 15:25:04 Peter

切換到sin/cos/acos的查找表。會更快，還有很多c/C++定點庫也包含這些庫。

這是來自其他人的代碼Memoization。如果使用的實際值更加集中，哪個可能會起作用。

這是關於Fixed Point的SO問題。

來源

2009-03-05 15:30:25 sfossen

CORDIC算法是否適合您（關於速度/準確性）？

來源

2009-03-05 15:31:31

謝謝你的想法，我會嘗試不同的方法，看看什麼效果最好。 – puls200 2009-03-06 07:04:08

好吧，由於經緯度保持在一定範圍內，因此您可以嘗試使用某種形式的查找表爲您提供Math。*方法調用。也就是說，一個Dictionary<double,double>

來源

2009-03-05 15:34:18

從@Brann使用靈感我認爲你可以減少一點計算（警告它很長一段時間，因爲我做了任何這一點，它將需要驗證）。某種預先計算值的查找可能是最快的，雖然

您有：

1：ACOS（罪過罪過B + COS一個COS乙COS（AB））

但2：COS（AB ）= SIN甲SIN B + COS甲COS乙

被改寫爲3：SIN甲SIN B = COS（AB） - COS甲COS乙

在1取代SIN甲SIN乙您有：

4：ACOS（COS（AB） - COS A COS B + COS A COS B COS（AB））

您可以預先計算X = COS（AB）和Y = COS A COS B，進入4

給：

ACOS（XY + XY）

4三角函數的計算，而不是6！

來源

2009-03-05 15:54:30

什麼是瓶頸？正弦/餘弦函數調用還是反正弦調用？

如果你的正弦/餘弦電話是緩慢的，你可以使用下面的定理，以防止那麼多電話：

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

但我喜歡的映射想法，這樣你就不必重新計算的值，在」已經計算出來了。儘管要小心，因爲地圖可能會很快變大。

來源

2009-03-05 15:57:55 user17720

我認爲你可能想重新檢查你是如何發現這個函數是瓶頸的。（IE瀏覽器是否介紹了應用程序？）

這個方程對我來說似乎很輕，並且應該不是會造成什麼麻煩。 當然，我不知道你的申請，你說你做了很多這些計算。

不過這是需要考慮的事情。

來源

2009-03-05 16:02:28

更改您存儲方式經度/緯度：

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

創建當經度/緯度，還計算（X，Y，Z）的三維表示上在中心的單位球體的等效位置點起源。現在

，以確定是否B點是接近點比C點，請執行下列操作：

// 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); 
}

，並得到兩個點之間的距離：

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-05 16:05:59 Skizz

正如別人指出的，你確定這是你的瓶頸嗎？

我已經完成了一些類似應用程序的性能測試，我正在構建一個簡單方法，使用標準trig來返回兩點之間的距離。 20000次調用將它推到剖析輸出的頂端，但我無法讓它更快地完成......這只是剪切調用數。

在這種情況下，我需要減少＃對它的呼叫...不是說這是瓶頸。

來源

2009-03-05 16:13:53 Ian

我使用不同的算法來計算2 lati/longi位置之間的距離，它可能比您的要輕，因爲它只能進行1次Cos調用和1次Sqrt調用。

public static double GetDistanceBetweenTwoPos(double lat1, double long1, double lat2, double long2) 
{ 
    double distance = 0; 
    double x = 0; 
    double y = 0; 

    x = 69.1 * (lat1 - lat2); 
    y = 69.1 * (long1 - long2) * System.Math.Cos(lat2/57.3); 

    //calculation base : Miles 
    distance = System.Math.Sqrt(x * x + y * y); 

    //Distance calculated in Kilometres 
    return distance * 1.609; 
}

來源

2009-03-05 16:28:25

有人已經提到了memoisation，這有點類似。如果將同一點與其他許多點進行比較，則最好預先計算該方程的一部分。

代替

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

有：

  
double result = Math.Acos(lat2rad.sin * lat1rad.sin 
+ lat2rad.cos * lat1rad.cos * (lon2rad.cos * lon1rad.cos + lon1rad.sin * lon2rad.sin));

，我認爲這是相同的公式爲別人張貼，因爲當您展開支架等式的一部分會消失:)

來源

2009-03-05 17:09:08

距離計算函數的優化

回答

相關問題