给定一组有序的2d像素位置（相邻的或相邻的对角线），它们形成一条完整的路径，没有重复，如何确定周长为该组像素的多边形的最大线性尺寸？（其中gld是集合中任意点对的最大线性距离）
就我的目的而言，显而易见的o（n^2）解对于数千个点的数字来说可能不够快。是否有好的启发式或查找方法使时间复杂度接近O（n）或O（log（n））？
最佳答案
一种简单的方法是首先找到点的凸壳，这种方法可以在o（n logn）时间内用多种方法实现。[我喜欢Graham scan（参见animation），但是incremental算法也很流行，正如others，尽管有些算法采用more time]
然后你可以找到最远的一对（直径），从凸面外壳上的任意两点开始（比如x和y），顺时针移动y直到它离x最远，然后移动x，再次移动y，等等。你可以证明整个过程只需要o（n）时间（摊销）。所以总共是o（n logn）+o（n）=o（n logn），如果你用礼品包装作为凸壳算法，可能是o（nh）。正如你所提到的，这个想法叫做rotating calipers。
这里是code by David Eppstein（计算几何学研究者；另请参阅hisPython Algorithms and Data Structures以供将来参考）。
所有这些代码都不是很难编写（最多应该是100行；在上面的python代码中不到50行），但是在编写之前，您应该首先考虑是否真的需要它。如果如您所说，您只有“数千个点”，那么在任何合理的编程语言中，平凡的O（N^2）算法（比较所有对）将在不到一秒钟的时间内运行。即使得了一百万分，也不应该超过一个小时。：-）
你应该选择最简单的算法。