距离计算功能的优化 [英] Optimization of a distance calculation function
问题描述
在我的代码我必须做大量的距离计算的对经/纬度值之间。
In my code I have to do a lot of distance calculation between pairs of lat/long values.
中的代码如下:
double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad)
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad));
(lat2rad例如是纬度转换为弧度)。
(lat2rad e.g. is latitude converted to radians).
我已经确定这个功能作为我的应用程序的性能瓶颈。有没有什么办法来改善呢?
I have identified this function as the performance bottleneck of my application. Is there any way to improve this?
(因为坐标的改变,我不能使用查找表)。我也看了一下这个问题其中像电网查找方案建议,这可能是一种可能性。
(I cannot use look-up tables since the coordinates are varying). I have also looked at this question where a lookup scheme like a grid is suggested, which might be a possibility.
感谢您的时间! ; - )
Thanks for your time! ;-)
推荐答案
如果你的目标是排名(比较)距离,然后近似(罪
和 COS
表查找)可以大大减少你所需要的计算量(实施快拒绝 。)
If your goal is to rank (compare) distances, then approximations (sin
and cos
table lookups) could drastically reduce your amount of computations required (implement quick reject.)
您的目标是仅与实际三角函数计算出发,如果近似距离之间的差(进行排列或比较)低于某一阈值下降。
Your goal is to only proceed with the actual trigonometric computation if the difference between the approximated distances (to be ranked or compared) falls below a certain threshold.
例如:使用查找表用1000个样本(即罪
和 COS
采样每个 2 * PI / 1000
),查找不确定性最多为0.006284。使用参数不确定性计算以 ACOS
,累积的不确定性,也算是门槛不确定性,将最多0.018731。
E.g. using lookup tables with 1000 samples (i.e. sin
and cos
sampled every 2*pi/1000
), the lookup uncertainty is at most 0.006284. Using uncertainty calculation for the parameter to ACos
, the cumulated uncertainty, also be the threshold uncertainty, will be at most 0.018731.
所以,如果评估数学。仙(lat2rad)* Math.Sin(lat1rad)
使用
+ Math.Cos(lat2rad)* Math.Cos(lat1rad)* Math.Cos(lon2rad - lon1rad)的两个坐标集对(距离)罪
和 COS
查找表产生一定的排名(一个距离似乎比基于其它更高近似),和差的模数大于阈值以上,则该近似是有效的。否则,实际三角计算继续进行。
So, if evaluating Math.Sin(lat2rad) * Math.Sin(lat1rad)
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad)
using sin
and cos
lookup tables for two coordinate-set pairs (distances) yields a certain ranking (one distance appears greater than the other based on the approximation), and the difference's modulus is greater than the threshold above, then the approximation is valid. Otherwise proceed with the actual trigonometric calculation.
这篇关于距离计算功能的优化的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!