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

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()您真正感兴趣的值即可。

关于：使用的潜在错误，acos()仅在使用单精度float变量时，这些错误才真正重要。使用double包含16个有效数字的数字，您可以将距离准确地控制在1米以内。