algorithm - 凸多边形的最大和最小对角线算法？

Question

有没有比蛮力比较更好的方法来获得多边形的最大和最小长度对角线？更具体地说，我想找到比率，这样我就可以根据它们的“皮肤”对多边形进行排序。

多边形不是太大（通常每个多边形有 4-8 个面），但数量很多。我想我只是和 SO 核对一下，看看是否有更好的方法来做到这一点。

提前致谢

Answer 1

多边形不是太大（通常每个多边形有 4-8 个面），但数量很多。

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

但是，您可以做的一件事来加快速度，就是在两点之间的距离公式中去掉平方根。首先找到 的最小值/最大值(xi-xj)*(xi-xj) + (yi-yj)*(yi-yj)，然后应用平方根。这是相当昂贵的操作，做 2 次而不是 20 次可能会有所作为。