来自两组的最接近的一对点，每组一个

我有两组点，A和B，并且我试图找到最接近的一对点，其中从每组取一点。也就是说，如果你要使用两点画线，我想要两点让我画两条线之间的最短线段。来自两组的最接近的一对点，每组一个

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

如果有帮助，这两套我比较表格行，虽然他们不一定是直的，我正在用C＃写这篇文章。

谢谢。

2014-01-21 djcmm476

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem –

但是，这只适用于一组要点... – djcmm476

想想你的句子_“哪里有一点从每个集合中拿走”_所以我们得到什么？一套新的C（A1，B1）或我想念你吗？ – WiiMaxx

应该可以通过处理所有的点并用额外的位标记它们来适应经典的D算法（如维基百科链接中所述）。

合并步骤需要修改，以便仅与每组中的成员接受候选左右对。这样，递归函数将返回最接近的A-B对。 O（N.Log（N））行为应该保留。

如果你提到的“线条”有一个已知方程，以便可以快速评估点/线距离（甚至线/线交点），那么可能会有更快的解决方案。

2014-01-21 11:50:37

这很有道理。我不太清楚如何在C＃中标记它们，但不添加一些预算法工作，你有什么建议吗？ – djcmm476

对不起，我看不到你的观点。你可以在你的点结构中添加一个布尔变量，或者维护一个单独的布尔列表，并与点列表相对应。不涉及处理。 –

您能否详细说明如何在N log N中执行此操作？如果A的所有点紧密聚集在（0,0）附近，并且B的所有点紧密聚集在（100,100）附近，我不知道该怎么办：我认为如果是这种情况，那么“划分”将最终将来自集合A的所有点集合在一起，并集合在一起，因此合并不会很快。 – Irvan

回答