Distance Calculations Using Latitudes and Longitudes

The corners of the bounding box give us the maximum and minimum values for latitude and longitude, which we will use to find all points satisfying the following inequalities:

Min Latitude <= Latitude <= Max Latitude

Min Longitude <= Longitude <= Max Longitude

We could have used a bounding circle for this problem, however this would be inefficient. For example, if we had 100 locations to filter down, using a circle we would have to calculate the distance between the new point and each existing point, before selecting all points where this distance is below a certain value. In this example we would need 100 calculations, whereas using a bounding box allows us to use only four calculations before executing the data retrieve.

To calculate the bounding box coordinates, we find the length of one degree of longitude in kilometres and likewise find the length of one degree of latitude in kilometres. Using this it becomes simple to convert the kilometre distance into degrees of latitude and longitude away from the new point. Degrees of latitude remain almost constant, whereas, degrees of longitude vary greatly.

Suppose we have a set of coordinates (X1,Y1), where X1 is the latitude and Y1 is the longitude.

Degrees of latitude vary from 110.574 km at the equator to 111.694 km at the poles. One degree of latitude can be approximated to 111 km for our calculations.

Hence, the latitude of a point d kilometres away will be:

Degrees of longitude vary much more greatly from 111.320 km at the equator to 0 km at the poles. The approximation for 1 degree of longitude = cos(Latitude)*degree length of longitude at the equator.

Hence, the latitude of a point d kilometres away will be:

Using these equations, we can generate four new points surrounding the original. (Min Latitude, Min Longitude), (Max Latitude, Min Longitude), (Min Latitude, Max Longitude) and (Max Latitude, Max Longitude). These are the coordinates of the bounding box around the original point. We are interested in any points whose latitude is between the minimum and maximum and whose longitude is also between the minimum and maximum.

Haversine formula

The bounding box allows us to determine whether a point is within a certain distance of another point but does not provide us with the value of the distance between the two points. For this we need to use the Haversine formula. The Haversine formula finds great circle distance between two points given their latitudes and longitudes. “The great-circle distance or orthodromic distance is the shortest distance between two points on the surface of a sphere, measured along the surface of the sphere (as opposed to a straight line through the sphere's interior)”. This formula allows us to determine how close two points are and make comparisons between these distances. To find this distance, we simply enter the latitude and longitude of our two points into the following formula:

Haversine formula:

Google driving distance

In order to analyse realistic driving routes that include the new location, we need to know driving distances between locations. Google’s Distance Matrix API provides information on travel time and distance, documented here: https://developers.google.com/maps/documentation/distance-matrix/intro

We provide a single origin with multiple destinations, given by their latitude and longitude. This returns the distance between the origin and each destination. The API will allow multiple origins and multiple destinations, returning the distances between each origin and destination combination. We’ve utilised this API as a way of comparing distances from one location, to each location in a list. Below is an example response for driving distances from Worcester to Liverpool and Birmingham:

Summary

Distance calculations can be extremely useful when working with location data. The above calculations provided methods of manipulating the data and comparing distances with the accuracy we required. Depending on the distance chosen for the bounding box calculations, some locations with shorter driving distances may have been discarded, but this can be set to a suitably large value as to include most of the relevant data. Once we’d used the bounding box calculation to narrow the initial list of locations to a certain area, we were then able to analyse routes accurately using the other two distance calculations.