36

Which is better for calculating the distance between two latitude/longitude points, The Haversine Formula or The Vincenty's Formula? Why?

The distance is obviously being calculated on Earth. Does WGS84 vs GCJ02 coordinates impact the calculation or distance (The Vincenty's formula takes the WGS84 axis into consideration)?

For example, in Android, the Haversine Formula is used in Google Map Utils, but the Vincenty Formula is used by the android.Location object (Location.distanceBetween()).

2 Answers 2

68

Haversine and Vincenty are two algorithms for solving different problems. Haversine computes the great circle distance on a sphere while Vincenty computes the shortest (geodesic) distance on the surface of an ellipsoid of revolution. So the answer to your question can be broken into 2 parts:

  1. Do you want to compute the distance on a sphere on an ellipsoid?
  2. How accurate is Haversine or Vincenty at calculating the given problem?

For terrestrial applications, an ellipsoid of revolution is a reasonable approximation to "mean sea level"; the error is ± 100 m. The flattening of this ellipsoid is small, about 1/300, and so can be approximated by a sphere (of equal volume, for example).

Great circle distances differ from geodesic distances by up to 0.5%. In some applications, e.g., what's the distance from the Cape to Cairo?, this error can be neglected. In other applications, e.g., determining maritime boundaries, it is far too large (it's 5 m over a distance of 1 km). In general, you're safer using the geodesic distance.

If you're interested is distance traveled (by car, boat, or plane), there are lots of constraints on the path taken and neither the great circle or geodesic distance, which measure the length of shortest paths on an ideal surface, would be appropriate.

On the question of whether the algorithms are accurate:

Haversine is accurate to round-off unless the points are nearly antipodal. Better formulas are given in the Wikipedia article on great-circle distances.

Vincenty is usually accurate to about 0.1 mm. However if the points are nearly antipodal, the algorithm fails to converge and the error is much larger. I give a better algorithm for solving the geodesic problem in Algorithms for geodesics. See also the Wikipedia article on geodesics on an ellipsoid.

Solving the geodesic problem is slower than solving for the great-circle. But it's still very fast (about 1 μs per calculation), so this shouldn't be a reason to prefer great circle distances.

ADENDUM

Here is the Java package which implements my algorithm for finding geodesic distances. Unlike Vincenty's method, this is accurate to round-off and converges everywhere.

5
  • Isn't it more accurate to say that Vincenty's formula sometimes fails to converge for near antipodal points, otherwise just takes a very large number of iterations for such point pairs? To demonstrate the computational inaccuracy in the Haversine formula, I coded both it and the improved great circle computation at the Wikipedia page (based on a simplification of Vincenty's algorithm!) in single precision. With 100M test cases, worst case error was 4.44148 km @ (-64.492126, -157.413849) (64.452232, 22.589592) [Hav] and 0.00392 km @ (-5.779476, 166.661758) (0.646194, -44.298119) [Impr]
    – njuffa
    Jul 30, 2016 at 3:24
  • 1
    The problem with Vincenty's method for near antipodal points is not that convergence is slow; rather it's that the iterative solution method is unstable in this case (if you start with a result close to the solution, each iteration takes you further from the solution). Note that the maximum error given for your "improved" method, 0.00393 km, is close to the round-off limit for single precision arithmetic; in practice double precision is needed.
    – cffk
    Jul 30, 2016 at 13:30
  • I am fully aware that the improved method gives great circle distances accurate to full single-precision but the length limit on comments left no space to point that out explicitly. I mostly wanted to emphasize how much better the improved formula from Wikipedia is (thanks for the pointer), while being barely more computationally costly than the classical Haversine formula: it seems one should always use the improved formula, rather than Haversine. Whether double precision is needed in distance computations of any kind would seem to depend on the accuracy requirements of each use case.
    – njuffa
    Jul 30, 2016 at 14:26
  • @cffk: Your answer looks excellent and deserves to appear in stackoverflow.com/questions/365826 , possibly including code implementing the distance algorithms you recommend.
    – Peter O.
    Nov 22, 2016 at 12:30
  • 1
    Worth noting that under geographiclib.sourceforge.net/index.html there are also libs/wrappers for C#, javascript and Python.
    – Stonetip
    Dec 24, 2016 at 17:20
26

Haversine is a simpler computation but it does not provide the high accuracy Vincenty offers.

Vincenty is more accurate but is also more computationally intensive and will therefore perform slower and increase battery usage.

As with anything "better" is a matter of your particular application. For your application, Vincenty may be a "better" choice than Haversine, but for a different application, Haversine may be a better choice. You will have to look at the particulars of your use cases and make a determination based upon what you find there.

3
  • 2
    My understanding is that in most applications, the Haversine formula (which assumes a spherical earth) provides sufficient accuracy for points up to several hundred miles apart, whereas Vincenty's formula (based on an ellipsoid earth) provides sufficient accuracy for any pair of points, and particularly for near antipodal points.
    – njuffa
    Jul 7, 2016 at 16:31
  • 1
    @njuffa Haversine formula can return inaccurate results even for nearby points. Relative error is up to 0.5%. For example Haversine formula returns 1000.0 meters and Vincenty's formula returns 1003.036 meters for points (48.857461,2.291029) and (48.857461,2.304698).
    – fdermishin
    May 24, 2020 at 18:08
  • 2
    @njuffa Vincenty's formula should not be used for nearly antipodal points, as it fails to converge.
    – fdermishin
    May 24, 2020 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.