给定一组点，如何找到彼此最远的两个点？
可能的重复：
最大线性维度二维点集
我可以计算每个点之间的距离点并取最大的，但是当有大量（> 1000）点时，这听起来不是一种非常有效的方法。
注意：这是针对 iPhone 的，所以我没有太多的处理能力。
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
可能的重复：
最大线性维度二维点集
我可以计算每个点之间的距离点并取最大的，但是当有大量（> 1000）点时，这听起来不是一种非常有效的方法。
注意：这是针对 iPhone 的，所以我没有太多的处理能力。
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（4）
为什么不直接计算点的凸包？根据您使用的算法，它需要
O(n)或O(n log n)时间，并消除所有内部点的考虑。然后，仅检查这些最外面的点以找到距离最远的两个点。Why not just compute the convex hull of the points? Depending on the algorithm you use, it takes either
O(n)orO(n log n)time and eliminates all the inner points from consideration. Then, only check these outermost points to find the two that are the farthest away.您要求计算该集合的直径。标准技术是首先计算凸包，这将问题简化为查找凸多边形的直径。即使在不消除任何点的情况下，这些添加的信息也正是有效解决问题所需要的。然而，求出凸多边形的直径并不是一件容易的事。几篇发表的关于此任务的算法的论文被证明是不正确的。
这是相当可读的讨论 任务的正确 O(n) 算法（其中 n 是凸包中的点数）。
另请注意，iPhone 并不受此限制。即使是完全简单的算法，精心编写的实现也可以在不到十分之一秒的时间内处理 1000 个点。当然，使用正确的算法会让你走得更快 =)
You're asking to compute the diameter of the set. The standard technique is to first compute the convex hull, which reduces the problem to finding the diameter of a convex polygon. Even in the case where you don't eliminate any points, this added information is exactly what's needed to solve the problem efficiently. However, finding the diameter of a convex polygon is not entirely trivial; several published papers with algorithms for this task turn out to be incorrect.
Here's a fairly readable discussion of a correct O(n) algorithm for the task (where n is the number of points in the convex hull).
Also, note the the iphone isn't that limited; a carefully written implementation of even the completely naive algorithm can handle 1000 points in less than a tenth of a second. Of course, using the correct algorithm will let you go much faster =)
从 x 坐标最低的点开始。 （称之为X点）
构造“边界点”集
从点 x 开始，通过该点的垂直线，PointX 左侧不应有其他点）通过顺时针（或逆时针）缓慢旋转线找到边界中的下一个点，直到线接触其他点，（见下文）。将该点添加到集合中，并重复下一个点以获得下一个点，直到最终回到原始点 x。你有一组点形成完整集合的边界。比较该简化集合中每对之间的距离，以找到相距最远的对。
要“旋转线”（以找到每个连续边界点），请取与最后一个边界点所用线垂直的方向“最远”的点，并在最后一个边界点和该“下一个”点。然后验证在该新线形成的新垂直方向上是否没有其他点。如果在垂直于这条线或最后一条线的方向上没有其他点“进一步向外”，那么这是下一个边界点的正确选择，如果存在这样的点，则切换到该点并重新测试。
Start with point with lowest x-coord. (Call it Point X)
Construct set of "boundary points"
starting with point x, and vertical line through the point, There should be no other points to left of PointX) find the next point in boundary by slowly rotating the line clockwise (Or counterclockwise) until the line touches some other point, (see below). Add that point to the set and repeat with that next point to get the next one, until you eventually get back to the original point x. You npw have a set of points forming the boundary of the complete set. Compare distance between each pair in this reduced set to find the pair that are furthest apart.
To "rotate the line" (to find each sequential boundary point), take the point which is "furthest" in the direction perpindicular to the line used for the last boundary point, and construct a new line between the last boundary point and that "next" point. Then verify that there are no other points furthur in the new perpindicular direction formed by that new line. If there are no other points "furthur out" in the dirtection perpindicular to this line or to the last line, then this is the right cjhoice for the next boundary point, if there is such a point, switch to that one and retest.
请参阅这些页面（链接到和单击“下一个”链接可访问的页面）计算一组点的凸包直径。
我的快速总结：
See these pages (the one linked to and the pages reachable by clicking on the "next" links) on computing the diameter of the convex hull of a set of points.
My quick summary: