什麼是最快的方式來找到哪些座標在一定的範圍內？

Question

比方說，我有一個100,000個座標的數據庫，我需要找到哪些距離某個座標不到1英里。 ？

什麼是最有效的方式做到這一點（在任何語言）

Answer 1

首先，我們必須寫一個基本功能，計算2點之間的距離：

function distance(lat1, lon1, lat2, lon2) {} 

在這個例子中首先，我們必須計算delta（經度和緯度之間的距離）和平均緯度（緯度的平均值）之間的距離（delta）：

var dLat = lat1 - lat2; 
var dLon = lon1 - lon2; 
var mLat = (lat1 + lat2)/2; 
var earthRadius = 3959; //in miles 

然後我們把那些弧度使用d=180/PI rad：

dLat = dLat * 180/3.1415926535; 
dLon = dLon * 180/3.1415926535; 
mLat = mLat * 180/3.1415926535; 

現在，我們用公式來我們的數據轉換成距離：

var distance = earthRadius * (dLat * dLat + Math.pow(Math.cos(mLat) * dLon, 2)); 

，並返回的距離

return distance; 

現在，只需遍歷所有的點和ch如果每個人的距離都沒有問題，那麼就去吃。比方說，一個點這樣描述：

var p = { 
    lat = ... 
    lon = ... 
} 

而且假定是一個點的列表（例如，名爲點）和參考點（例如，名爲REF）。

var result = [] 
points.forEach(function (d) { 
    if (distance(d.lat, d.lon, ref.lat, ref.lon) <= 1) { 
     result.push(d); 
    } 
}; 

您還可以檢查緯度邊界框 - 經度需要更復雜的計算，這只是浪費時間。你可以確定一英里的度數爲1/69 deg/mile（大約0.1449度）。所以，你可以檢查哪些點是這個邊界框之外：

var result = [] 
var maxLat = ref.lat + 0.1449; 
var minLat = ref.lat - 0.1449; 
points.forEach(function (d) { 
    if (d.lat > maxLat || d.lat < minLat) continue; 
    if (distance(d.lat, d.lon, ref.lat, ref.lon) <= 1) { 
     result.push(d); 
    } 
}; 

然後你應該完成與距離參考點越接近1英里點的數組。

我可能在公式中有一個錯誤（我更像是一個程序員而不是數學家）。因此，仔細檢查他們是否與我添加了鏈接的維基百科文章一起工作。