我目前正在致力于用 C++ 实现最接近的点对算法。也就是说，给定一个点列表 (x, y)，找到具有最小欧氏距离的点对。我对此进行了研究，我对算法的理解如下（如果我错了，请纠正我）：
将点数组从中间拆分
递归地找到左半部分和右半部分距离最小的点对。
按 y 坐标对左半部分和右半部分进行排序，并将左侧的每个点与右侧的 6 个最近邻点（按 y 坐标）进行比较。这背后有一些理论知识，但这是我对需要做什么的理解）。
我已经让算法的递归部分正常工作，但正在努力寻找一种有效的方法来为左侧的每个点找到右侧的 6 个最近的邻居。换句话说，给定两个已排序的数组，我需要为数组 A 中的每个点找到数组 B 中最接近的 6 个数字。我假设这里需要类似于合并排序的东西，但一直无法弄清楚。任何帮助将非常感激。
Let dist = min(dist_L, dist_R) where dist_L, dist_R分别是在左组和右组中找到的最小距离。
现在要找到一个点在左半部分而另一个点在右半部分的最小距离，您只需要考虑 x 坐标在区间内的点[x_m - dist, x_m+dist].
现在的想法是考虑这个区间内最接近的 6 个点。因此，按每个点的 y 坐标对点进行排序，展望下一个 6。这将导致O(nlog^2(n))运行时间。
您可以进一步改进这一点O(nlogn)通过加快分类过程。为此，让每个递归调用还返回点的排序列表。然后要对整个列表进行排序，您只需合并两个已排序的列表即可。细心的读者会注意到，这正是合并排序。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
