3D中的最小包围盒算法

Question

最小包围盒(MBB)是一个最小体积的三维点云周围的盒子。

约瑟夫·奥鲁尔克( Joseph‘’Rourke)发表了一种三次时间算法( [2] )，用于寻找三维点集的最小体积包围盒。O‘’Rourke的方法使用三维旋转卡尺技术.

我阅读了这篇文章和wiki (最小包围盒算法) [1]。由于极其复杂，我一无所获。此外，算法的执行步骤是我的下一个问题。

我想用Fortran写O‘’Rourke算法。

任何关于算法或流程图等的技巧都会让我感到高兴。

Answer 1

只是对算法精神的一个提示.

首先，您需要计算点集的凸包，即在2和3D中的O(N Log )过程。这给出了凸多边形(由顶点环描述)或多面体(描述为平面图)。

下一步是组合，包括尝试所有可能是最紧的位置。在2D中，最小边框与边缘平齐，然后依次尝试所有边缘的方向(旋转多边形，使边缘变为水平，并构造AABB)。

3D外壳更加精细，使用的事实是，最紧的盒子与多面体的两条边平齐，在盒子的两个相邻的面上(这个盒子不一定与一个面平齐)。该属性允许通过尝试所有的边对来生成有限的方向，如上所述，将边在两个坐标平面上并构造AABB。这需要一点球面三角。