如何根据缩短的距离对数组进行排序Javascript

我想对数组进行排序，使每个元素与前一个位置的距离最短。如何根据缩短的距离对数组进行排序Javascript

阵列是这样那样的

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

计算距离函数是这样的：

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; 
}

此功能时传递的值提供了两个位置之间的距离。

起点是位置数组现在我想要一个函数，将采取数组并返回排序的数组。

来源

2016-03-29 Neeraj Sharma

听起来像旅行商问题https://simple.wikipedia.org/wiki/Travelling_salesman_problem –

你的数组不是对象的一个有效的数组的数组。这不是一个有效的对象：'{“loc1”，lat，long}' – Adam

是的，但我无法在JavaScript中解决这个问题@ ManuAntony @Adam lat和long将是它的位置值只是例子它将如下所示： {“loc1”，“13.426785”，“44.475847”} –

你可以提供一个自定义函数来排序方法对数组原型，像这样：

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)

来源

2016-03-29 15:13:12

您需要执行排序函数内部的距离计算：

因为距离计算是一个相当密集，在一个对象缓存距离将使它更快这样你就不会计算相同的距离超过一次在你的分类方法中：

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

来源

2016-03-29 15:11:54 Adam

谢谢，但有什么办法让我把数组传递给排序函数，并返回给我排序的数组，因为我仍然通过JavaScript找到我的方式。 –

'locations.sort'对数组**进行排序**，这样在您调用locations.sort ....后，位置数组中的对象按照您想要的顺序排列。 – Adam

你可能会在这一块上掉下一个很大的兔子洞。我先看看这里是否可以使用Maps API Google Map V3, how to get list of best driving route for multiple destinations?。 optimizeWaypoints设置旨在返回最佳驾驶顺序中的位置列表。

显然这与纯距离比较不一样，但它可能适合您的需求。

来源

2016-03-29 15:12:40 jmcgriz

我试过这个，但是地图在南韩不能很好地运作，所以不能使用它。 –

嗯，这是不幸的 – jmcgriz

其实它是一个应用程序，我需要一个有序值的数组，以便我稍后根据数组在地图上绘制它。 –

没有真正的位置couln't测试，但类似下面应该做的工作：

（我不知道谷歌地图API，也许你可以找到更好的办法来做到这一点...）

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

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

 
\t return dist; 
 
} 
 

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

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

 

 
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>

来源

2016-03-29 15:22:30

如何根据缩短的距离对数组进行排序Javascript

回答

相关问题