php 计算地理邻近度的公式
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2096385/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Formulas to Calculate Geo Proximity
提问by Alix Axel
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:
我需要在我的应用程序中实现地理邻近搜索，但我对要使用的正确公式感到非常困惑。在 Web 和 StackOverflow 中进行了一些搜索后，我发现解决方案是：
- Use the Haversine Formula
Use the Great-Circle Distance Formula- Use a Spatial Search Enginein the Database
- 使用Haversine公式
使用大圆距离公式- 在数据库中使用空间搜索引擎
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 Formulaand Haversine Formulawere synonymousbut apparently I was wrong?
选项 #3 对我来说真的不是 ATM 的选项。现在我有点困惑，因为我总是认为大圆距离公式和Haversine公式是同义词，但显然我错了？
The above screen shot was taken from the awesome Geo (proximity) Search with MySQLpaper, and uses the following functions:
上面的屏幕截图来自很棒的Geo (proximity) Search with MySQL论文，并使用了以下功能：
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 Cosinesand the Vincenty'sformulae- which seems to be the most accurate) and that makes me even more confused...
我不是数学专家，但这些公式是一样的吗？我已经遇到了一些更多的变化和公式（如余弦球法和Vincenty的公式-这似乎是最准确的），这让我更糊涂了......
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?
我需要选择一个好的通用公式来在 PHP/MySQL 中实现。谁能解释一下我上面提到的公式之间的区别？
- 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 theonlytheoryanswer I tested the following Great-Circle Distance Formulas:
基于theonlytheory答案，我测试了以下大圆距离公式：
- Vincenty Formula
- Haversine Formula
- Spherical Law of Cosines
- 文森特公式
- 半正弦公式
- 余弦球定律
The Vincenty Formulais dead slow, however it's pretty accurate (down to 0.5 mm).
该Vincenty公式是死的慢，但是它是相当准确的（下降到0.5mm） 。
The Haversine Formulais 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.
该haversine公式是远远比Vincenty公式更快，我能够在大约6秒，这是我的需要非常接受试验1次亿次运算。
The Spherical Law of Cosines Formularevealed to be almost twice as fastas the Haversine Formula, and the precision difference is neglectfulnessfor most usage cases.
余弦公式的球面定律显示几乎是Haversine公式的两倍，并且精度差异对于大多数使用情况是可忽略的。
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)
- 谷歌总部(
37.422045,-122.084347) - 加利福尼亚州旧金山(
37.77493,-122.419416) - 法国埃菲尔铁塔(
48.8582,2.294407) - 悉尼歌剧院(
-33.856553,151.214696)
Google HQ - San Francisco, CA:
Google 总部 - 加利福尼亚州旧金山：
- Vincenty Formula:
49 087.066 meters - Haversine Formula:
49 103.006 meters - Spherical Law of Cosines:
49 103.006 meters
- 文森特公式：
49 087.066 meters - 半正弦公式：
49 103.006 meters - 余弦球定律：
49 103.006 meters
Google HQ - Eiffel Tower, France:
Google 总部 - 埃菲尔铁塔，法国：
- Vincenty Formula:
8 989 724.399 meters - Haversine Formula:
8 967 042.917 meters - Spherical Law of Cosines:
8 967 042.917 meters
- 文森特公式：
8 989 724.399 meters - 半正弦公式：
8 967 042.917 meters - 余弦球定律：
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
- 文森特公式：
11 939 773.640 meters - 半正弦公式：
11 952 717.240 meters - 余弦球定律：
11 952 717.240 meters
As you can see there is no noticeable differencebetween the Haversine Formula and the Spherical Law of Cosines, however both have distance offsets as high as 22 kilometerscompared to the Vincenty Formula because it uses an ellipsoidal approximation of the earth instead of a spherical one.
正如您所看到的，Haversine 公式和余弦球面定律之间没有明显区别，但是与 Vincenty 公式相比，两者的距离偏移量都高达 22 公里，因为它使用地球的椭球近似值而不是球面近似值。
采纳答案by morpheus
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
假设机器具有无限精度，余弦定律和半正弦公式将给出相同的结果。Haversine 公式对浮点误差更稳健。但是，今天的机器具有 15 位有效数字量级的双精度，余弦定律可能适合您。这两个公式都假设地球是球形的，而 Vicenty 的迭代解决方案（最准确）假设地球是椭球（实际上地球甚至不是椭球 - 它是大地水准面）。一些参考资料：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.
它变得更好：请注意余弦定律中使用的纬度以及Haversine是地心纬度，与大地纬度不同。对于球体，这两者是相同的。
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)
从最快到最慢的顺序是：余弦定律（5 次触发调用）-> 正弦（涉及 sqrt）-> Vicenty（必须在 for 循环中迭代地解决这个问题）
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 vectordistance - 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.
如果您的问题域是对于您尝试计算的距离，地球可以被认为是平坦的，那么您可以计算出（我不打算提供详细信息）形式为 x = kx * 经度差的公式, y = ky * 纬度差异。然后距离 = sqrt(dx dx + dydy)。如果您的问题域可以用距离平方来解决，那么您就不必采用 sqrt，而且这个公式将尽可能快。它还有一个额外的优势，您可以计算矢量距离 - x 是东向的距离，y 是北向的距离。否则，尝试 3 并选择最适合您情况的方法。
回答by BASTA
So you want to:
所以你想：
- sort records by distance from p0
- select only records whose distance from p0 is less than r
- 按距 p0 的距离对记录进行排序
- 只选择与 p0 的距离小于 r 的记录
The trick is that you don't exactly need to compute the great circle distance for that! You can do with anyfunction from a pair of points to a real value that strictly grows with the great circle distance between the points. There are many such functions and some are much faster to compute than the various formulas for the exact great circle distance. One such function is the Euclidean distance in 3D. Converting latitude and longitude to a 3D point on the sphere doesn't involve inverse trigonometric functions.
诀窍是您并不完全需要为此计算大圆距离！您可以使用从一对点到实际值的任何函数，该值随着点之间的大圆距离严格增长。有许多这样的函数，其中一些函数的计算速度比精确大圆距离的各种公式要快得多。一种这样的函数是 3D 中的欧几里得距离。将纬度和经度转换为球体上的 3D 点不涉及反三角函数。
Once you have x,Y,Z, you can realize that you don't actually need the distance from p0 to your point, because you can as well use the distance from the tangent plane at p0. That distance also strictly grows with the great circle distance, and is computed from X,Y,Z as a linear combination - not even a square root is needed. You just need to precompute the coefficients and the cutoff distance that corresponds to the desired great circle distance.
一旦你有了 x、Y、Z，你就会意识到你实际上并不需要从 p0 到你的点的距离，因为你也可以使用 p0 处到切平面的距离。该距离也严格随着大圆距离而增长，并根据 X、Y、Z 作为线性组合计算 - 甚至不需要平方根。您只需要预先计算对应于所需大圆距离的系数和截止距离。
