什么是最快的方式来找到哪些坐标在一定的范围内？

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英里点的数组。

我可能在公式中有一个错误（我更像是一个程序员而不是数学家）。因此，仔细检查他们是否与我添加了链接的维基百科文章一起工作。