一种简单的方法是首先找到这些点的凸包，可以通过多种方式在O（nlogn）时间内完成。[我喜欢Graham扫描（请参见动画），但是增量算法和其他算法一样也很流行，尽管有些算法需要更多时间。

然后，您可以通过从凸包上的任意两个点（例如x和y）开始找到最远的一对（直径），顺时针移动y直到它与x距离最远，然后移动x，再次移动y，等等。证明整个事情只需要O（n）时间（摊销）。因此，总共为O（nlog n）+ O（n）= O（n log
n），如果您使用礼物包装作为凸包算法，则可能为O（nh）。正如您提到的，这个想法称为旋转卡尺。

这是DavidEppstein（计算几何研究人员；另请参阅他的Python算法和数据结构，以供将来参考）的代码。

所有这些都不是很难编写的代码（最多应该是一百行；在上面的Python代码中少于50行），但是在您这样做之前-您首先应该考虑是否真正需要它。如您所说，如果您只有“数千个点”，那么在任何合理的编程语言中，琐碎的O（n ^2）算法（将所有对进行比较）都将在不到一秒钟的时间内运行。即使拥有一百万点，它也不会花费一个多小时。:-)

您应该选择 最简单的 算法。