algorithm - 从另一个点有效地找到最近的点

Question

我有一个包含约 10.000 个点的坐标列表 A(纬度、十进制形式的经度)和另一个包含约 100 万个点的相同类型的坐标列表 B。

我想为列表 B 中的每个元素找到列表 A 中最近的点。

我已经完成的是创建两个列表的笛卡尔积，并使用半正弦公式找到所有组合的距离。

然后我得到列表 A 中的点，这些点与列表 B 中的每个点具有最小距离。

由于总组合超过100亿，计算距离的时间太长。

有没有办法确保列表 B 中的每个点都与列表 A 中的一个点匹配，同时还能提高性能？

Answer 1

如果您已经创建了叉积并计算出所有的半正弦距离，那么您已经完成了大部分工作，所以我假设问题是关于如果您有新的集合 A 和 B 该怎么办。

为了反复找到 A 中的最近点，我会构建某种包含 A 中的点的树结构，并在树的每个节点存储信息，这相当于一个边界框或包含其所有后代的等效项。然后当试图找到 A 中最近的点时，你递归地搜索包含 A 的树，当你到达一个节点时从递归调用返回并且你可以从存储在那里的信息计算出它的所有后代都离目标点更远比目前最接近的匹配。

要使这段代码起作用，边界框信息需要准确，但如果树是愚蠢的，它会减慢搜索速度，但不会阻止他们找到正确答案。这尤其意味着，当您构建树时，您可以安全地忽略经度在 180W = 180E 处环绕的不便习惯。你可以假装经纬度是一个矩形网格并构建一个 k-d 树，你可以将纬度和经度组合起来并对其进行位交错并在结果上构建一个一维搜索树，你可以计算 https://en.wikipedia.org/wiki/Geohash并以此为基础构建一个搜索树，或者你可以计算大量的 haversines 并构建一个 https://en.wikipedia.org/wiki/Cover_tree - 所有这些都应该有效，我不知道哪个最好 - 这可能取决于您的数据和可用的库。