Feeds:
Posts
Comments

Archive for December, 2011

In a current  project, I need to pass an array of locations in to my Google map, and have the API find the directions between them. Google Maps API v.3 limits each directions request to a start point, an end point, and 8 waypoints in between. I need to be able to route more than this. The solution, essentially, is to break my list of stops down into groups, make multiple requests to Google, and stitch the results together when they come back.

This was (of course) a bit more easily said than done. For one thing, you cannot simply split your array into groups of 10, because you need to include the last stop of one array as the first stop of the subsequent array, otherwise there will be gaps in your route. That is, given an array of stops like this (and assuming the Google API max is 4, not 10 to keep the numbers lower):

[a,b,c,d,e,f,g,h]

I need a result like this:

[[a,b,c,d],[d,e,f,g],[g,h]]

So I wrote the following to create a multidimensional array of waypoints, that I can later iterate through and make requests on:

var batches = [];
var itemsPerBatch = 10; // google API max - 1 start, 1 stop, and 8 waypoints
var itemsCounter = 0;
var wayptsExist = stops.length > 0;

while (wayptsExist) {
	var subBatch = [];
	var subitemsCounter = 0;

	for (var j = itemsCounter; j < stops.length; j++) {
		subitemsCounter++;
		subBatch.push({
			location: new window.google.maps.LatLng(stops[j].Geometry.Latitude, stops[j].Geometry.Longitude),
			stopover: true
		});
		if (subitemsCounter == itemsPerBatch)
			break;
	}

	itemsCounter += subitemsCounter;
	batches.push(subBatch);
	wayptsExist = itemsCounter < stops.length;
	// If it runs again there are still points. Minus 1 before continuing to
	// start up with end of previous tour leg
	itemsCounter--;
}

In this sample, my ‘stops’ object is a rich object array, but as long as it contains your stops’ latitudes and longitudes, you’re set. Just update the location property above to match *your* stops object.

So at the end of this, we should have a two-dimensional array with a list of a list of waypoints. In the following method, we pass in this newly created multi-dimensional array (batches), a google.maps.DirectionsRenderer object (directionsDisplay), and a google.maps.DirectionsService object (directionsService). These latter two I have newed up in the calling code, and just send along references.

calcRoute: function (batches, directionsService, directionsDisplay) {
	var combinedResults;
	var directionsResultsReturned = 0;

	for (var k = 0; k < batches.length; k++) {
		var lastIndex = batches[k].length - 1;
		var start = batches[k][0].location;
		var end = batches[k][lastIndex].location;

		// trim first and last entry from array
		var waypts = [];
		waypts = batches[k];
		waypts.splice(0, 1);
		waypts.splice(waypts.length - 1, 1);

		var request = {
			origin: start,
			destination: end,
			waypoints: waypts,
			travelMode: window.google.maps.TravelMode.DRIVING
		};
		directionsService.route(request, function (result, status) {
			if (status == window.google.maps.DirectionsStatus.OK) {
				if (directionsResultsReturned == 0) { // first bunch of results in. new up the combinedResults object
					combinedResults = result;
					directionsResultsReturned++;
				}
				else {
					// only building up legs, overview_path, and bounds in my consolidated object. This is not a complete
					// directionResults object, but enough to draw a path on the map, which is all I need
					combinedResults.routes[0].legs = combinedResults.routes[0].legs.concat(result.routes[0].legs);
					combinedResults.routes[0].overview_path = combinedResults.routes[0].overview_path.concat(result.routes[0].overview_path);

					combinedResults.routes[0].bounds = combinedResults.routes[0].bounds.extend(result.routes[0].bounds.getNorthEast());
					combinedResults.routes[0].bounds = combinedResults.routes[0].bounds.extend(result.routes[0].bounds.getSouthWest());
					directionsResultsReturned++;
				}
				if (directionsResultsReturned == batches.length) // we've received all the results. put to map
					directionsDisplay.setDirections(combinedResults);
			}
		});
	}
}

When you make a route request on the directionsService object, Google returns with a DirectionsResult object that contains a DirectionsRoute object in it (see the API documentation at: http://code.google.com/apis/maps/documentation/javascript/reference.html#DirectionsResult).

This route object is fairly rich, and contains a copyright notice, the bounds of the route (to update the bounds of the map), the actual path of the route, and more. In my case, I only need to display the path, and have the bounds updated (to show the entire route, not just one batch), so I created a results object, put the first set of results into it, and then manually update the properties of the object as the subsequent responses come back.

I then use this combinedResults object to render the route.

One potential issue with this that I haven’t accounted for: what happens if / when the results come back in the wrong order? I think your route will get messed up. A better approach might be to stuff the results into another array (or dictionary) and then build the combined object once all the results are back (?).

Of course comments, improvements, etc welcome.

UPDATE 29/Feb/2012

I have updated my code, and modified it so that is should now return the final list of results in the correct order. Essentially I did as I suggested above: I store the results in an intermediary object with an index value and then, when I know I have them all, sort them into their correct order and build up a new object from that. This new object is the one I use to draw the route.

The modified calcRoute function is below.

calcRoute : function (batches, directionsService, directionsDisplay) {
	var combinedResults;
	var unsortedResults = [{}]; // to hold the counter and the results themselves as they come back, to later sort
	var directionsResultsReturned = 0;

	for (var k = 0; k < batches.length; k++) {
		var lastIndex = batches[k].length - 1;
		var start = batches[k][0].location;
		var end = batches[k][lastIndex].location;

		// trim first and last entry from array
		var waypts = [];
		waypts = batches[k];
		waypts.splice(0, 1);
		waypts.splice(waypts.length - 1, 1);

		var request = {
			origin : start,
			destination : end,
			waypoints : waypts,
			travelMode : window.google.maps.TravelMode.WALKING
		};
		(function (kk) {
			directionsService.route(request, function (result, status) {
				if (status == window.google.maps.DirectionsStatus.OK) {

					var unsortedResult = {
						order : kk,
						result : result
					};
					unsortedResults.push(unsortedResult);

					directionsResultsReturned++;

					if (directionsResultsReturned == batches.length) // we've received all the results. put to map
					{
						// sort the returned values into their correct order
						unsortedResults.sort(function (a, b) {
							return parseFloat(a.order) - parseFloat(b.order);
						});
						var count = 0;
						for (var key in unsortedResults) {
							if (unsortedResults[key].result != null) {
								if (unsortedResults.hasOwnProperty(key)) {
									if (count == 0) // first results. new up the combinedResults object
										combinedResults = unsortedResults[key].result;
									else {
										// only building up legs, overview_path, and bounds in my consolidated object. This is not a complete
										// directionResults object, but enough to draw a path on the map, which is all I need
										combinedResults.routes[0].legs = combinedResults.routes[0].legs.concat(unsortedResults[key].result.routes[0].legs);
										combinedResults.routes[0].overview_path = combinedResults.routes[0].overview_path.concat(unsortedResults[key].result.routes[0].overview_path);

										combinedResults.routes[0].bounds = combinedResults.routes[0].bounds.extend(unsortedResults[key].result.routes[0].bounds.getNorthEast());
										combinedResults.routes[0].bounds = combinedResults.routes[0].bounds.extend(unsortedResults[key].result.routes[0].bounds.getSouthWest());
									}
									count++;
								}
							}
						}
						directionsDisplay.setDirections(combinedResults);
					}
				}
			});
		})(k);
	}
}

UPDATE 25/Oct/2012

I put together a simple jsFiddle illustrating the code:
http://jsfiddle.net/ZyHnk/

UPDATE 29/Dec/2015

Levillain asked how he/she could display multiple routes. The short answer is to change the ‘stops’ object into a multidimensional array (a collection of stops arrays), and then loop through each set of stops and process the route. You must make sure and new up a new DirectionsRenderer for each request; if you reuse the same one, each query will wipe out the previous one.

I am unable to get the map bounds to update correctly. If anyone knows how to do this, I’m all ears.

Also, I threw this together very quickly, I’m sure it can be optimized / refactored.

Sample jsfiddle with multiple routes can be found here.

UPDATE 4/May/2016

Cesar Ulises Martinez Garcia in his comment below (May 3, 2016) has a workable solution to the 10 batch / OVER_QUERY_LIMIT problem. Essentially, when he hits an OVER_QUERY_LIMIT error, he pauses before sending another request. Thanks, Cesar!

 

Read Full Post »