基于凸包的最小有向包围盒生成算法

秦启飞，胡志刚

(中南大学 软件学院，长沙 410075)

1 引 言

物体的包围盒广泛应用于图像处理、模式识别、碰撞检测、模具分型设计和机械控制等领域[1,2].目前应用最广泛的OBB(Oriented Bounding Box，有向包围盒)根据物体本身的几何形状来决定包围盒的大小和方向，可以对原模型进行紧凑的拟合[3].对于给定的三维点集，怎样高效而准确地得到其最小有向包围盒一直是国内外学者关注的问题[4].

一般考虑物体的所有顶点在空间的分布，通过不同的算法找到最佳方向，以确定OBB包围盒的几个轴.主要使用数值和统计优化方法来找到非最优，但在实际使用中足够好的近似值.目前的主流方法是使用主成分分析(PCA)[5]，根据物体表面的顶点，计算特征向量来估计点集中最大扩展的方向，并作为OBB的主轴.这个过程必须使用凸包上的连续集合表示来完成，否则近似值可能是无界差的[5].为了获得接近最优的结果，Barequet and HarPeled提出一个(1 +α)逼近方案[6]，而另一方面，Larsson和 Kallberg则提出可以采用预定义的启发式方法来获得更好的计算速度[7].国内的陈柏松等[4]提出了基于非线性主成分分析的最小包围盒计算方法，在计算时间和运行结果上都取得了不错的效果，但是该方法利用了顶点之间的连接信息，无法处理无连接关系的点集数据.

还有学者提出使用粒子群优化[8]和遗传算法[9]来计算最佳结果，取得了不错的效果.但这些算法中包含随机因子，不能保证在所有情况下都找到最佳包围盒.

法国的Chang等提出……