4

我想将一个数组中的点与另一个数组中的点进行比较，并找到最接近的对。到目前为止，我遇到的只是一个数组。我不想比较来自同一个数组的点。蛮力算法有效，但速度太慢。是否有使用分治法的算法或实现？

编辑 1：一个点被定义为地球表面上的一对（纬度，经度）。

4

2 回答 2

4

您可以为第一个点数组构建一个 kd 树，然后使用此树为第二个数组的每个点从第一个数组中找到最近的点。它在平均 O(n log n) 上工作（n 是两个数组中最大的数组的大小）。要使用 kd-tree，您可以将初始坐标转换为 3D 空间坐标。

于 2014-08-01T15:28:24.013 回答
1

您可以使用 kd-tree、octo tree、rtree、rtree*。所有这些算法 O(log n) 来搜索最近点。在 boost 库中有一个 rtree 的实现

于 2014-08-01T18:27:14.043 回答