java - 用于比较来自 2 个不同数组的点的最近对算法

Question

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

编辑 1:点定义为地球表面上的一对(纬度、经度)。

Answer 1

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