更快速地计算两点之间的地理距离

Question

我从互联网上的某个地方借用了以下方法(不记得在哪里).但它正在做一个直接的过程,找到两个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;
  }
}

我确实找到了许多其他相关问题,但他们并没有真正关注我的速度问题.

Answer 1

如果您不介意忽略地球的轻微扁率(并且您发布的Haversine代码就是这样做的话)考虑首先将所有球形(纬度/长度)坐标预先转换为3D 单位长度笛卡尔坐标,每个:

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

然后直角坐标系之间的球面距离p1,并p2很简单:

r * acos(p1 . p2)

由于p1并且p2将具有单位长度,因此每对减少到四次乘法,两次加法和一次逆触发操作.

另请注意,点积的计算是优化的理想选择,例如通过GPU,MMX扩展,矢量库等.

此外,如果您的意图是按距离订购配对,可能忽略更远的配对,您可以r*acos()通过在点积值上对列表进行排序来推迟等式的昂贵部分,因为对于所有有效输入(即范围[-1, 1]),它保证那:

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

然后,您只需获取acos()您真正感兴趣的值.

Re:使用时可能存在的不准确之处,acos()如果您使用的是单精度float变量,那些实际上只是重要的.使用double16位有效数字可以使距离精确到一米或更小.