给定一组有序的二维像素位置(相邻或相邻对角线)形成一条没有重复的完整路径，我如何确定周长为该组像素的多边形的最大线性维度？ (其中 GLD 是集合中任意一对点的最大线性距离)
就我的目的而言，明显的 O(n^2) 解决方案对于数千点的数字可能不够快。是否有好的启发式或查找方法可以使时间复杂度更接近 O(n) 或 O(log(n))？
最佳答案
一个简单的方法是先找到点的凸包，这可以通过多种方式在 O(n log n) 时间内完成。 [我喜欢Graham scan (参见 animation )，但是 incremental算法也很受欢迎，others 也是如此。 , 虽然有些人需要 more time .]
然后你可以找到最远的一对(直径)，方法是从凸包上的任意两点(比如 x 和 y)开始，顺时针移动 y 直到它离 x 最远，然后移动 x，再次移动 y，等等. 你可以证明这整个事情只需要 O(n) 时间(摊销)。所以它总共是 O(n log n)+O(n)=O(n log n)，如果你使用礼品包装作为你的凸包算法，则可能是 O(nh)。这个想法叫做rotating calipers ，正如您提到的。
这里是 code by David Eppstein (计算几何研究员；另请参阅他的 Python Algorithms and Data Structures 以供将来引用)。
所有这些都不是很难编写代码(最多应该是一百行；在上面的 Python 代码中不到 50 行)，但是在您这样做之前——您应该首先考虑您是否真的需要它。如果如您所说，您只有“数千个点”，那么在任何合理的编程语言中，简单的 O(n^2) 算法(比较所有对)将在不到一秒的时间内运行。即使有一百万点，也不应该超过一个小时。 :-)
您应该选择有效的最简单算法。
关于algorithm - 最大线性维度 2d 点集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/321989/