Databases
StackOverflow2013
Postsdbo
POFormulas to Calculate Geo Proximity
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFormulas to Calculate Geo Proximity
    text
    copied!<p>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:</p> <ol> <li>Use the <strong>Haversine Formula</strong></li> <li><s>Use the <strong>Great-Circle Distance Formula</strong></s></li> <li>Use a <strong>Spatial Search Engine</strong> in the Database</li> </ol> <p>Option #3 is really not an option for me ATM. Now I'm a little confused since I always though that the <a href="http://en.wikipedia.org/wiki/Great-circle_distance" rel="nofollow noreferrer">Great-Circle Distance Formula</a> and <a href="http://en.wikipedia.org/wiki/Haversine_formula" rel="nofollow noreferrer">Haversine Formula</a> were <strong>synonymous</strong> but apparently I was wrong?</p> <p><a href="http://i46.tinypic.com/30shbn6.png" rel="nofollow noreferrer">Haversine Formula http://i46.tinypic.com/30shbn6.png</a></p> <p>The above screen shot was taken from the awesome <strong><a href="http://www.arubin.org/files/geo_search.pdf" rel="nofollow noreferrer">Geo (proximity) Search with MySQL</a></strong> paper, and uses the following functions:</p> <pre><code>ASIN, SQRT, POWER, SIN, PI, COS </code></pre> <p>I've also seen variations from the <strong><s>same formula</s> (<a href="http://www.thismuchiknow.co.uk/?p=71" rel="nofollow noreferrer">Spherical Law of Cosines</a>)</strong>, like this one:</p> <pre><code>(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)))) </code></pre> <p>That uses the following functions:</p> <pre><code>ACOS, COS, RADIANS, SIN </code></pre> <p>I am not a math expert, but are these formulas the same? I've come across some <strong>more variations, and formulas</strong> (such as the <strong><a href="http://en.wikipedia.org/wiki/Spherical_law_of_cosines" rel="nofollow noreferrer">Spherical Law of Cosines</a></strong> and the <strong><a href="http://www.movable-type.co.uk/scripts/latlong-vincenty.html" rel="nofollow noreferrer">Vincenty's</a> <a href="http://en.wikipedia.org/wiki/Vincenty%27s_formulae" rel="nofollow noreferrer">formulae</a></strong> - which seems to be the most accurate) and that makes me even more confused...</p> <p>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?</p> <ul> <li><strong>Which one is the fastest to compute?</strong></li> <li><strong>Which one provides the most accurate results?</strong></li> <li><strong>Which one is the best in terms of speed / accuracy of results?</strong></li> </ul> <p>I appreciate your insight on these questions.</p> <hr> <p>Based on <a href="https://stackoverflow.com/questions/2096385/formulas-to-calculate-geo-proximity/2097779#2097779">theonlytheory</a> answer I tested the following Great-Circle Distance Formulas:</p> <ul> <li>Vincenty Formula</li> <li>Haversine Formula</li> <li>Spherical Law of Cosines</li> </ul> <p>The <strong>Vincenty Formula</strong> is dead slow, however <strong>it's pretty accurate (down to 0.5 mm)</strong>.</p> <p>The <strong>Haversine Formula</strong> 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.</p> <p>The <strong>Spherical Law of Cosines Formula</strong> revealed to be <strong>almost twice as fast</strong> as the Haversine Formula, and <strong>the precision difference is neglectfulness</strong> for most usage cases.</p> <hr> <p>Here are some test locations:</p> <ul> <li><strong>Google HQ</strong> (<code>37.422045</code>, <code>-122.084347</code>)</li> <li><strong>San Francisco, CA</strong> (<code>37.77493</code>, <code>-122.419416</code>)</li> <li><strong>Eiffel Tower, France</strong> (<code>48.8582</code>, <code>2.294407</code>)</li> <li><strong>Opera House, Sydney</strong> (<code>-33.856553</code>, <code>151.214696</code>)</li> </ul> <hr> <p><strong>Google HQ - San Francisco, CA:</strong></p> <ul> <li>Vincenty Formula: <code>49 087.066 meters</code></li> <li>Haversine Formula: <code>49 103.006 meters</code></li> <li>Spherical Law of Cosines: <code>49 103.006 meters</code></li> </ul> <hr> <p><strong>Google HQ - Eiffel Tower, France:</strong></p> <ul> <li>Vincenty Formula: <code>8 989 724.399 meters</code></li> <li>Haversine Formula: <code>8 967 042.917 meters</code></li> <li>Spherical Law of Cosines: <code>8 967 042.917 meters</code></li> </ul> <hr> <p><strong>Google HQ - Opera House, Sydney:</strong></p> <ul> <li>Vincenty Formula: <code>11 939 773.640 meters</code></li> <li>Haversine Formula: <code>11 952 717.240 meters</code></li> <li>Spherical Law of Cosines: <code>11 952 717.240 meters</code></li> </ul> <hr> <p>As you can see there is <strong>no noticeable difference</strong> between the Haversine Formula and the Spherical Law of Cosines, however both have <strong>distance offsets as high as 22 kilometers</strong> compared to the Vincenty Formula because it uses an ellipsoidal approximation of the earth instead of a spherical one.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload