In order to sort the results by distance from the route, it is essential to have basic functions for calculating distance. The challenge arises from the fact that the Earth is a sphere, making distances on a sphere more complex than those on a plane.
For shorter distances, such as from Tamiami to Miami, we can simplify by treating the distances as if they were on a plane to obtain reasonable results. To achieve this approximation, we need a method to determine the minimum distance between a point and a line segment. Rather than starting from scratch, I modified existing code from a Stack Overflow 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;
var t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
if (t < 0) return v;
if (t > 1) return w;
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)); }
Since we are currently only using distance for sorting purposes, we can save computation by utilizing the dist2 (squared distance) function instead of taking the square root.
The Google route query results contain an array named overview_path, which includes all the line segments used to create the route on the map. We can leverage these segments to find 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 );
}
It's important to note that the function I named indicates it calculates Cartesian distance, which may introduce inaccuracies for long routes or routes near the poles.
With this function in place, we can annotate each result with its distance for sorting, and then proceed with the sorting:
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 );
});
}
results.sort( function(a,b) { return a.coordDist2 - b.coordDist2; } );
For visualization during debugging, I included code to draw a 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 );
As an additional feature, I implemented the haversine formula for calculating geographic distance, allowing for the display of accurate geographic distance in the results list:
Number.prototype.toRad = function() {
return this * Math.PI / 180;
}
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;
}
It is worth noting that due to the calculation of distances on a plane, the order of results may not align with the true geographic distance computed using the haversine formula, particularly for long routes or those near the poles. Addressing this discrepancy would involve developing an algorithm for determining point/segment distance on a sphere, a task for future exploration.
For a demonstration of the complete solution in action, you can visit: http://jsfiddle.net/UqLTE/4/