c# - 两组中最接近的一对点，每组一个

Question

我有两组点，A 和 B，我试图找到最接近的一对点，从每组中取一个点。也就是说，如果您要使用两个绘制线的点，我想要允许我在两条线之间绘制最短线段的两个点。

环顾四周，几乎所有事情似乎都与寻找一组中的最近点有关。虽然我确实找到了一个推荐 voronoi 分割开始的解决方案，这似乎有点矫枉过正，但我​​只是在寻找比 O(n^2) 更好的东西。

如果有帮助的话，我比较的是两套表格线，尽管它们不一定是直的，而且我是用 C# 编写的。

谢谢。

Answer 1

通过一起处理所有点并用额外的位标记它们，应该可以调整经典的 D&C 算法(如维基百科链接中所述)。

合并步骤需要修改以接受候选左右对，每个集合中只有一个成员。这样，递归函数将返回最近的 A-B 对。应保留 O(N.Log(N)) 行为。

如果您提到的“线”有一个已知方程，以便可以快速评估点/线距离(甚至线/线交点)，则可能会有更快的解决方案。