71

我需要在我的应用程序中实现地理邻近搜索,但我对要使用的正确公式感到非常困惑。在 Web 和 StackOverflow 中进行一些搜索后,我发现解决方案是:

  1. 使用Haversine 公式
  2. 使用大圆距离公式
  3. 在数据库中使用空间搜索引擎

选项#3 对我的 ATM 来说真的不是一个选项。现在我有点困惑,因为我一直认为大圆距离公式哈弗辛公式同义词,但显然我错了?

哈弗辛公式

上面的屏幕截图取自很棒的Geo (proximity) Search with 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

我不是数学专家,但这些公式是否相同?我遇到了更多的变体和公式(例如余弦的球面定律和文森蒂公式 -这似乎是最准确的),这让我更加困惑......

我需要选择一个好的通用公式在 PHP/MySQL 中实现。谁能解释我上面提到的公式之间的区别?

  • 哪个计算速度最快?
  • 哪一个提供最准确的结果?
  • 就结果的速度/准确性而言,哪一个是最好的?

感谢您对这些问题的洞察力。


基于唯一的理论答案,我测试了以下大圆距离公式:

  • 文森提公式
  • 哈弗辛公式
  • 球面余弦定律

Vincenty 公式非常慢,但它非常准确(低至 0.5 毫米)

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

余弦公式的球面定律显示出几乎是哈弗辛公式的两倍,并且对于大多数用例来说,精度差异是可忽略的。


以下是一些测试地点:

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

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

  • 文森特公式:49 087.066 meters
  • 哈弗辛公式:49 103.006 meters
  • 球面余弦定律:49 103.006 meters

Google 总部 - 法国埃菲尔铁塔:

  • 文森特公式:8 989 724.399 meters
  • 哈弗辛公式:8 967 042.917 meters
  • 球面余弦定律:8 967 042.917 meters

Google 总部 - 悉尼歌剧院:

  • 文森特公式:11 939 773.640 meters
  • 哈弗辛公式:11 952 717.240 meters
  • 球面余弦定律:11 952 717.240 meters

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

4

2 回答 2

36

假设一台具有无限精度的机器,余弦定律和Haversine 公式将给出相同的结果。Haversine 公式对浮点错误更稳健。但是,今天的机器具有 15 位有效数字的双精度,余弦定律可能对您很有效。这两个公式都假设地球是球形的,而 Vicenty 的迭代解决方案(最准确)假设地球是椭球体(实际上地球甚至不是椭球体 - 它是大地水准面)。一些参考资料: http ://www.movable-type.co.uk/scripts/gis-faq-5.1.html

它变得更好:注意余弦定律中使用的纬度以及Haversine是地心纬度,与大地纬度不同。对于一个球体,这两个是相同的。

哪一个计算速度最快?

从最快到最慢的顺序是:余弦定律(5 个三角函数调用)-> hasrsine(涉及 sqrt)-> Vicenty(必须在 for 循环中迭代地解决这个问题)

哪一个最准确?

维森蒂。

当同时考虑速度和准确性时,哪一个最好?

如果您的问题域对于您要计算的距离而言,地球可以被认为是平坦的,那么您可以计算出(我不打算提供详细信息)形式为 x = kx * 经度差的公式, y = ky * 纬度差。然后距离 = sqrt(dx dx + dy dy)。如果您的问题域可以通过距离平方来解决,那么您就不必使用 sqrt,并且这个公式将尽可能快。它还有一个额外的优点是您可以计算矢量距离 - x 是东方向的距离,y 是北方向的距离。否则,请尝试 3 并选择最适合您情况的方法。

于 2010-01-19T22:46:38.757 回答
12

所以你想:

  • 按与 p0 的距离对记录进行排序
  • 仅选择与 p0 的距离小于 r 的记录

诀窍是您并不完全需要为此计算大圆距离!您可以使用从一对点到严格随着点之间的大圆距离增长的实际值的任何函数。有许多这样的函数,其中一些函数的计算速度比精确大圆距离的各种公式要快得多。一个这样的函数是 3D 中的欧几里得距离。将纬度和经度转换为球体上的 3D 点不涉及反三角函数。

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

于 2012-03-29T01:30:36.973 回答