计算地理邻近度的公式 [英] Formulas to Calculate Geo Proximity
问题描述
我需要在我的应用程序中实现地理邻近搜索，但是对于要使用的正确公式，我感到非常困惑.在Web和StackOverflow中进行一些搜索后，我发现解决方案是:
- 使用 Haversine公式
-
使用大圆距离公式 - 在数据库中使用空间搜索引擎
选项3确实不是我的ATM选项.现在，我有点困惑了，因为尽管我总是大圆距离公式和 Haversine公式是同义词，但显然我错了吗?
上面的屏幕截图来自令人敬畏的 使用MySQL进行Geo(邻近)搜索 纸张，并使用以下功能:
ASIN, SQRT, POWER, SIN, PI, COS
我还看到了与 相同公式(余弦的球形定律 和 公式 -似乎是最准确)，这让我更加困惑...
我需要选择一个良好的通用公式以在PHP/MySQL中实现.谁能解释我上面提到的公式之间的区别?
- 哪个是计算速度最快的?
- 哪个提供了最准确的结果?
- 在速度/结果准确性方面哪个最好?
感谢您对这些问题的见识.
基于 theonlytheory 答案我测试了以下Great-Circle距离公式:
- Vincenty公式
- Haversine配方
- 余弦的球形定律
Vincenty配方的速度很慢，但是它非常准确(小于0.5毫米).
Haversine公式比Vincenty公式快得多，我能够在大约6秒钟内运行100万次计算，这完全可以满足我的需求.
余弦公式的球形定律显示为几乎是Haversine公式的两倍，并且大多数情况下，精度差异为忽略不计使用案例.
以下是一些测试位置:
- Google总部(
37.422045，-122.084347) - 加利福尼亚州旧金山(
37.77493，-122.419416) - 法国艾菲尔铁塔(
48.8582，2.294407) - 悉尼歌剧院(
-33.856553，151.214696)
Google总部-加利福尼亚州旧金山:
- Vincenty公式:
49 087.066 meters - Haversine公式:
49 103.006 meters - 余弦的球形定律:
49 103.006 meters
Google总部-法国艾菲尔铁塔:
- Vincenty公式:
8 989 724.399 meters - Haversine公式:
8 967 042.917 meters - 余弦的球形定律:
8 967 042.917 meters
Google总部-悉尼歌剧院:
- Vincenty公式:
11 939 773.640 meters - Haversine公式:
11 952 717.240 meters - 余弦的球形定律:
11 952 717.240 meters
如您所见，Haversine公式与余弦球定律之间没有明显差异，但是与之相比，两者的距离偏移量高达22公里. Vincenty公式，因为它使用地球的椭圆近似而不是球形近似.
假设机器精度无限，余弦定律和Haversine公式将给出相同的结果. Haversine公式对于浮点错误更健壮.但是，当今的机器具有15位有效数字量级的双精度，并且余弦定律可能对您来说很好.这两个公式都假设球面土，而维森特的迭代解(最精确)假定椭圆形土(实际上，地球甚至不是椭球面-它是一个大地水准面).一些参考: http://www.movable-type.co.uk/scripts /gis-faq-5.1.html
它会变得更好:请注意余弦定律中使用的纬度以及Haversine是地心纬度，这与大地纬度不同.对于一个球体，这两个是相同的.
哪个计算速度最快?
从最快到最慢的顺序是:余弦定律(5次三角函数调用)-> Haversine(涉及sqrt)-> Vicenty(必须在for循环中迭代解决此问题)
哪个是最准确的?
Vicenty.
同时考虑速度和准确性时，哪个最好?
如果您的问题域使得对于您要计算的距离，地球可以被认为是平坦的，那么您可以计算出一个x = kx *的公式(我将不提供详细信息)经度差，y = ky *纬度差.然后距离= sqrt(dx dx + dy dy).如果您的问题域可以用距离平方解决，那么您将不必花费sqrt，并且该公式将尽可能快地获得.它具有附加的优势，您可以计算 vector 距离-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:
- Use the Haversine Formula
Use the Great-Circle Distance Formula- 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屋！
