凸多边形最大和最小对角线的算法？
有没有比暴力比较更好的方法来获取多边形的最大和最小长度对角线？更具体地说，我想找到比率，这样我就可以根据多边形的“厚度”对多边形进行排序。
多边形不是太大（通常每个多边形有 4-8 个面），但数量很多。我想我应该咨询一下SO，看看是否有更好的方法来做到这一点。
提前致谢
Is there a way better than a brute force comparison to get the max and min length diagonals of a polygon? To be more specific, I would like to find the ratio, so I can sort polygon on their "skinniness."
The polygons aren't too large (usually 4-8 faces per polygon), but there's a lot of them. I thought I'd just check with SO to see if there was a better way of doing this.
Thanks in advance
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
多边形不是太大（通常每个多边形有 4-8 个面），但数量很多。
我不知道是否有比 O(n^2) 更快的解决方案，但是对于 n <= 8 来说，这并不重要。如果
n = 8，则只需检查 20 条对角线 (8 * 5 / 2)。它本身并不是那么大的乘数，任何复杂的算法都可能有大量的计算开销（数据结构、复杂的循环和检查）。不过，为了加快计算速度，您可以做的一件事就是在两点之间的距离公式中舍弃平方根。首先求
(xi-xj)*(xi-xj) + (yi-yj)*(yi-yj)的最小值/最大值，然后应用平方根。这是一个相当昂贵的操作，执行 2 次而不是 20 次可能会有所不同。The polygons aren't too large (usually 4-8 faces per polygon), but there's a lot of them.
I don't know if there's a faster solution than O(n^2), but for
n <= 8it's not gonna matter. Ifn = 8, you just have to check 20 diagonals (8 * 5 / 2). It's not so big multiplier itself, and any complex algorithm is likely to have a lot of computational overhead (data structures, sophisticated loops and checks).One thing you can do to speed it up, though, is to throw away square root in the formula of distance between two points. First find min/max of
(xi-xj)*(xi-xj) + (yi-yj)*(yi-yj), then apply square root. It's quite expensive operation and doing it 2 times instead of 20 could make a difference.