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

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

顺便说一句，我确实找到了许多其他相关的问题，但它们并没有真正关注我的速度问题。

- Steve

---

你使用距离是为了什么？这种情况下的典型用途是查找所有接近Y的X。如果这适用于您，那么您应该考虑使用边界框方法，这可能将您的计算从数百万个减少到只有几十个。例如，在5英里范围内找到最近的杂货店。您不需要计算从我的房子到加利福尼亚或阿拉斯加的商店的距离。 - George Mastros

Answer 1

如果您不介意忽略地球的轻微扁平（而且您发布的Haversine代码已经这样做了），可以考虑先将所有球面（纬度/经度）坐标预先转换为三维单位长度笛卡尔坐标，如下所示：

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变量时才会显著。使用具有16个有效数字的double可以获得精度在一米以内的距离。

- Alnitak

Answer 2

对于球面三角学，您可以尝试余弦定理：

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

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

这里有一个完整的讨论链接。 然而，哈弗赛公式是最正确的方法，所以除了其他人建议的之外，你可能没有太多可以做的事情。 @Alnitak的答案可能有效，但球面到笛卡尔转换并不一定快速。

- reve_etrange

---

将球面坐标转换为极坐标只需要四个三角函数操作（或两个三角函数、两个乘法、两个减法和两个平方根），我的回答的重点是，你只需要对每个点进行一次转换，而不是对每对组合都进行转换。 - Alnitak

谢谢！我特别关注短距离的区域，所以可能不是最优的。不过我会运行它并看看效果如何！ - Steve

Haversine的缺点在于中间计算依赖于角度之间的差异，因此必须为每一对进行计算。链接中提到的问题与arccos（在这里和我的答案中都使用）无关，如果您使用具有16位精度的“double”变量，则不应该出现问题。 - Alnitak

Answer 3

这是Haversine算法，能够提供相当准确的水平。

如果真的是“数百万”个点，也许可以实现一个已计算过的计算缓存... 如果您遇到一对坐标，两者都足够接近已经计算过距离的一对坐标，则使用缓存值？

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

- funkybro

---

是的，我认为缓存可能会有所帮助，现在这种方法相当懒惰。没想到数据集会变得如此庞大！ - Steve

Answer 4

如果你牺牲准确性，可以进行一些改进。就我所记得的而言，当x很小时，sin(x) 大约等于x。此外，你似乎正在计算多次相同的内容，例如：Math.sin(dLat/2)（根据上面的说明，实际上可以近似为dLat/2）。

然而，如果你要执行数百万次这样的操作，我建议你在其他地方执行。

• 你的算法是否最优？也许你正在做太多简单的计算？

• 如果点来自数据库，你能否将计算作为存储过程在数据库服务器端执行？

• 如果你正在寻找最接近的点，你能否对它们进行索引？

• 地理空间索引能帮助你吗？

- Tomasz Nurkiewicz

---

我在数据库中没有使用任何形式的GIS扩展，这会有很大的区别吗？ - Steve

@steve 这可能会有所不同，但我不确定有多大。如果您的点在具有空间功能的数据库中，则可以让数据库执行距离计算。但这有点超出了您的问题范围（如何在Java中实现）。 - steenhulthin

添加数据库不是问题，只要我有一个可以指向Java的东西，让我得到一个距离数字就可以了 :) - Steve