In traditional methods, we calculate distance by assuming the earth as a sphere. But the truth is the Earth is neither perfectly spherical nor ellipse hence calculating the distance on its surface is a challenging task.

There are many algorithms that deal with the shortest distance problem. Each algorithm is related to a specific shape or representation. In this blog we are going to find more about Haversine and Vincenty formula.

HAVERSINE FORMULA:

By using this formula we can easily compute the great-circle distance (The shortest distance between two points on the surface of a Sphere). – Giving an ‘as-the-crow-flies’ distance between the points (ignoring any hills they fly over, of course!)

Haversine formula mostly used to calculate distances for spherical shape.

FORMULA:

haversine (d/r) = haversine (Φ₂ – Φ₁) + cos(Φ₁)cos(Φ₂)haversine(λ₂ -λ₁)

Where d is the distance between two points with longitude and latitude ( λ,Φ ) and r is the radius of the earth.

Java code to calculate the distance between two points using Haversine formula:

 public double getDistance(double startLat, double startLong, double endLat, double endLong) {

        double haversine, distance;

        double dLatitude,  dLongitude;

        double DEG_RAD = 0.01745329251994;

        double R_EARTH = 6367.45;

        dLatitude, = (endLat - startLat) * DEG_RAD;

        dLongitude = (endLong - startLong) * DEG_RAD;

        haversine = Math.sin(dLat * 0.5) * Math.sin(dLat * 0.5) +

                Math.sin(dLon * 0.5) * Math.sin(dLon * 0.5) *

                        Math.cos(startLat * DEG_RAD) *

                        Math.cos(destLat * DEG_RAD);

        distance = Math.asin(Math.sqrt(haversine)) * R_EARTH * 2.0;

        return distance;

    }

Why to use it: Haversine provide simpler computation. Also reduces battery drainage when compared to Vincenty.

Why not to use it: It does not provide high accuracy that Vincenty offers.

VINCENTY FORMULA :

The formulae were developed by Thaddeus Vincenty(1975a) for calculating geodesic distances between a pair of latitude/longitude points on an ellipsoidal model of the Earth.

Unlike the Haversine method for calculating distance on a sphere, these formulae are an iterative method and assume the Earth is an ellipsoid.

This formula include a direct and an inverse method where:

1. Direct Method: It computes the location of a point that is a given distance and azimuth from another point
2. Inverse Method: It computes the geographical distance and azimuth between two given points.

For eg. In the Inverse Method outputs λ after assigning several constants including the length of the semi-major axis, length of the semi-minor axis, flattening, latitude coordinates, reduced latitudes, etc. The aim of the method is to minimise the value of the output λ (i.e. when the results converge to a desired degree of accuracy):

When the difference between the current value of λ and the value of λ from the previous iteration is less than the convergence tolerance then the final stage of the Inverse Method can be executed:

Java code to calculate the distance between two points using Vincenty formula:

public static double getVincentyDistance(double lat1, double lon1, double lat2, double lon2) {

  double a = 6378137, b = 6356752.314245, f = 1 / 298.257223563;

  double L = Math.toRadians(lon2 - lon1);

  double U1 = Math.atan((1 - f) * Math.tan(Math.toRadians(lat1)));

  double U2 = Math.atan((1 - f) * Math.tan(Math.toRadians(lat2)));

  double sinU1 = Math.sin(U1), cosU1 = Math.cos(U1);

  double sinU2 = Math.sin(U2), cosU2 = Math.cos(U2);

  double cosSqAlpha, sinSigma, cos2SigmaM, cosSigma, sigma;

  double lambda = L, lambdaP, iterLimit = 100;

  do {

    double sinLambda = Math.sin(lambda), cosLambda = Math.cos(lambda);

    sinSigma = Math.sqrt( (cosU2 * sinLambda)

      * (cosU2 * sinLambda)

      + (cosU1 * sinU2 - sinU1 * cosU2 * cosLambda)

      * (cosU1 * sinU2 - sinU1 * cosU2 * cosLambda)

    );

    if (sinSigma == 0) return 0;

    cosSigma = sinU1 * sinU2 + cosU1 * cosU2 * cosLambda;

    sigma = Math.atan2(sinSigma, cosSigma);

    double sinAlpha = cosU1 * cosU2 * sinLambda / sinSigma;

    cosSqAlpha = 1 - sinAlpha * sinAlpha;

    cos2SigmaM = cosSigma - 2 * sinU1 * sinU2 / cosSqAlpha;

    double C = f / 16 * cosSqAlpha * (4 + f * (4 - 3 * cosSqAlpha));

    lambdaP = lambda;

    lambda =  L + (1 - C) * f * sinAlpha  
      * (sigma + C * sinSigma 
        * (cos2SigmaM + C * cosSigma
          *(-1 + 2 * cos2SigmaM * cos2SigmaM)
        )
      );

  } while (Math.abs(lambda - lambdaP) > 1e-12 && --iterLimit > 0);

  if (iterLimit == 0) return 0;

  double uSq = cosSqAlpha * (a * a - b * b) / (b * b);

  double A = 1 + uSq / 16384

      * (4096 + uSq * (-768 + uSq * (320 - 175 * uSq)));

  double B = uSq / 1024 * (256 + uSq * (-128 + uSq * (74 - 47 * uSq)));

  double deltaSigma = 

    B * sinSigma

      * (cos2SigmaM + B / 4

        * (cosSigma 

          * (-1 + 2 * cos2SigmaM * cos2SigmaM) - B / 6 * cos2SigmaM

            * (-3 + 4 * sinSigma * sinSigma)

              * (-3 + 4 * cos2SigmaM * cos2SigmaM)));

  double s = b * A * (sigma - deltaSigma);
  return s;
}

Why to use it: Vincenty is more accurate.

Why not to use it: It is more computationally intensive and will, therefore perform slower and increases battery drainage.

HOW DO YOU CHOOSE WHICH DISTANCE CALCULATION TO USE? A FEW IMPORTANT FACTORS:

A few important factors to considered when choosing formulas for calculating distance:

1. What are the requirements and use cases for your application?
2. How accurate do you need the distance calculation to be?
3. How fast do you need to do it?
4. Which method/implementation works best with the data you have?

As with anything “better” is a matter of your particular application. For your application, Vincenty may be an appropriate choice than Haversine. You will have to look at the particulars of your use cases and need of your application.

For Example: Let’s calculate the distance between Pune (PNQ) to Sydney (SYD) using Air Miles Calculator.

OBSERVATION:

Here we see that Haversine formula shows 6236.243 miles and Vincenty formula shows 6231.892 miles which is more accurate.

So, which one to use depends on your needs.

Choose the best fit!

References :

1. https://community.esri.com/groups/coordinate-reference-systems/blog/2017/10/11/vincenty-formula
2. https://www.airmilescalculator.com/distance/pnq-to-syd/
3. https://github.com/janantala/GPS-distance/blob/master/java/Distance.java