javascript - 查找特定周长内的坐标的最快方法是什么？

Question

假设我有一个包含 100,000 个坐标的数据库， 我需要找到哪些距离某个坐标不到 1 英里。

最有效的方法是什么？(任何语言)

Answer 1

首先，我们必须编写一个基本函数来计算两点之间的距离:

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

对于此示例，我将根据球形地球投影到平面 ( here ) 的公式来计算该函数 首先，我们必须计算增量(经纬度之间的距离)和平均纬度(纬度的平均值):

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;

现在，只需迭代所有点并检查每个点的距离是否合适。假设这样描述一个点:

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 度/英里(大约 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 英里的一系列点结束。

我可能在公式方面有错误(我更像是程序员而不是数学家)。因此，请仔细检查它们是否适用于我添加了链接的维基百科文章。