我正在寻找一种算法来找到包围多面体的最小盒子。
我的想法如下：找到最大的边，然后移动实体，使边与x轴对齐。找到与该边相交的下一个最大边，并将其尽可能靠近 z 轴对齐，同时将另一边留在 x 上。然后，计算 x、y 和 z 的最大差异。使用这些尺寸创建周围的形状，然后将框移回对象的原始位置。
有没有更有效的策略呢？我的想法是否忽略了一些极端情况？
编辑：现在假设要绑定的对象是凸的。不过，一般情况下的答案也将受到欢迎。
问问题
316 次
1 回答
1
O'Rourke 研究了为凸多面体寻找最小（体积）框的问题，他提出了一种O(n^3)算法：
J. O-Rourke。寻找最小的封闭框。国际计算机与信息科学杂志，1985 年，14(3)，第 183 页。
O'Rourke 的算法找到了一组点的最小封闭框R^3——但这显然等同于找到作为基础点集的凸包形成的多面体的封闭框。
与人们可能期望的相反（以及您所描述的方法，如果我理解正确的话），最小盒子不一定是定向的，使得多面体的面与盒子的面共面！请注意此处显示的简单四面体动画。
如果您对简单地找到一个相对较小的封闭框而不是最小的封闭框的想法感到满意，那么可能还有其他（更快）可以应用的启发式方法......
于 2015-06-12T02:30:08.657 回答