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

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

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

Answer 1

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

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

然后是笛卡尔坐标之间的球面距离 p1 和 p2 很简单：

r * acos(p1 . p2)

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

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

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

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

然后您只需获取您真正感兴趣的值的 acos() 即可。

回复：使用 acos() 的潜在不准确之处，这些确实是仅当您使用单精度浮点变量时才有意义。使用具有 16 位有效数字的 double 应该可以让您的距离精确到一米或更小。

Answer 2

这就是半正矢算法，将为您提供相当高的准确性。

如果它确实是“数百万”个点，也许可以实现您所做的计算的缓存...如果您遇到一对坐标，这两个坐标都足够接近您已经计算出距离的一对坐标，然后使用缓存的值？

或者尝试缓存一些中间步骤，例如角度到弧度的转换。

Answer 3

如果您牺牲准确性，则可以进行一些改进。据我记得，sin(x) 大约是大约对于较小的x，等于x。而且看起来您正在多次计算相同的事物，例如：Math.sin(dLat/2)（实际上可以近似为如上所述的 dLat/2） ）。

但是，如果您要执行数百万次此类操作，我会在其他地方进行。

• 你的算法是最优的吗？也许您做了太多简单的计算？

• 如果点来自数据库，您可以在数据库服务器端以存储过程的形式执行计算吗？

• 如果你正在寻找最近的点，你能以某种方式索引它们吗？

• 地理空间索引可以帮助您吗？

Answer 4

您可以尝试球面三角函数的余弦定律：

a = sin(lat1) * sin(lat2)
b = cos(lat1) * cos(lat2) * cos(lon2 - lon1)
c = arccos(a + b)
d = R * c

但对于短距离来说，它将不准确（并且可能只是稍微快一点）。

此处有完整的讨论。
然而，半正矢公式是最正确的方法，因此除了其他人的建议之外，您可能无能为力。
@Alnitak 的答案可能有效，但球面到笛卡尔的转换不一定很快。