给定一组点，我如何找到彼此最远的两个点？ [重复]

Question

  

可能重复：
  最大线性维度2d点

我可以计算每个点之间的距离并取最大值，但是当存在大（> 1000）个点数时，这听起来不是一种非常有效的方法。

注意：这适用于iPhone，因此我没有足够的处理能力。

Answer 1

您要求计算集合的直径。标准技术是首先计算凸包，这减少了找到凸多边形直径的问题。即使在您没有消除任何积分的情况下，这些添加的信息正是有效解决问题所需要的。然而，找到凸多边形的直径并非完全无关紧要;几篇发表的关于这项任务的算法的论文结果证明不正确。

这是相当可读的讨论任务的正确O（n）算法（其中n是凸包中的点数）。

另外，请注意iphone不 限制;即使是完全天真的算法，精心编写的实现也可以在不到十分之一秒的时间内处理1000个点。当然，使用正确的算法可以让你走得更快=）

Answer 2

为什么不计算这些积分的凸包？根据您使用的算法，它需要 O（n）或 O（n log n）时间并消除考虑的所有内部点。然后，只检查这些最外面的点，找到距离最远的两个点。

Answer 3

从具有最低x-coord的点开始。 （称之为X点） 构造“边界点”集合。    从点x开始，通过该点的垂直线，PointX左边应该没有其他点）通过顺时针（或逆时针）缓慢旋转线直到线接触其他点，找到边界中的下一个点，（见下文） ）。将该点添加到集合中并使用下一个点重复以获取下一个点，直到最终返回到原始点x。你npw有一组点形成整套的边界。比较此缩减集中每对之间的距离，以找到距离最远的对。

要“旋转线”， （为了找到每个连续的边界点），取“最远”的点。在垂直于最后边界点的线的方向上，并在最后一个边界点和“下一个”边界点之间构造一条新线。点。然后验证在新线形成的新的perpindicular方向上没有其他点。如果没有其他要点“更进一步”在对这条线或最后一条线的污秽处理中，这是下一个边界点的正确cjhoice，如果有这样一个点，切换到那个并重新测试。

Answer 4

请参阅这些页面（一页在计算一组点的凸包直径时，通过点击“下一步”链接链接到和可到达的页面。

我的简短摘要：

1. 计算凸包中的点集（= O（n log n），唯一得到O（n）的是你首先对列表进行排序，无论如何都需要O（n log n））
2. 沿着边界排序（如果你使用格雷厄姆扫描，你可以免费获得这个＃ 1）
3. 使用O（n）直径算法之一扫描具有最大直径的对映点。 Shamos算法对我来说很好，因为它是旋转卡尺算法。