给定一组点，如何找到距离最远的两个点？

Question

可能是重复问题:
二维点集的最大线性尺寸

我可以计算每个点之间的距离，然后取最大值，但是当有大量（> 1000）的点时，这并不像一种非常有效的方法。

注意：这是为iPhone设计的，因此我没有太多的处理能力。

- willc2

Answer 1

为什么不直接计算点的凸包呢？根据您使用的算法，它需要O(n)或O(n log n)的时间，并消除了所有内部点的考虑。然后，只需检查这些最外层的点，找到最远的两个点即可。

- Chris Bunch

---

这并不会使事情变得更容易。如果凸包中的点数为O(n)，那么复杂度仍然保持不变。 - P Shved

非常正确。但希望的是，如果有>1000个点，则其中许多点将位于凸包内部。 - Chris Bunch

很棒的答案。我也是这么想的。在找凸包之前，先使用Akl-Toussaint启发式算法尽可能地排除多余的点。 - Nosredna

你已经将复杂度从O(n^2)降低了。在最坏的情况下，所有点都在凸包上，但在许多情况下，你会大幅减少实际工作量。 - PanCrit

@Pavel（和@Chris），期望的凸包点数是O(log n)，因此检查这些点的期望运行时间为O(log^2 n)。 - Jesse Beder

@Jesse（和@Pavel、@Chris）：如果凸包上有k个点，则可以使用“旋转卡尺”在O(k)时间内找到最远的一对点，而不需要k^2。请参见其他问题的答案，该问题询问相同的内容：https://dev59.com/u3RC5IYBdhLWcg3wW_tk - ShreevatsaR

Answer 2

您正在请求计算集合的直径。标准技术是首先计算凸包，这将问题简化为查找凸多边形的直径。即使在您不消除任何点的情况下，这个额外的信息也正是解决问题所需的。然而，查找凸多边形的直径并不完全是微不足道的；一些已发表的用于此任务的算法论文结果证明是不正确的。

以下是一个关于正确O(n)算法的相当易读的讨论（其中n是凸包中点的数量）。

另外，请注意iPhone并非如此有限制性；即使使用完全天真的算法的仔细编写实现也可以在不到十分之一秒的时间内处理1000个点。当然，使用正确的算法会让您更快 =)

- Stephen Canon

---

只有在找到凸包后，它才是O(n)的 - 如果你只是给定一组点，那么先找到凸包可能需要O(n log n)的时间。 - ShreevatsaR

@ShreevatsaR：当然。我的回答明确指出“其中n是凸包中点的数量”，这很清楚地表明您需要先找到凸包。 - Stephen Canon

是的，也许确实如此。清晰度在读者的眼中。 :-) （问题中的任务算法显然不是O（n），其中n是凸包中点的数量；正如您所说，它是第二部分。）无论如何，我认为值得提一下，只是为了完整起见：通过搜索引擎多年后可能会到达这些答案的人可能不会仔细阅读，会感到困惑等等。 - ShreevatsaR

PDF链接已失效，快速谷歌搜索失败了，有人有副本吗？ - Thomas

@Thomas：这个算法被称为“旋转卡尺”，ShreevatsaR在他对另一个问题的回答中给出了一个很好的非正式描述（https://dev59.com/u3RC5IYBdhLWcg3wW_tk#322409）。 - Stephen Canon

Answer 3

从x坐标最低的点开始（称其为点X），构建一组“边界点”，从点x开始，垂直于该点的线段上，没有其他点在PointX左侧。缓慢逆时针（或顺时针）旋转该线段，直到该线段接触到另一个点（见下文），将该点添加到集合中，并重复使用该下一个点获得下一个点，直到最终回到原点x。现在您拥有一组点形成完整集合的边界。比较减少集合中每对之间的距离，找出距离最远的一对。

要“旋转该线段”（以查找每个连续边界点），请沿着垂直于用于上一个边界点的线段的方向“最远”的点，并构建一条新的线段，在最后一个边界点和那个“下一个”点之间。然后验证在由该新线形成的新垂直方向或上一个线段的垂直方向中是否有更远的其他点。如果在与该线段或上一个线段垂直的方向上没有其他“更远”的点，则这是下一个边界点的正确选择。如果有这样一个点，请切换到该点并重新测试。

- Charles Bretana

---

和Chris一样的评论。如果在外部边界上没有更少的点，那么你不会使任何事情变得更容易。 - P Shved

这似乎是计算复合壳的一种昂贵方式，接下来是Chris Bunch的其他回答。 - PanCrit

我以前不知道这个有一个技术术语叫做凸包(convex hull)，其实就是一个橡皮筋边界。我会研究其他算法来计算它...关于点的数量，对于任何随机的点集，边界中的点数应该比总点数少O(n)。(边界是一个一维的线，用来限制一个二维区域。) - Charles Bretana

Answer 4

请参阅这些页面（链接到的页面和通过单击“下一页”链接可访问的页面），了解计算一组点的凸包直径。

我的快速摘要：

1. 计算凸包中的点集（= O(n log n)，唯一可以获得O(n)的时间是如果您首先对列表进行排序，这需要O(n log n)）
2. 沿边界排序（如果您使用Graham扫描进行＃1，则可以免费获得此功能）
3. 使用其中一个O(n)直径算法扫描具有最大直径的反极点。 Shamos算法 看起来很不错，因为它是旋转卡尺算法之一。

- Jason S