凸多边形最大和最小对角线的算法?

多边形不太大(通常每个多边形有4-8个面),但有很多。

我不知道是否有比O(n^2)更快的解决方案,但是 n <= 8 没关系。如果 n = 8 你只要检查20条对角线( 8 * 5 / 2 )它本身并没有那么大的乘数,任何复杂的算法都可能有大量的计算开销(数据结构、复杂的循环和检查)。

不过,有一件事可以加快速度,那就是去掉两点之间距离公式中的平方根。首先查找的最小值/最大值 (xi-xj)*(xi-xj) + (yi-yj)*(yi-yj) ,然后应用平方根。这是一个相当昂贵的操作,2次而不是20次会有不同。