计算地理邻近度的公式

问题描述

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

1. 使用
2. 在数据库中使用的变化(余弦球面定律)，像这样:

   (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

   我不是数学专家，但这些公式是一样的吗?我遇到了一些

3. Use a (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.

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