I'm searching for places located within a boundary on a route. I want to return results in order of distance from the route.
I tried rankby=distance in my Nearby Search request but it doesn't work because it requires a location and radius whereas I have a LatLngBounds object and a route. Is this even possible?
This is my script returning places along a route within a boundary.
It returns results but in random order...
Note: The goal is to use bounds not location.
Before we even consider ordering the results by distance from route, we have to have some basic functions to calculate distance. We immediately run into a snag here, because of course the earth is a sphere, and distances on a sphere are more complicated than distances on a plane.
However, over relatively small distances (Tamiami to Miami, for example), we can treat distances as if they were on a plane, and achieve reasonable results. If we can live with that approximation, we simply need a method for determining the minimum distance between a point and a line segment. Instead of re-inventing the wheel, I adapted some code from this SO answer:
function sqr(x) { return x * x }
function dist2(v, w) { return sqr(v.x - w.x) + sqr(v.y - w.y) }
function distToSegment2(p, v, w) {
return dist2(getClosestPoint(p,v,w));
}
function getClosestPoint( p, v, w ) {
var l2 = dist2(v, w);
if (l2 === 0) return v; // line is actually a point; just return one ofthe two points
var t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
// point is closest to v, return v
if (t < 0) return v;
// point is closest to w, return w
if (t > 1) return w;
// point is closets to some midpoint, return that
return { x: v.x + t * (w.x - v.x), y: v.y + t * (w.y - v.y) };
}
function distToSegment(p, v, w) { return Math.sqrt(distToSegmentSquared(p, v, w)); }
Now since all we're using the distance for (currently) is sorting, we don't have to take the extra step of taking the square root, so we can simply use the dist2 (distance squared) function to save us a little extra computation.
The results from a Google route query contain an array called overview_path which contains all of the line segments used to actually draw the path on the map. We'll use these segments to determine the closest point:
function closestPointOnPath_Cartesian( place, path, cb ) {
var min = Number.MAX_VALUE;
var closestPoint = null;
for( var i=0; i<path.length-1; i++ ) {
var v = { x: path[i].lng(), y: path[i].lat() };
var w = { x: path[i+1].lng(), y: path[i+1].lat() };
var p1 = { x: place.geometry.location.lng(),
y: place.geometry.location.lat() };
var p2 = getClosestPoint( p1, v, w );
var d2 = dist2( p1, p2 );
if( d2 < min ) {
min = d2;
closestPoint = new google.maps.LatLng( p2.y, p2.x );
}
}
cb( closestPoint, min );
}
Note that I was careful to name this function to indicate that this calculates Cartesian distance, which could cause problems with long routes, or routes close to the poles.
Now that we have this function, all we have to do is annotate each result with the distance so we can sort it, and then actually perform the sort:
for( var i=0; i<results.length; i++ ) {
closestPointOnPath_Cartesian( results[i],
result.routes[0].overview_path,
function( closestPoint, coordDist2 ){
results[i].closestPointOnPath = closestPoint;
results[i].coordDist2 = coordDist2;
results[i].geoDistKm = geoDistanceKm( results[i].geometry.location, closestPoint );
});
}
// sort results by relative distance (coordDist2)
results.sort( function(a,b) { return a.coordDist2 - b.coordDist2; } );
For debugging visualization purposes, I added some code to draw the line from the closest point on the path to each location:
var distLine = new google.maps.Polyline({
path: [place.closestPointOnPath, place.geometry.location],
strokeColor: '#ff0000',
strokeOpacity: 1.0,
strokeWeight: 2
});
distLine.setMap( map );
Lastly, for extra credit, I used the haversine formula (adapted from this SO answer)
Number.prototype.toRad = function() {
return this * Math.PI / 180;
}
// geographic distance courtesy the haversine formula
function geoDistanceKm(p1,p2) {
var R = 6371; // km
var x1 = p2.lat()-p1.lat();
var dLat = x1.toRad();
var x2 = p2.lng()-p1.lng();
var dLon = x2.toRad();
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(p1.lat().toRad()) * Math.cos(p2.lat().toRad()) *
Math.sin(dLon/2) * Math.sin(dLon/2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
return R * c;
}
So now we can actually display true geographic distance in the results list.
Note: because we're computing distance on the plane, for long routes, or routes near the pole, it is entirely possible that the order will NOT match the (correct) order based on the geographic distance as determined by the haversine formula. To fix this would require deriving an algorithm to determine point/segment distance on a sphere, which is a task for another day.
You can see the complete solution working here: http://jsfiddle.net/UqLTE/4/
If you are using the Place Search Request method you can use the bounds parameter instead of location and radius.
Otherwise you could use the Google Maps API method using the centre of your box as the centre of the circle and half of the diagonal of the box as the radius of the circle. This will give you all of the places within the circle enclosing the box. You can then scan through the set removing any places that are inside the circle but outside of the box.
Adding rankby=distance to the method call would sort the results in order of distance from the specified location (e.g. the centre of the box.) If you need to sort in order of distance from the route you would need to calculate the distance from the route. The simplest way to do this is to calculate a perpendicular to each line segment in the route using vector projection. If the projected point is off one end of the line segment, the distance is to the end point of that end of the line. The sign of the distance along the vector will tell you which end to test. The distance to the closest line segment is the shortest distance to the route.
The closest method in the Google Maps API V3 is: DistanceMatrixService which finds the distance between multiple source and destination locations. There are a few other methods that might help with parts of the calculation, but I can't see anything that finds the distance between a route/polyline and a place/point.
Here's an idea. you have to get each distance of each place from the route starting point and add the value as an attribute of the list, then sort the list according to the value of the attribute.
Here's an example of how to sort list according to it's attribute value.
HTML
<ul id="place-list">
<li data-id="4">Tokyo 4</li>
<li data-id="0">Paris 0</li>
<li data-id="5">Frankfurt 5</li>
<li data-id="2">London 2</li>
<li data-id="1">greece 1</li>
<li data-id="3">Munich 3</li>
</ul>
<button id="asc">ASC</button>
<button id="desc">DESC</button>
jQuery
var sortArray = function (items, inverse) {
var inverse = inverse || false;
var sortedArray = items.map(function () {
return {
id: $(this).data("id"),
element: $(this)[0].outerHTML
};
});
var appendTo = items.parent();
items.remove();
sortedArray.sort(function (a, b) {
return a.id > b.id ? (inverse ? -1 : 1) : (inverse ? 1 : -1);
});
sortedArray.each(function () {
$(appendTo).append(this.element);
});
}
$("#asc").click(function () {
sortArray($("#place-list").find("li"));
});
$("#desc").click(function () {
sortArray($("#place-list").find("li"), true);
});
EXAMPLE: http://jsfiddle.net/995dY/
