问凸多边形最大最小对角线的算法？
EN

Stack Overflow用户

提问于 2010-08-16 04:59:48

回答 1查看 990关注 0票数 2

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

多边形不是太大(通常每个多边形有4-8个面)，但数量很多。我想我应该检查一下SO，看看有没有更好的方法。

提前感谢

回答已采纳

发布于 2010-08-16 05:06:18

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

我不知道是否有比O(n^2)更快的解决方案，但对于n <= 8来说这无关紧要。如果是n = 8，你只需要勾选20条对角线(8 * 5 / 2)。它本身并不是很大的乘法器，而且任何复杂的算法都可能有大量的计算开销(数据结构，复杂的循环和检查)。

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

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/3489240

复制

相似问题

问凸多边形最大最小对角线的算法？EN