计算地理邻近度的公式 [英] Formulas to Calculate Geo Proximity

查看：35
本文介绍了计算地理邻近度的公式的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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

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

选项#3 对我来说真的不是 ATM 的选项.现在我有点困惑，因为我总是认为

上面的屏幕截图取自很棒的使用 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(弧度(d_lat))))

使用以下函数:

ACOS、COS、弧度、SIN

我不是数学专家，但这些公式是一样的吗?我遇到了一些更多变体和公式(例如 余弦球面定律和Vincenty's formulae - 这似乎是最准确)，这让我更加困惑......

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

  • 哪个计算速度最快?
  • 哪种结果最准确?
  • 哪个在结果的速度/准确性方面最好?

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

<小时>

基于 theonlytheory 答案，我测试了以下大圆距离公式:

  • 文森特公式
  • 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)
<小时>

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

  • 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 公式，因为它使用地球的椭球近似值，而不是球面近似值.

解决方案

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

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

哪个计算速度最快?

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

哪个最准确?

文森特.

同时考虑速度和准确性时，哪个最好?

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

I need to implement a Geo proximity search in my application but I'm very confused regarding the correct formula to use. After some searches in the Web and in StackOverflow I found that the solutions are:

  1. Use the Haversine Formula
  2. Use the Great-Circle Distance Formula
  3. Use a Spatial Search Engine in the Database

Option #3 is really not an option for me ATM. Now I'm a little confused since I always though that the Great-Circle Distance Formula and Haversine Formula were synonymous but apparently I was wrong?

The above screen shot was taken from the awesome Geo (proximity) Search with MySQL paper, and uses the following functions:

ASIN, SQRT, POWER, SIN, PI, COS

I've also seen variations from the same formula (Spherical Law of Cosines), like this one:

(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))))

That uses the following functions:

ACOS, COS, RADIANS, SIN

I am not a math expert, but are these formulas the same? I've come across some more variations, and formulas (such as the Spherical Law of Cosines and the Vincenty's formulae - which seems to be the most accurate) and that makes me even more confused...

I need to choose a good general purpose formula to implement in PHP / MySQL. Can anyone explain me the differences between the formulas I mentioned above?

  • Which one is the fastest to compute?
  • Which one provides the most accurate results?
  • Which one is the best in terms of speed / accuracy of results?

I appreciate your insight on these questions.

Based on theonlytheory answer I tested the following Great-Circle Distance Formulas:

  • Vincenty Formula
  • Haversine Formula
  • Spherical Law of Cosines

The Vincenty Formula is dead slow, however it's pretty accurate (down to 0.5 mm).

The Haversine Formula is way faster than the Vincenty Formula, I was able to run 1 million calculations in about 6 seconds which is pretty much acceptable for my needs.

The Spherical Law of Cosines Formula revealed to be almost twice as fast as the Haversine Formula, and the precision difference is neglectfulness for most usage cases.

Here are some test locations:

  • Google HQ (37.422045, -122.084347)
  • San Francisco, CA (37.77493, -122.419416)
  • Eiffel Tower, France (48.8582, 2.294407)
  • Opera House, Sydney (-33.856553, 151.214696)

Google HQ - San Francisco, CA:

  • Vincenty Formula: 49 087.066 meters
  • Haversine Formula: 49 103.006 meters
  • Spherical Law of Cosines: 49 103.006 meters

Google HQ - Eiffel Tower, France:

  • Vincenty Formula: 8 989 724.399 meters
  • Haversine Formula: 8 967 042.917 meters
  • Spherical Law of Cosines: 8 967 042.917 meters

Google HQ - Opera House, Sydney:

  • Vincenty Formula: 11 939 773.640 meters
  • Haversine Formula: 11 952 717.240 meters
  • Spherical Law of Cosines: 11 952 717.240 meters

As you can see there is no noticeable difference between the Haversine Formula and the Spherical Law of Cosines, however both have distance offsets as high as 22 kilometers compared to the Vincenty Formula because it uses an ellipsoidal approximation of the earth instead of a spherical one.

解决方案

The Law of Cosines and the Haversine Formula will give identical results assuming a machine with infinite precision. The Haversine formula is more robust to floating point errors. However, today's machines have double precision of the order of 15 significant figures, and the law of cosines may work just fine for you. Both these formulas assume spherical earth, whereas Vicenty's iterative solution (most accurate) assumes ellipsoidal earth (in reality the earth is not even an ellipsoid - it is a geoid). Some references: http://www.movable-type.co.uk/scripts/gis-faq-5.1.html

It gets better: note the latitude to be used in the law of cosines as well as the Haversine is the geocentric latitude, which is different from geodetic latitude. For a sphere, these two are the same.

Which one is fastest to compute?

In order from fastest to slowest are: law of cosines (5 trig. calls) -> haversine (involves sqrt) -> Vicenty (have to solve this iteratively in a for loop)

Which one is most accurate?

Vicenty.

Which one is best when speed and accuracy are both considered?

If your problem domain is such that for the distances you are trying to calculate, the earth can be considered as flat, then you can work out (I am not going to give details) a formula of the form x = kx * difference in longitude, y = ky * difference in latitude. Then distance = sqrt(dxdx + dydy). If your problem domain is such that it can be solved with distance squared, then you won't have to take sqrt, and this formula will be as fast as you get possibly get. It has the added advantage that you can calculate the vector distance - x is distance in east direction, and y is distance in the north direction. Otherwise, experiment with the 3 and choose what works best in your situation.

这篇关于计算地理邻近度的公式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
PHP最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆