计算地理位置的公式

71
我需要在我的应用程序中实现地理位置搜索,但是我对使用正确的公式非常困惑。在网上和StackOverflow上进行了一些搜索后,我发现解决方案如下:
  1. 使用Haversine公式
  2. 使用大圆距离公式
  3. 在数据库中使用空间搜索引擎
目前,选项#3对我来说真的不是一个选择。现在我有点困惑,因为我一直认为Great-Circle Distance FormulaHaversine Formula同义词,但显然我错了?

Haversine Formula

上面的截图来自于精彩的使用MySQL进行地理(接近度)搜索论文,并使用以下函数:

ASIN, SQRT, POWER, SIN, PI, COS

我也看到了从球面余弦定理相同的公式)衍生出来的变体,比如这个:

(3956 * ACOS(COS(RADIANS(o_lat)) * COS(RADIANS(d_lat)) * COS(RADIANS(d_lon) - RADIANS(o_lon)) + SIN(RADIANS(o_lat)) * SIN(RADIANS(d_lat))))

使用以下函数:

ACOS, COS, RADIANS, SIN

我不是数学专家,但这些公式是否相同?我遇到了一些更多的变化和公式(例如球面余弦定理Vincenty's formulae - 这似乎是最准确的),这让我更加困惑...
我需要选择一个好的通用公式来在PHP / MySQL中实现。有人可以解释一下我上面提到的公式之间的区别吗?
- 哪个计算速度最快? - 哪一个提供最准确的结果? - 从速度/结果准确性方面来看,哪一个是最好的?
感谢您对这些问题的洞察力。

根据theonlytheory的回答,我测试了以下大圆距离公式:

  • Vincenty公式
  • Haversine公式
  • 球面余弦定理

Vincenty公式非常慢,但精度很高(可达0.5毫米)

Haversine公式比Vincenty公式快得多,我能够在约6秒内运行100万次计算,这对我的需求来说是可以接受的。

球面余弦定理公式的速度几乎是Haversine公式的两倍,并且精度差异可以被忽略,适用于大多数情况。


以下是一些测试位置:

  • 谷歌总部 (37.422045, -122.084347)
  • 加利福尼亚州旧金山市 (37.77493, -122.419416)
  • 法国艾菲尔铁塔 (48.8582, 2.294407)
  • 悉尼歌剧院 (-33.856553, 151.214696)

谷歌总部 - 加利福尼亚州旧金山:

  • Vincenty公式:49,087.066米
  • Haversine公式:49,103.006米
  • 球面余弦定理:49,103.006米

Google总部 - 巴黎铁塔,法国:

  • Vincenty公式:8,989,724.399米
  • Haversine公式:8,967,042.917米
  • 球面余弦定理:8,967,042.917米

Google总部 - 悉尼歌剧院:

  • Vincenty公式:11,939,773.640米
  • Haversine公式:11,952,717.240米
  • 余弦定理球面距离公式:11,952,717.240米

正如您所看到的,Haversine公式和球面余弦定理之间几乎没有明显的区别,但与Vincenty公式相比,两者的距离偏差高达22公里,因为它使用的是地球的椭圆近似而不是球形近似。

1
我很久以前遇到了类似的问题,在一个我从未开始的项目中。在我的笔记中,我找到了这个公式:AB=sqrt(pow(($Xb-$Xa),2)+pow(($Yb-$Ya),2)));,我从来没有完全理解它的作用...希望能帮到你 ;) - Strae
2
值得一提的是:对于那些被“3956”搞糊涂的人来说,这是地球的英里半径。但根据维基百科的数据,这应该近似为3959 http://en.wikipedia.org/wiki/Earth_radius 如果你想用公里测量距离,那么就应该使用6371。我不确定这是否会影响到你的回答@Alix,但是取决于你使用的数字,你的单位可能会错乱,因此应该换算成英里为单位。 - Chris Marisic
如果你的“搜索范围”足够小(<500公里),你可以使用勾股定理对结果进行排序。距离可能不是很准确(世界不是平面的,这有点遗憾),但是距离顺序将是正确的。 - Rudie
1
顺便问一句,使用坐标[-180, 180]orig.lat - dest.lat是否有误?如果orig.lat = -170dest.lat = 170会发生什么?距离是340度吗?不,实际上只是20。如果您正在使用实际地球(地图集)坐标,您该如何解决这个问题? - Rudie
如果有人能够在这个平地公式问题中添加结果,那就太好了!此外,添加一个附近数据集(接近现有数据集约1公里)将有助于判断短距离内的准确性。我本来想自己做的,但是我对这三个公式的理解不是很好,所以我来这里寻求帮助:D - Jethro
显示剩余2条评论
2个回答

36
余弦定理和Haversine公式在具有无限精度的计算机上将产生相同的结果。 Haversine公式对浮点数错误更加稳健。然而,今天的计算机具有双精度,约为15个有效数字,余弦定理可能适用于您。这两个公式都假定地球为球体,而Vicenty的迭代解(最精确的)则假定地球为椭球体(实际上地球不是椭球体,而是大地水准面)。一些参考资料: http://www.movable-type.co.uk/scripts/gis-faq-5.1.html 更好的是:请注意,余弦定理和Haversine中使用的纬度是地心纬度,而不是大地纬度。 对于一个球体,这两个值是相同的。 哪个计算速度更快? 按速度从快到慢的顺序是:余弦定理(5个三角函数调用)-> Haversine(涉及sqrt)-> Vicenty(必须在for循环中迭代求解) 哪个最准确? Vicenty. 在同时考虑速度和准确性时,哪个最好? 如果您要计算的距离可以考虑地球是平坦的,那么您可以计算出形式为x = kx * difference(经度差)和y = ky * difference(纬度差)的公式。然后用distance = sqrt(dx * dx + dy * dy)求距离。如果您要解决的问题领域可以用距离的平方来解决,那么您将不必计算平方根,这个公式将是尽可能快的。它的额外优势是您可以计算向量距离 - x是东向距离,y是北向距离。 否则,请尝试使用这三种公式并选择适合您情况的公式。

3
非常好的回答,谢谢。尽管如此,我仍然有一些疑问。我以为只有一种纬度,是什么区分了大地纬度和地心纬度?Google在Google Maps API中提供哪种类型的纬度?关于你和DaNieL提供的公式,你们所说的将地球视为平面是什么意思?如果我想知道纽约和悉尼之间的距离,那个公式会返回准确的结果吗? - Alix Axel
1
我不知道Google Maps API提供了哪种类型的纬度,但我猜测它将是大地纬度。如果距离在几公里左右,那么在这个尺度下地球看起来是平的 - 对吧?对于从纽约到悉尼的计算,您应该使用余弦定理。 - morpheus
@theonlytheory:再次感谢,我只有一个最后的问题:您没有提到大圆距离公式...您能详细说明一下这个公式与其他所有公式的区别吗? - Alix Axel
4
没有唯一的大圆公式。上面讨论的公式是用于计算大圆距离的公式。你可以说它们都是大圆公式。 - morpheus
谷歌地图API据传提供WGS84纬度和经度,我认为这使它成为大地测量学? - MarkJ
1
是的,WGS84纬度=大地纬度。 - morpheus

12

所以你想要:

  • 按距离 p0 排序记录
  • 选择距离 p0 距离小于 r 的记录

诀窍在于,你不需要计算大圆距离!你可以使用 任何从一对点到实数范围内的函数其严格随着点之间的大圆距离增加而增加。这样的函数有很多,并且有些比各种精确计算大圆距离的公式快得多。其中一种函数是 3D 中的欧几里德距离。将纬度和经度转换为球面上的 3D 点不涉及反三角函数。

一旦你拥有了 x、Y 和 Z,你实际上不需要计算从 p0 到你的点的距离,因为你可以使用切平面到 p0 的距离。该距离也严格随着大圆距离的增加而增加,并且是由 X、Y 和 Z 计算出的线性组合 - 甚至不需要平方根。你只需要预计算系数和与所需大圆距离相对应的截止距离即可。


1
这是一个非常好的想法。我通常不会提交“好主意”帖子,但这太棒了!在查找表中预计算指标的距离,然后就可以开始了!确实是非常好的建议。 - Eric Cope

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接