r - 一组经度/纬度点之间的最大距离

Question

我有一组经纬度坐标。什么是计算集合中任意两点之间的最大距离(如果愿意，也称为“最大直径”)的有效方法？

一种天真的方法是使用 Haversine formula计算每 2 个点之间的距离并获得最大值，但这显然不能很好地缩放。

编辑:这些点位于足够小的区域，测量携带移动设备的人在一天内事件的区域。

Answer 1

定理 #1:沿地球表面的任意两个大圆距离的顺序与您穿过地球的点之间的直线距离的顺序相同。

因此，根据任意半径的球形地球或给定形状参数的椭圆体，将经纬度转换为 x、y、z。这是每个点的几个正弦/余弦(不是每对点)。

现在您有了一个不依赖于计算半正弦距离的标准 3 维问题。点之间的距离只是欧几里德(3d 中的毕达哥拉斯)。需要一个平方根和一些平方，如果您只关心比较，可以省略平方根。

可能有奇特的空间树数据结构来帮助解决这个问题。或算法，如 http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_ss_07w/Webprojects/Qinbo_diameter/2d_alg.htm (单击“下一步”获取 3d 方法)。或此处的 C++ 代码:http://valis.cs.uiuc.edu/~sariel/papers/00/diameter/diam_prog.html

找到最大距离对后，您可以使用 Haversine 公式计算该对沿表面的距离。