如何有效計算JavaScript中最近的2D點？

Question

我有一組位置，我想根據它們當前的座標以接近順序（最接近最遠）顯示給用戶。假設我們有大約100個包含每個經緯度（在某種對象或數組中）的位置的數據點，並且我們知道用戶的lat和long。我們的目標是顯示一個有序的位置列表 - 如果我們可以在計算出最接近的8-10個位置並向用戶顯示時顯示剩餘的距離，這將是有益的。

我知道蠻力解決方案是循環遍歷所有位置，計算與用戶的距離，將它們按順序排列，然後將它們全部顯示給用戶。但是這太慢了。

更好的解決辦法是這樣的一個：https://stackoverflow.com/a/2466908/1766230，你有界框內首先檢查，擴大如有必要，然後做休息。

我也看到有其他算法 - 例如FLANN和other methods - 但我還沒有看到任何用JavaScript編寫的例子。

所以問題：什麼是最快的方式來計算（並按順序顯示）JavaScript中的最近點？

Answer 1

所以，如果你開始接觸點的該列表，畫一個小的邊界框不會減少很多，因爲你還是做一個O（n）的核對他們的位置的所有點。

我會建議使用最大長度堆或其他形式的部分排序，同時遍歷所有點。這使您可以跟蹤大約最大/最小點的一小部分（如長度所述），因此您可以在處理其餘部分之前快速渲染它們。如果你需要更多關於我正在說的話的解釋，請告訴我。

此外，你有什麼這樣做，有這樣嚴格的性能問題？通常，這樣的計算不應該是一個壓力點，除非你有100K +點。 DOM操作通常是最昂貴的現貨

var points = []; 
for (i = 0; i < 100; i++) { 
    var point = [getRandomInt(0, 999), getRandomInt(0, 999)]; 
    point.len = distanceBetweenPoints(point, [499,499]); 
    points.push(point); 
} 

console.log(Heap.nsmallest(points, 10, function (a, b) { 
    return a.len < b.len; 
})); 

Here is the performance for it compared to bruteforce

Heap Code

js fiddle

使用我所描述的方法，以及預建堆另外一個人寫的，我比較我們的方法。我想你會很開心！它在強力技術中執行了8,586次操作/秒，而566次操作！

Answer 2

嗯，這是我的距離排序點的數組給定點的嘗試。據我所知，這是蠻力。然後我給這個數組給你10個最近的點。

的Javascript

function distanceBetweenPoints(p1, p2) { 
    return Math.abs(Math.sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]))); 
} 

function sortByDistance(location, arrayOfPoints) { 
    arrayOfPoints.sort(function (a, b) { 
     a.distance = distanceBetweenPoints(location, a); 
     b.distance = distanceBetweenPoints(location, b); 

     return a.distance - b.distance; 
    }); 

    return arrayOfPoints; 
} 

function getRandomInt(min, max) { 
    return Math.floor(Math.random() * (max - min + 1)) + min; 
} 

var points = []; 

for (i = 0; i < 100; i += 1) { 
    points.push([getRandomInt(-90, 90), getRandomInt(-180, 180)]); 
} 

console.log(sortByDistance([0, 0], points).slice(0, 10)); 

在jsFiddle

這將至少給你的東西來測試算法反對。以上是jsPerf，因此您可以添加其他例程並進行一些真正的性能比較。

注意：這並沒有考慮到地球是一個球體！這是計算Euclidean distance而不是測地距離。如果這些點例如位於同一個城鎮（或者很接近），但是如果它們位於不同的國家/大陸，則沒有問題。它還假定您已將經度和緯度轉換爲十進制表示。

否則，你就需要看的東西像Great-circle distance和Haversine formula

事實上，地球是非常輕微的橢圓形;使用球形模型給出了錯誤通常高達0.3％

的Javascript

function toRadians(degrees) { 
    return (degrees * Math.PI)/180; 
} 

// Haversine formula 
function distanceBetweenPoints(p1, p2) { 
    var R = 6371, // mean earth radius in km 
     lat1 = toRadians(p1[0]), 
     lon1 = toRadians(p1[1]), 
     lat2 = toRadians(p2[0]), 
     lon2 = toRadians(p2[1]), 
     dLat = lat2 - lat1, 
     dLon = lon2 - lon1, 
     a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2), 
     c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)), 
     d = R * c; 

    return d; 
} 

function sortByDistance(location, arrayOfPoints) { 
    arrayOfPoints.sort(function (a, b) { 
     a.distance = distanceBetweenPoints(location, a); 
     b.distance = distanceBetweenPoints(location, b); 

     return a.distance - b.distance; 
    }); 

    return arrayOfPoints; 
} 

function getRandomInt(min, max) { 
    return Math.floor(Math.random() * (max - min + 1)) + min; 
} 

var points = []; 

for (i = 0; i < 100; i += 1) { 
    points.push([getRandomInt(-90, 90), getRandomInt(-180, 180)]); 
} 

console.log(sortByDistance([0, 0], points).slice(0, 10)); 

在jsFiddle