距离计算函数的优化

在我的代码中，我必须在成对的纬度/经度值之间进行大量的距离计算。距离计算函数的优化

代码看起来是这样的：

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

距离计算函数的优化

回答

相关问题