Isochrone Generation with the Google Maps API using a Quadtree

To go directly to the live demo, click: http://codepen.io/anon/pen/KdOzvO

Isochrones represent all points on a map that can be reached within a certain time limit from a given starting position, so they are basically contours for a time value. They have a range of useful applications, e.g. when buying a house one might want to check what places can be reached within half an hour. Naturally, isochrones differ every time a new starting position is chosen.

Following in the footsteps of Sandro Paganotti’s excellent demo, I will use the Google Maps Directions Service for data on travel duration. His demo used an earlier version of the Google Maps API that doesn’t work any more today, but his youtube video reveals the method: His script queries points which lie on lines that radially spread from the starting position.

I decided to take a different approach for two reasons:

  • Data collection by far the most costly part: for every point a request has to be sent to Google. Hence, I wanted to implement a method that samples sparsely and increases  sampling density only in regions of interest.
  • The radial approach produces blob or star shaped patterns. It ignores local extrema and fails to capture ‘U’-shaped isochrones:

Quadtrees meet the requirement for adaptive sampling nicely: if the isochrone passes through a square, this square can be subdivided to four smaller squares, adding more sample points. Provided that there is a minimum number of subdivisions, they can also capture local “islands” that can be reached as they might appear around public transport stops. I drew on several great resources online that demonstrate how quadtrees can be used for contours. What is different in this case is that new sample points can be obtained at will at any resolution and that evaluating a point takes so long that it has to be done asynchronously.

After a quadtree is constructed with the desired level of detail, marching squares is applied to convert the list of squares that contain the isochrone into an actual line. Marching squares has an ambiguous case for which we will simply split the square in question once more.

We can see that the quadtree structure really only begins to shine at medium to high numbers of sample points, but then it captures more detail and preserves shape better. One additional thing one can do to make the lines smoother is to use linear interpolation along the edges of the squares.

Conclusion

My method for generating isochrones from the Google Maps API uses quadtrees and adaptive sampling to create more detailed and accurate contours. It solves problems of local minima or “islands”. However, a lot more data points are needed than in the original method, so it takes longer.

Do try the live demo! It has pre-set values to find the boundary for 30-minute commute to the City.

For a more technical explanation of the script, click here.

Advertisements
Isochrone Generation with the Google Maps API using a Quadtree