Calculating geographic distances in location-aware apps

If you are developing a location-aware application, you may reach a point where you need to know the distance between two geographic locations, such as the user's current position and some destination point like a city, airport, or attraction. The Location API in Windows 8 and the LocationManager class in Android, however, report positions in latitude and longitude as do most global services that map geographic names to a position on the earth. Latitude and longitude are really polar coordinates in three dimensions which give angles from the center of the earth relative to the equator and the prime meridian, respectively. Given these angles, how does one calculate the shortest distance that can be presented to the user in a more convenient form, such as miles or kilometers?

Great-circle distance

The answer is to use great-circle distance calculations. The Earth is very nearly spherical, and for general distance measurements one can assume that it is a sphere with an average radius of 6371.01 kilometers. The shortest distance between any two points on a sphere is an arc along a great circle, which is the circle formed on the surface of a sphere when it is evenly divided into two hemispheres. You define your great circle to pass through your source and destination points on the globe, and for any two points (that are not polar opposites) there is only one great circle that can pass through them.  Because they offer the shortest distance between two points, great circles are frequently used as the basis for aircraft routes when flying long distances (though geopolitical restrictions and atmospheric conditions do have a significant impact on flight planning).

The figure below shows the great circle defined by the cities of Portland, OR in the USA and London, England. The shortest distance between the two cities is shown by the solid red arc.

The shortest path between Portland and London passes through Canada and the southern half of Greenland.

There are multiple formulae for calculating the distance along an arc on a great circle, but I prefer the method known as the "spherical law of cosines" because its trig functions do not contain any singularities. This function works equally well at all points on the Earth, including near the poles, for points that are very close together, and for points that are polar opposites.

The distance, d, is defined as:

d = r * arccos( sin(Φ1) * sin(Φ2) + cos(Φ1) * cos(Φ2) * cos(λ2 - λ1) )

In this formula, r is the radius of the sphere which we can assume is 6371.01 km for the Earth, the latitudes of our two points are Φ1 and Φ2, and the longitudes are λ1 and λ2. Note that trig functions in virtually all programming languages use angles defined in radians, not degrees. To convert degrees to radians, you multiply by π/180. Plugging in the latitude and longitude for Portland (obtained from GNIS) and London (obtained from the GEOnet Names Server):

Portland: 45.5371781 N, -122.6500385 E

London: 51.5141667 N, 0.0936111 E

Distance: 7912.891 km (4916.841 miles)

Code

Below are some code snippets that can be used to calculate great circle distances in kilometers between two points. You pass the latitude and longitude (in decimal degrees) for the first point as lat1 and long1, and for the second point in lat2 and long2.

For Windows 8 developers, here is an implementation in C#:

```static class GreatCircleDistance
{
static Double degToRad= Math.PI / 180.0;

static public Double kilometers (Double lat1, Double long1, Double lat2, Double long2)
{
Double phi1 = lat1 * degToRad;
Double phi2 = lat2 * degToRad;
Double lam1 = long1 * degToRad;
Double lam2 = long2 * degToRad;

return 6371.01 * Math.Acos( Math.Sin(phi1) * Math.Sin(phi2) + Math.Cos(phi1) * Math.Cos(phi2) * Math.Cos(lam2 - lam1) );
}
}
```

And in JavaScript:

```function distanceKilometersGreatCircle (lat1, long1, lat2, long2)
{

return  6371.01 * Math.Acos( Math.Sin(phi1) * Math.Sin(phi2) + Math.Cos(phi1) * Math.Cos(phi2) * Math.Cos(lam2 - lam1) );
}
```

For Android developers, an implementation in Java:

```class GreatCircleDistance
{
public static double kilometers (double lat1, double long1, double lat2, double long2)
{
static double degToRad= Math.PI / 180.0;
double phi1 = lat1 * degToRad;
double phi2 = lat2 * degToRad;
double lam1 = long1 * degToRad;
double lam2 = long2 * degToRad;

return 6371.01 * Math.acos( Math.sin(phi1) * Math.sin(phi2) + Math.cos(phi1) * Math.cos(phi2) * Math.cos(lam2 - lam1) );
}
}
```

But the Earth isn't a sphere!

Yes, yes, the Earth is not a perfect sphere: it's an oblate spheroid, flattened slightly at the poles and bulging around the equator. The equitorial diameter is roughly 6,335.43 km and the polar diameter is about 6,399.59 km. Using a spherical approximation means you'll be, at best, within about 0.5% of the true distance and for casual applications that is probably good enough. If, however, your goal is scientific use where you require much higher accuracy, then you should look at something like Charles Karney's GeographicLib for more precise modeling.

§

Calculating a bearing between points in location-aware apps

For more complete information about compiler optimizations, see our Optimization Notice.
Categories:
Tags: