A feature that we are sometimes asked for with our mapping products and solutions is “can you show a map of how far I can travel by car from X in Y minutes?”. I was recently inspired by a demo of the Masternaut fleet management system at the UK Virtual Earth partners day, that showed very nice detailed polygons of how far you could travel my car from a given point in a given time.
Now I’m sure Masternauts solution, which works almost instantly, has a massive backend data store to query all this information but it got me wondering if we could do a very simple version of this just using the data available from Virtual Earth?
How might we achieve this?
The basic process behind this idea is to create a set of “spokes” at evenly distributed angles around a centre point (the start location) like a bicycle wheel.
The diameter of the “wheel” being set to the maximum possible distance that could be travelled in a straight line from the centre of the “wheel”.
We then need to get the latitude and longitude of the point at the end of each “spoke” and use this to get directions, using Virtual Earth, from the centre of the “wheel” to each “spoke” end point.
We should then be able to go through the details of each “spoke” route returned and work out how far along the route we could get in the given time. This should give us a set of latitude / longitude points around the centre of our “wheel” indicating how far along each “spoke” we can travel in the given time, join them together in a polygon and you have your map!
So the basic process is:
1) Get X spoke point positions (lat / lon) at equal distance and equally distributed around a start point
2) Calculate the full driving directions from the start point to each of the X spoke positions
3) Go through each route returned and work out how far along the route we could travel in the given time, get the position (lat / lon) of this point
4) Add all the points from 3 and draw a polygon on the map showing the boundaries of the possible locations.
The Code
I would usually write this as a javascript class using the asp.net ajax libraries but to make it as readable as possible and portable to any framework it is coded as simple function calls with a few global variables.
First we have to work out the position of each end point of the “spokes”:
//starts the process of calculating the driving distances
function GetDrivingDistance(startpoint, mins, numspokes, maxspeedkmph) {
gmins = mins; //need to use later
gnumspokes = numspokes;
gstartpoint = startpoint;
//add original start point as pushpin to map
var pin = new VEShape(VEShapeType.Pushpin, startpoint);
gmap.AddShape(pin);
//calculate maximum distance possible in a straight line
//at the maxspeed
var maxdist = (maxspeedkmph/60) * mins;
gspokearray = new Array(); //new array to contain spoke VELatLong objects
groutesarray = new Array(); //new array to contain the VERoute objects calculated
//setup verouteoptions for directions
gropts = BuildRouteOptions();
//calculate position, in lat lon, of each spoke
//assuming maximum distance away
for (i = 0; i < numspokes; i++) {
var bearing = (360 / numspokes) * i; //get bearing of current spoke
gspokearray[i] = GetPointAtDistanceAndBearing(startpoint, maxdist, bearing);
//get first route between startpoint and spoke endpoint
//cannot call more than one GetDirections at once
if (i == 0) {
document.getElementById("progress").innerHTML = "Proccessing step 1 of " + gnumspokes;
//plot spoke
if (gdebug) gmap.AddShape(new VEShape(VEShapeType.Pushpin, gspokearray[i]));
//get directions
gmap.GetDirections(new Array(startpoint, gspokearray[i]), gropts);
}
}
}
This function starts by setting some global variables and then adds a pushpin to the map at the location of the supplied VELatLong startpoint parameter.
The we calculate the maximum possible distance coverable in a straight line at the parameter maxspeedkmph (max speed in km per hour).
Then we setup a few arrays for storing results in later, and create the VERouteOptions class to be used in all routing (see full code for function BuildRouteOptions). The route options set a callback method called OnRoutingComplete when the route is complete
Now we loop through the number of spokes requested (parameter numspokes) and work out the bearing of each spoke around the start point using the GetPointAtDistanceAndBearing method (see full code).
After updating the UI with our progress we optionally plot the spoke end point if the code is in debug mode (see full code) just so we can see what is going on.
Finally we fire off the first request to VEMaps GetDirections method for the first spoke point.
When the GetDirections is complete the OnRoutingComplete function is called:
//the callback function when a route completes
function OnRoutingComplete(result) {
//add new route to groutesarray
groutesarray.push(result);
if (groutesarray.length == gnumspokes) {
//now all routing is complete start next stage
ProcessDrivingRoutes();
}
else {
//update progress
document.getElementById("progress").innerHTML = "Proccessing step " + (groutesarray.length + 1) + " of " + gnumspokes;
//debug plot spoke and route end
if (gdebug) {
gmap.AddShape(new VEShape(VEShapeType.Pushpin, gspokearray[groutesarray.length]));
if(result.Distance>0) gmap.AddShape(new VEShape(VEShapeType.Pushpin, result.RouteLegs[0].Itinerary.Items[result.RouteLegs[0].Itinerary.Items.length-1].LatLong));//end of route, to see how close it got to spoke
}
//get next route
gmap.GetDirections(new Array(gstartpoint, gspokearray[groutesarray.length]), gropts);
}
}
This adds the returned VERoute object to an array for processing later and then either calls ProcessDrivingRoutes if all routes have been completed or calls itself again with the next “spoke” position.
Once all routes have been completed the ProcessDrivingRoutes function is called:
function ProcessDrivingRoutes() {
var pointsarray = new Array();
var numroutesnotfound = 0;
//process each route result
for (i = 0; i < gnumspokes; i++) {
//check route found, or if was in middle of sea etc so nothing returned!
if (groutesarray[i].Distance > 0) {
//work out how far down route we can actually get in the time supplied
var totaltime = 0;
for (var ii in groutesarray[i].RouteLegs[0].Itinerary.Items) {//will only be one RouteLeg
//is current leg time greater than time supplied?
var items = groutesarray[i].RouteLegs[0].Itinerary.Items;
totaltime += items[ii].Time; //calculate the cumlative time of the route so far
if (totaltime >= gmins * 60) {
//work out average speed between this point and the last
var routetimesecs = items[ii - 1].Time;
var avspeedkmph = 0
//check route time is greater than zero, as some itineraries can have zero time and distance
if (routetimesecs > 0) {
avspeedkmph = items[ii - 1].Distance / (routetimesecs / 360);
}
//work out aprox how far along route between this point and the previous
//you can get in the remaining time at the average speed
var timeleftsecs = (gmins * 60) - (totaltime - items[ii].Time); //time left from previous point
var maxdist = (avspeedkmph / 360) * timeleftsecs;
//work out bearing between previous point and this one
var bearing = GetBearingBetweenPoints(items[ii - 1].LatLong, items[ii].LatLong);
//work out new point along route between previous point and this one
//that can be reached in the remaining time
var newpoint = GetPointAtDistanceAndBearing(items[ii - 1].LatLong, maxdist, bearing);
pointsarray.push(newpoint);
break; //exit loop as have maximum point reachable in time given
}
}
}
else {
numroutesnotfound++;
}
}
//debug
if (gdebug) {
alert("routes not found: " + numroutesnotfound);
alert("routes found: " + pointsarray.length);
}
//we have all our maximum points in each direction
//now draw the polygon representing the points
var poly = new VEShape(VEShapeType.Polygon, pointsarray);
poly.HideIcon();
gmap.AddShape(poly); //add to map
gmap.SetMapView(pointsarray);
//reset button
document.getElementById("btnCalc").disabled = false;
document.getElementById("btnCalc").value = "Calculate";
document.getElementById("progress").innerHTML = "Proccessing complete";
}
This loops through the routes returned in the groutesarray and first checks if the route has any distance, if it doesn’t we ignore it as is means a route could not be found between the startpoint and a specific “spoke” end point.
Now we loop through each stage of the route (there will only be one route leg) working out how far we can get along the route before the maximum time in minutes (as supplied to GetDrivingDistance as parameter mins) is exceeded.
Once we find the 2 stages of the route that are either side of the maximum time we calculate the distance between the 2 stages of the route and the average speed along that part of the route (distance travelled / time taken). We can then work out the distance from the first of the 2 route stages to the final position possible to reach in the time given, and the direction of travel in degrees between the 2 stage’s start points. Finally we can work out the position (lat / lon) of this final reachable point by calling the GetPointAtDistanceAndBearing function again (see full code).
Now we have the point which we can reach along the route to the end point of the “spoke” in the given time limit. Finally we add this to an array and draw all the points in the array as a polygon on the map, zooming the map out using SetMapView so we can see the whole polygon.
So does it work?
As you can see in the demo, it does indeed plot a drive time polygon, which improves its accuracy as you increase the number of spokes. You can manually check a location within the polygon to confirm that you can actually reach it within the given time, and most of the time that works.
However there are a few issues…
What doesn’t work?
Well unfortunately there is a lot that doesn’t work:
1) Try centering the map near a costal region, you will see quite often the polygon drawn does not even include the start point. This is either because Virtual Earth used shipping lines to get a route (which head inland first to get to the port), or could not even find a route out to the middle of the sea.
2) Even in inland locations if there is not a road even remotely close to the end point of a spoke Virtual Earth will get a route to the nearest road which may be miles away in any direction. To see this for yourself change the gdebug global variable to true and see each spoke end point and each route end point ploted on the map, many of which are far apart.
3) Often the polygons points end up not plotting in order of increasing degrees around the start point mostly due to point 2 above. This can lead to points in the polygon crossing over as below:
4) Its SLOOOOOOWWW. As we seem to only be able to call one GetDirections at a time it takes forever to plot a map with a high number of spokes.
5) Exactly how accurate or even useful the results are is certainly questionable
6) It will of course not work if directions are not available in the region the map is covering.
7) Routes to the endpoint of the spoke might go a long way off the angle of the “spoke” to get to the final destination so getting a point along this route is never going to give a really accurate answer to the problem.
How could it be made better?
There are lots of simple ways this could be made to work better including:
1) Using country boundaries to work out when we are asking for a route in the sea and instead ask for a route to the very edge of the coast.
2) Fix the polygon points so they are in order when plotting on the map which should remove the crossing over effect discussed above.
3) Right now we are using the routleg itineraries to plot the data but these are not the exact route points but only the turn by turn points so are not as accurate. With a commercial account we could get to the full route data which might be able to be used to get a more accurate position of the polygons points.
Got an idea to make this better?
Do you have an idea for making this work better? Please add it to the comments below.
