最小边界框 (MBB) 是体积最小的 3D 点云周围的框。
Joseph O'Rourke 发表 [2]用于查找 3 维点集的最小体积封闭框的立方时间算法。 O'Rourke 的方法使用 3 维旋转卡尺技术。
我阅读了文章和 wiki(最小边界框算法)[ 1 ].因为 极其复杂，我一无所获。此外，算法的执行步骤是我的下一个问题。
我想用 Fortran 编写 O'Rourke 算法。
任何有关算法或流程图等的提示都让我很高兴。
最佳答案
只是关于算法精神的提示。
首先，您需要计算点集的凸包，这是一个 2 维和 3 维的 O(N Log N) 过程。这给出了一个凸多边形(由顶点环描述)或多面体(由平面图描述)。
下一步是组合，包括尝试所有可能最紧的位置。在二维中，一个最小边界框与一条边齐平，依次尝试所有边的方向就足够了(旋转多边形使边变为水平，并构造AABB)。
3D 情况更为复杂，它使用了这样一个事实，即最紧的盒子与多面体的两个边齐平，在盒子的两个相邻面上(盒子不一定与一个面齐平)。此属性允许通过尝试所有对边来生成有限数量的方向，并且如上所述，将边带入两个坐标平面并构建 AABB。这需要一点球面三角学知识。
关于algorithm - 3D 中的最小边界框算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/63481946/