围绕多面体的最小矩形框

Question

我正在寻找一种算法,找到包围多面体的最小盒子.

我的想法如下:找到最大的一侧,并移动实体,使侧面与x轴对齐.找到遇到这一侧的下一个最大的一侧,并将其尽可能靠近z轴对齐,同时将另一侧放在x上.然后,计算x,y和z的最大差异.使用这些尺寸创建周围的形状,然后将框移回对象的原始位置.

对此有更有效的策略吗？我的想法是否忽略了一些角落案例？

编辑:现在假设要限制的对象是凸的.虽然,对一般情况的答案也是受欢迎的.

Answer 1

O'Rourke 研究了寻找凸多面体的最小（体积）盒子的问题，他提出了一种O(n^3)算法：

J.奥洛克。寻找最小的封闭盒子。国际计算机与信息科学杂志，1985 年，14(3)，第 183 页。

奥罗克的算法找到了一组点的最小包围盒R^3——但这显然等同于找到形成为基础点集的凸包的多面体的包围盒。

与人们的预期相反（以及您所描述的方法，如果我理解正确的话），最小盒子不一定定向为使得多面体的面与盒子的面共面！请注意此处显示的简单四面体动画。

如果您对简单地找到一个相对较小的封闭框而不是最小的封闭框的想法感到满意，那么可能还有其他（更快的）启发式方法可以应用......