给定一组点，我如何找到彼此最远的两个点？
可能重复：
最大线性尺寸2d点集
我可以计算每个点之间的距离并取最大值，但是当有大（> 1000）点数时，这听起来不是一种非常有效的方法。
注意：这适用于iPhone，因此我没有大量的处理能力。
你要求计算集合的直径 。 标准技术是首先计算凸包，这减少了找到凸多边形直径的问题。 即使在您没有消除任何积分的情况下，这些增加的信息正是有效解决问题所需要的。 然而，找到凸多边形的直径并非完全无关紧要; 一些已发表的论文与此任务的算法结果是不正确的。
这是对任务的正确O（n）算法的相当可读的讨论 （其中n是凸包中的点数）。
另外，请注意iphone不是那么有限; 即使是完全天真的算法，精心编写的实现也可以在不到十分之一秒的时间内处理1000个点。 当然，使用正确的算法会让你走得更快=）
为什么不计算点的凸包呢？ 根据您使用的算法 ，它需要O(n)或O(n log n)时间并消除考虑的所有内部点。 然后，只检查这些最外面的点，找到距离最远的两个点。
从具有最低x-coord的点开始。 （称之为点X）构造从点x开始的“边界点”集合，以及通过点的垂直线，PointX左边应该没有其他点）通过顺时针缓慢旋转线来找到边界中的下一个点（或者逆时针方向）直到线接触其他一些点，（见下文）。 将该点添加到该集合并重复该下一个点以获取下一个点，直到最终返回到原始点x。 你npw有一组点形成整套的边界。 比较该减少的集合中每对之间的距离，以找到最远的对。
要“旋转直线”（找到每个连续的边界点），将在垂直方向上“最远”的点取向用于最后一个边界点的直线，并在最后一个边界点与“之间”构造一条新线。下一个“点。 然后validation在新线形成的新的perpindicular方向上没有其他点。 如果在这条线或最后一条线路上没有其他点“向外”，那么这就是下一个边界点的正确选择，如果有这样一个点，切换到那个并重新测试。
在计算一组点的凸包的直径时，请参阅这些页面 （链接到的页面和通过单击“下一个”链接可到达的页面）。
我的快速摘要：
- 计算凸包中的点集（= O（n log n），唯一得到O（n）的是你首先对列表进行排序，无论如何都需要O（n log n）
- 沿着边界排序（如果你使用格雷厄姆扫描 ＃1，你可以免费获得这个）
- 使用O（n）直径算法之一扫描具有最大直径的对映点。 Shamos算法对我来说很好，因为它是旋转卡尺算法之一。