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

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

P.s 我确实发现了许多其他相关问题，但它们并没有真正关注我的速度问题。

Answer 1

如果您不介意忽略地球的轻微扁率(并且您发布的 Haversine 代码无论如何都会这样做)考虑将所有球面(纬度/经度)坐标预先转换为 3D 单位长度 首先是笛卡尔坐标，per:

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

那么笛卡尔坐标 p1 和 p2 之间的球面距离就是:

r * acos(p1 . p2)

由于 p1 和 p2 将具有单位长度，因此每对减少为四次乘法、两次加法和一次反三角运算。

另请注意，点积的计算是优化的理想选择，例如通过 GPU、MMX 扩展、 vector 库等。

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

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

然后您只需获取您实际感兴趣的值的 acos()。

回复:使用 acos() 的潜在错误，只有在您使用单精度 float 变量时，这些错误才真正重要。使用具有 16 位有效数字的 double 可以使您的距离精确到一米或更小。