r - 找到最近的地理位置最有效的方法是什么？

Question

我有两个数据框，其中观察是由纬度/经度组合定义的地理位置。对于每个点，df1我想获得最近的点df2和相关的值。我知道如何通过计算所有可能的距离（例如使用包中的gdist函数Imap）并获取最小距离的索引来做到这一点。但事实是，它最多df1只有 1,000 行和df2大约 1500 万行。

你知道我如何在不计算所有距离的情况下达到我的目标吗？也许有一种方法可以限制必要的计算（例如使用纬度/经度值的差异）？

感谢您的帮助，

瓦尔

如下df1所示：

   Latitude Longitude
1  56.76342  8.320824
2  54.93165  9.115982
3  55.80685  9.102455
4  57.27000  9.760000
5  56.76342  8.320824
6  56.89333  9.684435
7  56.62804  8.571573
8  56.64850  8.501947
9  55.40596  8.884374
10 54.89786 11.880828

然后df2：

   Latitude Longitude       Value
1  41.91000 -4.780000       40500
2  41.61063 14.750832       13500
3  41.91000 -4.780000        4500
4  38.70000 -2.350000       28500
5  52.55172  0.088622        1500
6  39.06000 -1.830000       51000
7  41.91000 -4.780000       49500
8  48.00623 -4.389639       12000
9  56.24889 -3.666940       27000
10 42.72000 -3.750000       49500

标签： rgis

Answer 1

将第二帧分成大小相等的块

然后只搜索你的点合理距离内的块。您将基本上在地图上绘制棋盘格。您的点将在这些方格之一内 - 因此您将只搜索那个和少数几个相邻的方格以确保安全。

天真的蛮力搜索是行（df1）*行（df2）。在我们的例子中是 1000 * 15M，使得 15G 操作乘以每个操作的计算时间。

那么我们如何将数据拆分成块呢？

1. 按纬度排序
2. 按经度排序
3. 取等距的块

排序将进行一些 Nlog(N) 操作。在我们的例子中，N 是 15M，所以这两种类型需要 ~24 15M 2 次操作。分割成块然后是线性的~15M 操作，可能是几次。
当你完成这种分离后，在每个块中你都total_points/(chunk_side ^ 2)有点，假设你的点是均匀分布的。块的数量与开始时块的大小成正比： total_area/(chunk_side ^ 2).

理想情况下，您希望平衡块数和每个块中的点数，以便两者都是 ~ sqrt(points_total)。

现在，每千次搜索只需要chunk_count + points_in_chunk* 9 （如果我们想要超级安全并搜索我们的点所在的块和所有周围的块。）所以现在不是 1000 * 15M 你现在有 `1000 * (sqrt(15M ) *18) ~ 1000 * 16K，提高了 50 倍。

请注意，如果第二组变得更大，这种改进将会增加。如果你选择的块大小不好，改进也会更小。
为了进一步改进，您可以再迭代一次或两次，将块分成块。逻辑类似。