Finding the distance between two latitude, longitude points is a small but important function of our favorite apps and gadgets. When building campnear.me, a web platform for camping in the Pacific Northwest, I knew distance would be an important feature for searching campgrounds. In this post I’ll cover several ways to measure geographic distances and how to decide what works best for your application.
Geographic distance
Distance between two points… sounds like that Pythagoras guy from junior high algebra
While it is true that the distance between two cartesian points on a plane can be derived from the Pythagorean Theorem, two points on the earth need to be handled differently. A plane[1]:
- Is an infinite, flat surface
- Has the same unit of length for both the X and Y axis
Interestingly, Pythagoras was believed by some to be the first person to assert that the Earth was unlike a cartesian plane in that it was NOT flat, violating #1 above. Besides not being flat, the units of measure on the X (Longitude) and Y (Latitude) axises of the earth have varying lengths of measure, so we can forget about #2 as well. How do we deal with these non-cartesian plane realities of earth? Besides be glad that we can’t actually sail off the end of the thing, lets take a look at how we can approach the different units of latitude and longitude.
Latitude and Longitude
Lets start with Latitude. Looking at the distance between latitudinal lines, we can see that this distances increases slightly as we move toward the equator. On the Longitudinal side, we see that the distance between lines varies quite a bit between the equator and the poles. Close to the equator, the distance between lines of longitude are large, whereas close to the poles these distances are small. You can see the difference in the changes in latitude vs longitude in this delta lat/long chart on wikipedia
Put another way, as you head north or south in latitude, the distance between lines of longitude becomes smaller. So the distance between the longitude of two points is dependent on the latitude of those points. A rough approximation is [2]:
1 deg of longitude = 111.320*cos(latitude) [km]
or 69.17*cos(latitude) [miles]
where latitude is expressed in degrees
As we saw in the map images above, the distance between latitudes changes slightly as we move away from the equator, but not significantly. A rough approximation of a degree of latitude is [2]
Latitude: 1 deg = 110.574 km or 68.69 miles
So, while our axis units of measure are not of equal length, there is a way for these points to be related to each other. This gets us a bit closer to being able to take the distance between them.
A simple approach
One interest I had in calculating distance was to find campgrounds within a distance “r” of Portland. As a coarse and quick approximation, my first method was to use a bounding box, with the origin set for Portland.
By finding the bounding latitudes and longitudes I would have a set of coordinates to check my campgrounds against.
With the above relationships, we can convert miles into approximate lat and long offsets.
For latitude, we know that 1 degree is about 69 miles. Lets say we wanted to look for campgrounds within 10 miles of Portland, r = 10. By dividing 10 by 69 miles/degree I get an offset of 0.145 degrees. Applying these to the origin latitude of Portland:
Upper latitude = 45.5231 + 0.145 = 45.6681
Lower latitude = 45.5231 – 0.145 = 45.3781
which gives us the latitude bounds; any campgrounds with a latitude in [45.3781, 45.6681] could be part of our r=10 set.
Longitude is a little more involved, since our longitudinal distance will vary by the latitude we are measuring it at. As an approximation, I used the upper latitude for calculating the longitudinal distance from the origin to the left longitudinal bound:
1 degree left longitude = 69.17*cos(45.6681) = 48.337 miles
Dividing our r of 10 miles by 48.337 gives us 0.207 degrees. On this half of the world longitude goes up as we move west, so to get the left longitude we add the offset of 0.207 degrees to our origin:
Left longitude = 122.6765 + 0.207 = 122.8835
Repeating the same calculations for the right longitude using the lower latitude:
1 degree right longitude = 69.17*cos(45.3781) = 48.587
offset: 10 / 48.587 = 0.206
Notice how close our offsets are using the different latitudes; the change in latitude for r=10 isn’t significant enough to see a big change in our degree/mile ratio for longitude. It would be interesting to see at what r the offsets diverge significantly.
Right longitude = 122.6765 – 0.206 = 122.4705
Great! So now we have a bounding box to check our coordinates against. If a campground lies within [(45,6681,122,8845), (45.3781,122.4705)] then it is roughly within 10 miles of Portland, with campgrounds in the corners of our bounding box being 10√2 miles away.
The round(ish) earth
So far we have a crude way of finding points around an origin, but there are more accurate ways of doing so. There are a few different ways to calculate the distance between geographic points that take our roundish earth into consideration. The earth is really a spheroid, a spherical ellipsoid, which is a kind of smushed sphere. Very technical. Think of the the head crusher. The Haversine formula is fast, but is accurate for spherical shapes, not spheroid shapes. The Vincenty formula is slower, but extremely accurate for spheroidal shapes like the earth. How do you choose which distance calculation to use? A few important factors:
- How accurate do you need the distance calculation to be?
- How fast do you need to do it?
- What method / implementation works best with the data you have?
Speed
For a location based web app like campnear.me you can pre-calculate distances for popular locations. If the user is not in one of the pre-calculated locales you can run the distance calculation on the fly, caching the result for future use. I focused on camping near Portland, OR so I chose to run the distance calculation offline, meaning speed wasn’t a concern. Either Haversine or Vincenty would meet my needs here.
Accuracy
I was using the distance calculation in a variety of places, some needed high accuracy and some did not. I could either just use Vincenty or use a mix of Haversine and Vincenty for the corresponding calculations.
Implementation
Ultimately I chose to go with Vincenty, in a large part due to the vincenty python module. It is incredibly straight forward and easy to use with lat/long points, with a command line flag for specifying miles or kilometers. Lets take a look at some examples. You can get the code on my github. You will need Python 3.4.3 and vincenty-0.1.4 which you can get via “pip3 install vincenty” at the time of this writing.
First lets import the vincenty library and create some lat/long points to measure distance between.
Next, we will try out the vincenty function. Default output is in kilometers unless you set miles=True
How about computing the distance from Portland to all three campgrounds? We can create a function that will calculate the vincenty distance from Portland to any point we pass in via the variable cg_point:
Now, we can use the map() function on the list of campground points to calculate the vincenty distance from Portland:
Better together
While I could just run vincenty on every point in my database, its faster to eliminate campgrounds clearly outside of the radius of interest through the bounding box method. I can then apply vincenty, a slower algorithm, to a smaller set of points. This technique is described here, with some sample SQL queries using BETWEEN and HAVING to do the boundary boxing and apply a great circle distance measurement, which you could replace with haversine or vincenty.
Another option is to use GIS extensions for popular databases like MySQL. This enables you to store your latitude and longitude as point fields, and provides built in functions for finding points in a minimum bounding box (MBR) and distance calculations
In this post we’ve learned how to find the distance between two points on a spheroid, that is, the distance between two points as the crow flies. It may give us a rough approximation of distance between two places, but its not the distance we would cover if we were trying to travel between these two places. For this I would refer you to the Google Distance Matrix, which is a great resource for calculating travel distance and times between places, and perhaps a future blog post. 😉