How to draw a travel time boundary on Google Maps

If you have a specific destination in mind, then Google Maps is perfect for estimating how long it will take to get there, by various modes of travel. But if you just want to know how far you could travel from a given address in an hour, then it isn't much help.

Perhaps you're visiting somewhere new and just want to see what you could walk to within an hour of your hotel. Or you want to make a day trip somewhere and want to see where you could drive in a couple of hours.



I decided to build a website where you could enter an address, a travel time, and a travel mode (e.g. driving). It would then generate a map using JavaScript showing the origin, and drawing a boundary that represented how far you could travel. It's not as straightforward as drawing a circle at a given distance from the address. Depending on the routes available by the selected mode of travel, you may be able to travel further in some directions than others. Here is an outline of the approach that I took.

  1. Ask Google for the LatLng (Latitude and Longitude) of the starting address
  2. Calculate the LatLng of a set of evenly spaced destinations around the origin
  3. Ask Google for the travel time to each of those destinations
  4. Calculate a new distance estimate for each bearing based on this travel time
  5. Repeat steps 3 and 4 for a given number of iterations
  6. Pick the destinations at each bearing with the travel time closest to that entered
  7. Draw this boundary on the map

Ask Google for the LatLng (Latitude and Longitude) of the starting address

To get the Latitude and Longitude of a given address I used Google's geocode function. You pass the address and a callback function which Google will call with a status indicating whether it succeeded, and what the coordinates were.

var address = "London, England";
geocoder = new google.maps.Geocoder();
geocoder.geocode({
 'address': address
}, function(results, status) {
  if (status == google.maps.GeocoderStatus.OK) {
    var origin = {lat: results[0].geometry.location.lat(), 
                  lng: results[0].geometry.location.lng()};
  } else {
    alert('Google did not recognize the address you entered [' + status + ']');
  }
});

Calculate the LatLng of a set of evenly spaced destinations around the origin

For a first approximation, I started with 25 points at a fixed distance from the origin, arranged in a circle. The radius of the circle was calculated from the travel time and travel mode entered. For driving I assumed 55 miles per hour, for walking 2.5 miles per hour, etc. At first I just used simple trigonometry to calculate the offset latitude and longitude from the origin. But when I looked at my resulting circle on Google Maps it was very squished. Which was when I remembered that the distance on the earth between two longitudes varies by latitude.

So I needed to use the Haversine Formula to calculate the appropriate Lat/Lng of each destination. I found a useful article "Calculate distance, bearing and more between Latitude/Longitude points". The author had done most of the heavy lifting of translating these formulas into JavaScript. I had a little trouble at first because I forgot that Google was providing the Latitude and Longitude in degrees, while the formulas expected radians. But once I made that conversion they worked perfectly. Here is the resulting function

// distance is in miles, bearing in radians
function calculateDestination(origin, distance, bearing) {
  var earthRadius = 3959;
  var lat = origin.lat * Math.PI / 180;
  var lng = origin.lng * Math.PI / 180;
  var destLat = Math.asin( Math.sin(lat) * Math.cos(distance/earthRadius) +
                           Math.cos(lat) * Math.sin(distance/earthRadius) * 
                           Math.cos(bearing) );
  var destLng = lng + Math.atan2( Math.sin(bearing) * 
                                  Math.sin(distance/earthRadius) * Math.cos(lat),
                                  Math.cos(distance/earthRadius) - Math.sin(lat) *
                                  Math.sin(destLat) );
  return {lat: destLat * 180 / Math.PI, lng: destLng * 180 / Math.PI};
}        

Ask Google for the travel time to each of those destinations

Google imposes usage limits on the Google Maps API, and I wanted to try and be as efficient as possible about the number of calls I made. Fortunately I came across the DistanceMatrixService which allows you to pass up to 25 origins and 25 destinations in a single call. So I decided that I would use 25 points around the circle, allowing each iteration to just be a single call to Google.

Working with the DistanceMatrixService is similar to the Geocoder. One of the parameters you pass is a callback function which Google calls with the results.

service.getDistanceMatrix({
  origins: [origin],
  destinations: boundaryCoordinates,
  travelMode: travelMode,
  unitSystem: google.maps.UnitSystem.IMPERIAL,
},function (response, status) {
  if (status !== google.maps.DistanceMatrixStatus.OK) {
    alert('Error calculating distances: ' + status);
  } else {
    var results = response.rows[0].elements;
    for (var i = 0; i < results.length; i++) {
      if (results[i].status == google.maps.DistanceMatrixStatus.OK) {
        // results[i].distance.text is the travel distance, e.g. "23.2 mi"
        // results[i].duration.value is the travel time in seconds
      }
    }
  }
});

Repeat steps 3 and 4 for a given number of iterations

It's unlikely that the first response will match the desired travel time. For example, let's suppose you entered 60 minutes. This means we picked a destination 55 miles away from the origin. Depending on the layout of roads the travel time to this destination might be 90 minutes. So now we will estimate a new destination distance. In this instance we are trying to get to a travel time that is 2/3 the actual value. So we try 2/3 of the travel distance - or 36.67 miles. We do calculation for each of the 25 points.

After the second iteration you now have 2 data points for each bearing (plus the data point that 0 travel time will always be 0 miles). So you need to pick the 3rd distance based on all this data. It wasn't obvious what the best approach to this would be. As a first pass I tried an averaging approach where I calculated based on each data point where the desired destination should be, and then just averaged all of those. This worked pretty well, but there were certain situations where it would get confused. In particular, there are times where you can drive to a point further away quicker than you can drive to a closer point, just because of the arrangement of the roads.

More confusing than this is that there are times when you pick a destination and it turns out to be one that you simply can't travel to. Either because it is too far from a road, in the middle of an airport, or in a lake or ocean. So for a given bearing, if I received a valid travel time, I needed to use one approach to estimate the next distance. And if I received an error, I had to use a different approach.

I tried simple linear regression, but it didn't prove to be very accurate because of some of the problems above. One of the breakthroughs was realizing that there was a fairly well defined upper and lower boundary to the distance I was trying to find. If I was trying to find a distance that I could drive to in 60 minutes, then I could assume it wouldn't be more than 100 miles. And it seemed reasonable to also assume that it wouldn't be less than 10 miles. So if any of my estimation approaches calculated a distance outside of this boundary, I could throw it away.

I'm sure the approach can be improved. The current implementation is in the functions aboveBelowEstimator() and minMaxGuessor() and you can review them by following the links below to the code.

Pick the destinations at each bearing with the travel time closest to that entered

I made the number of iterations configurable. I found that with 3 iterations you could get a fairly good approximation, especially in places without lots of lakes, or close to the ocean. And I found that after 9 iterations there was diminishing returns. If you couldn't find reasonable destinations at each bearing after 9 iterations, then you were probably never going to find them. The more iterations you used, the longer it took to run. This is especially true, because after 3 consecutive calls to the distance matrix service, Google falls the next call with an overuse message. So I had to implement delays. And I made it configurable how many iterations that you wanted to run, by having an "Accuracy" setting.

Once all those iterations ran, I needed to pick the best destination at each bearing. It's not always the case that the last attempt has the closest travel time to the one desired. And it's also possible that you never found a destination at a particular bearing with a travel time close to the one desired. Or even with any legal travel destinations at all. This is especially true when using the "Transit" travel mode, or picking an origin next to the ocean.

So for each of the 25 bearings I either pick a destination with a travel time closest to the one desired, or I mark it as unreachable. In the resulting map I show this by putting a green mark on the boundary where I found a reachable destination, and a black mark where I didn't. 

Draw this boundary on the map

To draw the map I used google.maps.Map, then google.maps.Polyline. And lastly, to put the green and black markers I used google.maps.Marker. Each of these are fairly simple API with no need for a callback function. Here's what each of them look like

var mapCanvas = document.getElementById('map');
var mapOptions = {
  center: results[0].geometry.location,
  zoom: 7,
  mapTypeId: google.maps.MapTypeId.ROADMAP
};
map = new google.maps.Map(mapCanvas, mapOptions);

I draw the map when the geocoder first returns the coordinates, so results[0].geometry.location is the response from the geocoder.

boundaryCoordinates.push(boundaryCoordinates[0]); // complete the loop
var boundaryPath = new google.maps.Polyline({
  path: boundaryCoordinates,
  geodesic: true,
  strokeColor: color,
  strokeOpacity: 1.0,
  strokeWeight: 5
});
boundaryPath.setMap(map);        

Here boundaryCoordinates[] is the array of 25 destinations that were picked from the previous section (implemented as pickBest() in the code). While we are iterating through them we just work with this array. But before we draw it as a polyline, we have to "complete" the loop, by adding the first coordinate at the end of the array, otherwise the resulting boundary will have a gap.

var marker = new google.maps.Marker({
    position: {lat: boundaryCoordinates[i].lat, lng: boundaryCoordinates[i].lng},
    map: map,
    icon: {
      path: google.maps.SymbolPath.CIRCLE,
      scale: 3,
      strokeColor: color,
    },
    title: title
  });

And this is an example of drawing one of the circle markers on the boundary. For each green circle mark I include details like the direct-distance, travel-distance and travel-time in the title. This makes that information available in a hover text over the marker. I also draw a red circle mark at the origin, and include information about how accurate the boundary is (how close to the desired duration) in the hover text.

Next Steps

If you want to try it out, I have it running at "travel-time-circle". I'd be grateful for a comment if you try it.

It has had minimal testing, so you're likely to run into a few problems. If you want to try fixing it yourself, you can pull the github repository for the travel-time-circle project. I'd be grateful if you can let me know of any problems you encounter, either by posting in a comment, or reporting an issue in the travel-time-ecircle github project. If you report a problem, please include the street address, travel time, travel mode and accuracy exactly as you entered them. And also your browser and operating system.

And lastly, if you think of any ways that it can be improved, please post a comment letting me know your idea.

6 comments:

  1. I really like this ... it reminds me of a related problem. When traveling from Point A (e.g. home in brooklyn) on a roadtrip to Point B (e.g. Lincoln, MA) what are interesting places to stop that are not too out of the way.

    ReplyDelete
    Replies
    1. Thanks. Yes, that's another good question. Will have to look around and see if someone has already built that. Not even sure how to identify interesting places on the map.

      Delete
  2. This is awesome. Is their anyway i could downloade the results as KML files?

    ReplyDelete
    Replies
    1. I know the Javascript API for Google Maps allows you to import KML files, but I don't think you can export them. So the only way I can see doing this would be to dynamically build the KML file based on the points that the script adds to the map. If anyone tries this, or knows of a simpler method to add it, please comment.

      Delete
  3. Great app! Is there a way I can get a list of zip codes or block groups (preferable) that are contained in the driving distance polygon? Thanks!

    ReplyDelete
    Replies
    1. Sorry, I don't know how to get to the zip codes.

      Delete