我想将一个数组中的点与另一个数组中的点进行比较，找到最接近的一对 . 直到现在我遇到的只有一个阵列 . 我不想比较来自同一阵列的点 . 蛮力算法有效，但速度太慢 . 是否有使用分而治之方法的算法或实现？
编辑1：一个点被定义为地球表面上的一对（纬度，经度） .
您可以为第一个点阵列构建kd树，然后使用此树为第二个阵列的每个点找到第一个阵列中最近的点 . 它在av（n log n）上工作（n是两个数组中最大的一个的大小） . 要使用kd-tree，您可以将初始坐标转换为3D空间坐标 .
你可以使用kd-tree，octo tree，rtree，rtree * . 所有这些alghorithms O（log n）搜索最近的点 . 在boost库中有一个rtree的实现
2 回答
您可以为第一个点阵列构建kd树，然后使用此树为第二个阵列的每个点找到第一个阵列中最近的点 . 它在av（n log n）上工作（n是两个数组中最大的一个的大小） . 要使用kd-tree，您可以将初始坐标转换为3D空间坐标 .
你可以使用kd-tree，octo tree，rtree，rtree * . 所有这些alghorithms O（log n）搜索最近的点 . 在boost库中有一个rtree的实现