Generating Drive Time Polygons using Mapbox Directions API

I have been working on a project at work to build a mapping application to support the out of home advertising business which as you can imagine relies heavily on the geographical locations of assets, stores, audience etc. Its very important for us to have a rich set of geo-spatial querying tools which allow the users to interact with the map directly and derive meaningful insights from it.

Some of the most common ways for doing quick geo-querying on the map is by drawing shapes – circles, polygons, squares etc directly on the map to isolate the area that you are interested in. Fortunately, for us the open source Mapbox API already offered a drawing toolbox out of the box and that made things a lot easier as a lot of other APIs that I evaluated for e.g. OpenLayers 3, ArcGIS, Google Maps etc didn’t have this functionality or offered it in a way that would have taken us longer to build.

drawing-tools-and-shapes

One of the seemingly common use cases (certainly for us) is the ability to render a polygon on the map that is roughly indicative of the area that can be covered from a certain origin within “x” minutes of driving from it. The Mapbox JavaScript API however doesn’t provide this feature by default, so I decided to build it using the existing tools. But how?

Here’s the thought process that went into developing the algorithm, to start off the inputs were:

a) the origin lat/long where the journey would start from. This would be established by user clicking on the map.

b) the time in minutes from the origin to drive for. Users would key this in before selecting their origin point.

Using the time input and assuming an average driving speed of 70mph, I can find out the longest “line of sight” distance that can be covered within that time using the classic Distance = Speed x Time formula. Given the origin coordinates, I can then somehow find the end coordinates that are “distance” miles away from the origin. I can then use Mapbox’s Directions API to compute the directions from the origin to these destination coordinates.

Now, the actual route will most likely be longer than the line of sight distance that I computed earlier but that’s OK because the response from the Directions API includes turn by turn navigation instructions that contains a running total of the time spent so far, the distance covered so far and the coordinates of the current turn point. From these instructions I can extrapolate the coordinates that CAN be reached within the target drive time, backtracking when I overshoot the target time and storing the resultant lat/long into a collection. The screenshot below shows the idea as a sketch, its the inner target polygon that I was interested in. The vertices of the polygon are all the points that can be reached within “x” minutes of driving.

drive-time-algo1

I will then repeat this process in a circular fashion rotating by 10 degrees clockwise each time and returning the extrapolated lat/longs at the end. From these lat/longs, I will somehow construct a polygon and render it on the map (example shown below).

sample-drive-time-5-min

As you can see there are a lot of “somehow”s i.e. unknowns in the above algorithm and the API that helped solved all of them is called turf.js. Its a lightweight JavaScript geo-spatial processing library that allows you to calculate those unknowns. It uses GeoJSON to represent shapes so its very easy to construct a concave hull i.e. a polygon from a bunch of lat/longs and add it to the GeoJSON aware Leaflet map (the base for Mapbox’s map).

For the open source JavaScript implementation of this algorithm, head over to my Github account. Its not yet an official Leaflet plugin, but my hope is one day it will be worthy enough to be.

Tagged with: , , , , , , , , , , , , , , , , ,
Posted in Algorithms, Geo-spatial, GIS, Mapping

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories
Follow Artineering on WordPress.com
Links
%d bloggers like this: