c - 给定一组点，我如何找到彼此最远的两个点？

Question

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

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

注意：这是针对 iPhone 的，所以我没有大量的处理能力。

Answer 1

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

Answer 2

您要求计算集合的直径。标准技术是首先计算凸包，这将问题简化为找到凸多边形的直径。即使在您不消除任何点的情况下，这些附加信息也正是有效解决问题所需要的。然而，找到凸多边形的直径并非易事。几篇已发表的包含该任务算法的论文被证明是不正确的。

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

另外，请注意 iphone 并没有那么有限。即使是完全朴素的算法，精心编写的实现也可以在不到十分之一秒的时间内处理 1000 个点。当然，使用正确的算法会让你走得更快 =)

Answer 3

从 x 坐标最低的点开始。（称为点 X）从点 x 开始构造“边界点”集合，并通过该点的垂直线，PointX 左侧不应有其他点）通过顺时针缓慢旋转线找到边界中的下一个点（或逆时针）直到线触及其他点，（见下文）。将该点添加到集合中并重复下一个点以获得下一个点，直到您最终回到原始点 x。您的 npw 有一组点构成完整集的边界。比较此缩减集中每对之间的距离，以找到相距最远的一对。

为了“旋转线”（找到每个连续的边界点），取与用于最后一个边界点的线垂直的方向上“最远”的点，并在最后一个边界点和那个“下一个”点。然后验证在由该新线形成的新垂直方向上没有其他点。如果在与这条线或最后一条线垂直的方向上没有其他点“进一步向外”，那么这是下一个边界点的正确选择，如果有这样的点，切换到那个点并重新测试。

Answer 4

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

我的快速总结：

1. 计算凸包中的点集（= O(n log n)，你得到 O(n) 的唯一时间是如果你先对列表进行排序，无论如何需要 O(n log n)）
2. 沿边界订购（如果您对#1使用Graham 扫描，您将免费获得此功能）
3. 使用其中一种 O(n) 直径算法来扫描具有最大直径的对映点。Shamos 算法对我来说看起来不错，因为它是旋转卡尺算法之一。