1

I am using the Google Maps API in my application (ASP.NET with MVC).

I have an array of coordinates (each consisting of latitude and longitude), let us call it "origin" (this can be a polygon, polyline or marker) and another array of coordinates, let us call that "destination" (can be a polygon, polyline or marker either).

I want to calculate the shortest distance between "origin" and "destination". How can I do that?

Qantas 94 Heavy
  • 15,750
  • 31
  • 68
  • 83
user1799982
  • 102
  • 1
  • 11

4 Answers4

2

Well, looking from it at a mathematical standpoint:

your problem is to find the shortest distance between a point in space and a vektor line or plane.

So if you have your coords in arrays like [a1,a2,a3] and [b1,b2,b3] the distance between this 2 points in 3 dimensional space is like the Pythagorean theorem with three elements: sqrt[(a1-b1)²+(a2-b2)²+(a3-b3)²]=d(a,b).

I know this does not take the curvature of the earth into account but for "short" distances this is is not important.

If you understand some math the wikipedia article might help you as well. http://en.wikipedia.org/wiki/Euclidean_distance#Three_dimensions

Edit 12.08.14:
To take the curvature of the earth into account, you can do a simple calculation:
(1) You already know the distance of the earth
(2) you know the approx. radius of the earth

With your start point(A) and your destination(B) known, you now build a triangle with the center of the earth(C). You do this to now calculate the angle at (C) (sin/cos/tan). With that angle you can now get the length of the earth (including the curvature).

([boundary of earth]/360°)*[angle at (C)] = the dinstance from (A) to (B) over the curvature of the earth.

Nils
  • 111
  • 1
  • 6
1

One solution would be to take one of the options found here and calculate the distance from each point in the origin to each point in the destination. The smallest distance would be the distance between your two shapes.

Code might look like this (untested):

var minDistance = Number.POSITIVE_INFINITY;
for (var i=0; i<origin.length; i++){
   for (var j=0; j<destination.length; j++){
      var dist = google.maps.geometry.spherical.computeDistanceBetween(origin[i], destination[j]);
      if (dist < minDistance) 
         minDistance = dist;
   }
}

This could likely be optimized if performance is an issue. For more information on that, I would look at this question and its answers which deal with the same issue, although from a purely mathematical perspective.

Community
  • 1
  • 1
Kade Keith
  • 208
  • 1
  • 11
1

I recommend that you use the Spherical Law of Cosines to calculate the distance between the points. If you have an array of latitude and longitude for the origins, and an array of latitude and longitude coordinates for destinations, then you can do something like this:

var origins = [{lat: "35.5", lon: "-80.0"}, ...]; // Array of origin coordinates
var destinations = [{lat: "34.5", lon: "-80.0"}, ...]; // Array of destination coordinates
var shortestDistance = null;
var shortestPair = [];

for (i = 0; i < origins.length; i++) {
    for (j = 0; j < destinations.length; j++) {

        var lat1 = origins[i].lat.toRadians();
        var lat2 = destinations[j].lat.toRadians();
        var lon = (destinations[j].lon - origins[i].lon).toRadians();
        var R = 6371; // gives distance in kilometers
        var calcDistance = Math.acos(Math.sin(lat1) * Math.sin(lat2) + Math.cos(lat1) * Math.cos(lat2) * Math.cos(lon)) * R;

        if (shortestDistance === null || calcDistance < shortestDistance) {
            shortestPair[0] = origins[i]; // Store the origin coordinates
            shortestPair[1] = destinations[j]; // Store the destination coordinates
            shortestDistance = calcDistance; // Update the shortest distance
        }
    }
}

/* After this runs, you'll have the array indexes for the origin and 
destination with the shortest distance as well as the actual distance (kilometers) 
in the array shortestPair and the variable shortestDistance respectively.

For miles, divide shortestDistance by 1.609344
For nautical miles, divide shortestDistance by 1.852

*/

This seems to be a simpler approach than attempting to use the Maps API for the distance calculations. The above formula was sourced from http://www.movable-type.co.uk/scripts/latlong.html. You could also use the haversine formula if you need the calculations to be more accurate; it's detailed on the page that I linked.

aecend
  • 2,432
  • 14
  • 16
  • There is a logical mistake in your solution. Take a look at [this graphical demonstration of the problem](http://i.stack.imgur.com/hzJdY.png) – Matteo B. Aug 05 '14 at 21:38
  • @Matmarbon: Yes, my solution implemented as-is won't address that situation, but by comparing each of the vertices of the polygons, my solution could still be effective. To go any further than that would require calculating closeness to points along each segment in each polygon, which is a computationally heavy NP-Complete problem. – aecend Aug 05 '14 at 22:34
  • So, long story short: "Forget about it, it's too complex"? Look, to be precise, the question does not say anything about performance but needs a solution to this problem. Anyway, I appreciate your help so far :) – Matteo B. Aug 07 '14 at 19:09
0
function moveAlongPath(points, distance, index) {  
  index = index || 0;  

  if (index < points.length && typeof points[index +1] !="undefined") {
    var polyline = new google.maps.Polyline({
      path: [points[index], points[index + 1]],
      geodesic: true,
      strokeColor: '#FF0000',
      strokeOpacity: 1.0,
      strokeWeight: 2
    });

    var distanceToNextPoint = polyline.Distance();
    if (distance <= distanceToNextPoint) {
      return polyline_des(points[index],points[index + 1], distance);
    }
    else {
      return moveAlongPath(points,
            distance - distanceToNextPoint,
            index + 1);
    }
  }
  else {
    return null;
  }  
}
manlio
  • 18,345
  • 14
  • 76
  • 126