How to sort an array according to shorted distance Javascript

Question

I want to sort an array such that each element is in the shortest distance from previous location.

array is such like that

locations=[{"loc1",lat,long},{"loc2",lat,long},{"loc3",lat,long},{"loc4",lat,long},{"loc5",lat,long}]

the function to calculate the distance is this:

var distance = function(lat1, lon1, lat2, lon2)
{
  var radlat1 = Math.PI * lat1/180;
  var radlat2 = Math.PI * lat2/180;
  var theta = lon1-lon2;
  var radtheta = Math.PI * theta/180;
  var dist = Math.sin(radlat1) * Math.sin(radlat2) + Math.cos(radlat1) * Math.cos(radlat2) * Math.cos(radtheta);
  dist = Math.acos(dist);
  dist = dist * 180/Math.PI;
  dist = dist * 60 * 1.1515;
  dist = dist * 1.609344 ;

  return dist;
}

This function when passed the value provide the distance between two location.

The starting point is the first element of locations array now i want a function that will take array and return the sorted array.

Sounds like a Travelling salesman problem https://simple.wikipedia.org/wiki/Travelling_salesman_problem — John, Mar 29 '16 at 15:06
Your array isn't a valid array array of objects. This isn't a valid object: `{"loc1",lat,long}` — Adam Jenkins, Mar 29 '16 at 15:07
Yes it is but i am unable to solve this in JavaScript.@ManuAntony @Adam lat and long will be the values of the locations its just example it will be like: {"loc1","13.426785","44.475847"} — Neeraj Sharma, Mar 29 '16 at 15:10
The JS object should look like `{ "name": "Loc1", "lat": 1231231, "lon": 234235232 }` — Dean Meehan, Mar 29 '16 at 15:12
@NeerajSharma - paste `{"loc1","13.426785","44.475847"}` into your console and you'll see an error - it's not a valid JS object. — Adam Jenkins, Mar 29 '16 at 15:12
ok i understand @Adam although i do have valid json in my array. — Neeraj Sharma, Mar 29 '16 at 15:31
Why are you using trigonometric functions to calculate distance? Surely you can do it with basic squares and square root operations? Or does that come out more performance intensive somehow? `distance = Math.sqrt(Math.pow(latitudeDifference, 2) + Math.pow(longitudeDifference, 2));` — ManoDestra, Mar 29 '16 at 16:15

score 1 · Accepted Answer · answered Mar 29 '16 at 15:13

You can provide a custom function to the sort method on the Array prototype, like this:

locations = [
  ["loc1", 1, 1],
  ["loc2", 3, 3],
  ["loc3", 2, 2],
  ["loc4", 5, 4],
  ["loc5", 3, 5]
];

var distance = function(lat1, lon1, lat2, lon2) {
  var radlat1 = Math.PI * lat1 / 180;
  var radlat2 = Math.PI * lat2 / 180;
  var theta = lon1 - lon2;
  var radtheta = Math.PI * theta / 180;
  var dist = Math.sin(radlat1) * Math.sin(radlat2) + Math.cos(radlat1) * Math.cos(radlat2) * Math.cos(radtheta);
  dist = Math.acos(dist);
  dist = dist * 180 / Math.PI;
  dist = dist * 60 * 1.1515;
  dist = dist * 1.609344;

  return dist;
};

locations.sort(function(a, b) {
  var origLat = 0,
    origLong = 0;

  return distance(origLat, origLong, a[1], a[2]) - distance(origLat, origLong, b[1], b[2]);
});

console.log(locations)

Rogerio Soares · Answer 2 · 2016-03-29T15:45:46.910

Without real locations couln't test but something like below should do the job :

(I dont know Google Map API, maybe you can find a better way to do this...)

var locations = [{
  name : "loc1",
  lat : 1001,
  long : 2001
 }, {
  name : "loc2",
  lat : 150,
  long : 630
 }, {
  name : "loc3",
  lat : 151,
  long : 631
 }, {
  name : "loc4",
  lat : 850,
  long : 56
 }, {
  name : "loc5",
  lat : 960,
  long : 698
 }
];

var distance = function (lat1, lon1, lat2, lon2) {
 var radlat1 = Math.PI * lat1 / 180;
 var radlat2 = Math.PI * lat2 / 180;
 var theta = lon1 - lon2;
 var radtheta = Math.PI * theta / 180;
 var dist = Math.sin(radlat1) * Math.sin(radlat2) + Math.cos(radlat1) * Math.cos(radlat2) * Math.cos(radtheta);
 dist = Math.acos(dist);
 dist = dist * 180 / Math.PI;
 dist = dist * 60 * 1.1515;
 dist = dist * 1.609344;

 return dist;
}

var locationWithDistFromPrevious = locations.map(function (l, i) {
  if (i === 0) {
   l.dist = 0;
  } else {
   l.dist = distance(l.lat, l.long, locations[i - 1].lat, locations[i - 1].long)
  }
  return l;
 }).sort(function (a, b) {
  return a.dist - b.dist
 });

var locationWithDistFromFirst = locations.map(function (l, i) {
  if (i === 0) {
   l.dist = 0;
  } else {          
   l.dist = distance(l.lat, l.long, locations[0].lat, locations[0].long)
  }
  return l;
 }).sort(function (a, b) {
  return a.dist - b.dist
 });


document.getElementById("resultFromPrev").textContent = JSON.stringify(locationWithDistFromPrevious, null, 4);
document.getElementById("resultFromFirst").textContent = JSON.stringify(locationWithDistFromFirst, null, 4);

<body>
  Sort by previous item<br/>
  <pre id="resultFromPrev"></pre><br/>
  Sort by first item dist <br/>
  <pre id="resultFromFirst"></pre><br/>
</body>

Adam Jenkins · Answer 3 · 2016-03-29T15:21:13.840

You need to perform the distance calculation inside a sort function:

Because the distance calculation is a pretty intensive, caching distances in an object will make it much faster so you're not calculating the same distance more than once in your sort method:

var startingLoc = {lat:0.000,lng:0.000};//your starting location;
var distanceCache = {}; //a cache to hold your distance calculations

//sort the locations - assumes loc1 is {lat:some number, lng: some number}
locations.sort(function(loc1,loc2) {
    var loc1Key = loc1.lat+'-'+loc1.lng;
    var loc2Key = loc2.lat+'-'+loc2.lng;

    if(!distanceCache.hasOwnProperty(loc1Key)) {
      distanceCache[loc1Key] = distance(startingLoc.lat,startingLoc.lng,loc1.lat,loc1.lng);
    }

    if(!distanceCache.hasOwnProperty(loc2Key)) {
      distanceCache[loc2Key] = distance(startingLoc.lat,startingLoc.lng,loc2.lat,loc2.lng);
    }

    return distanceCache[loc1Key] - distanceCache[loc2Key];

 });

distanceCache = null; //done with distanceCache

thanks but is there any way such that i pass an array to the sort function and it return me the sorted array as i am still finding my way through JavaScript. — Neeraj Sharma, Mar 29 '16 at 15:22
`locations.sort` sorts the array **in place** such that after you call `locations.sort....`, the objects in the `locations` array are in the order you want. — Adam Jenkins, Mar 29 '16 at 15:26

score 0 · Answer 4 · edited May 23 '17 at 11:59

0

You're probably headed down a pretty big rabbit hole on this one. I'd look here first to see if you can use the Maps API Google Map V3, how to get list of best driving route for multiple destinations?. The optimizeWaypoints setting is meant to return a list of locations in optimal driving order.

Obviously this isn't the same as a pure distance comparison, but it may be suitable for your needs.

edited May 23 '17 at 11:59

Community

1
1

answered Mar 29 '16 at 15:12

jmcgriz

2,819
1
9
11

i tried this but the map do not work well in south korea so cant use it. – Neeraj Sharma Mar 29 '16 at 15:15
Ah, that's unfortunate – jmcgriz Mar 29 '16 at 15:16
actually it for an app i need an array of sorted value so that i will later plot it on map according to the array. – Neeraj Sharma Mar 29 '16 at 15:17

How to sort an array according to shorted distance Javascript

4 Answers4

Linked