更快速地计算两点之间的地理距离
我从互联网上的某个地方借用了以下方法（不记得在哪里）。 但它正在做一个直接的过程，找到两个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; } } 我确实找到了许多其他相关问题，但他们并没有真正关注我的速度问题。
如果你不介意忽略地球的轻微扁率（并且你发布的Haversine代码就是这样做的话）考虑首先将所有球面（纬度/长度）坐标预先转换为3D 单位长度笛卡尔坐标，每个：
那么笛卡尔坐标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变量，那么这些非常重要。 使用带有16位有效数字的double精度表可以使距离精确到一米或更小。
那是thersineine算法，将为您提供相当高的准确度。
如果真的是“数百万”点，也许可以实现你所做的计算缓存…如果你遇到一对坐标，这两个坐标都足够接近你已经计算过的距离对，然后使用缓存值？
或尝试缓存一些中间步骤，例如度数到弧度的转换。
如果您牺牲准确性，您可以做出一些改进。 据我记忆，对于小x ， sin(x) 近似等于x 。 此外，您似乎计算了几次相同的事情，例如： Math.sin(dLat/2) （实际上可以近似为dLat/2 ，如上所述）。
但是，如果您正在进行数百万次这样的操作，我会在其他地方。
-
你的算法是最优的吗？ 也许你做了太多简单的计算？
-
如果点来自数据库，您可以在数据库服务器端执行计算作为存储过程吗？
-
如果您正在寻找最近的点，您能以某种方式索引它们吗？
-
地理空间索引可以帮助您吗？
您可以尝试球面三角函数的余弦定律：
a = sin(lat1) * sin(lat2) b = cos(lat1) * cos(lat2) * cos(lon2 - lon1) c = arccos(a + b) d = R * c
但是对于短距离来说这将是不准确的（并且可能只是稍微快一些）。
这里有一个完整的讨论。 然而，hasrsine公式是最正确的方式，所以除了别人的建议，你可能没有太多可以做的。 @ Alnitak的回答可能有效，但笛卡尔转换的球形并不一定快。