algorithm - 从两个列表中匹配大量坐标

Question

我正在寻找一种更有效的算法来匹配两个列表之间的坐标。

给定两个具有纬度/经度值的列表。我的目标是为第一个列表中的每个坐标找到给定半径(例如 500 米)中另一个列表中的所有匹配坐标。

现在它只是被两个 for 循环强制执行，只是计算距离并检查每个坐标是否在我的半径范围内。但这让我想到了 O(n²) 的复杂性。

为了改善这一点，我的第一个想法是做一些类似于 Hashmap 的事情:通过在末尾切断一些小数，将第一个列表分类为更大的“字段”。一个例子是:

• lat: 44.7261 long: 8.2831 -> lat: 44.72 long: 8,28
• 纬度:43.8102 经度:9.7612 -> 纬度:43.81 经度:9.76
• lat: 44.7281 long: 8.2899 -> lat: 44.72 long: 8,28

因此创建了一些坐标“组”。现在我只需要在第二个列表上迭代一次并查看特定坐标位于哪个组中，然后对该组中的所有坐标进行计算。在视觉上，您可以描述在 map 中创建方 block 的想法，这些方 block 是我的哈希。然后首先查看当前坐标所在的散列，并将该散列中的所有坐标与当前坐标进行比较。

像这样我可以将复杂度从 O(n²) 降低到 O(n+m*(average_size_of_groups))如果坐标位于组的边界，我还需要检查该组的邻居。

但不知何故，我相信有一种更有效的方法来匹配这两个列表。我一直在寻找处理这类问题的算法，但我的谷歌搜索没有成功。

非常感谢:)

Answer 1

您的算法非常好，但您的组的最佳规模比您猜测的要小，这意味着您进行了太多比较。

您不应只去掉小数点后几位，而应将这些点分成与您的半径大小相同的正方形。

然后将每个点与它自己的组和 8 个相邻组的点进行比较。