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

Exact Algorithm for Finding Minimum Oriented Bounding Boxes Based on Convex Hull

作　　者：秦启飞[1] 胡志刚[1] QIN Qi-fei;HU Zhi-gang(School of Software,Central South University,Changsha 410075,China)

机构地区：[1]中南大学软件学院,长沙410075

出　　处：《小型微型计算机系统》2018年第11期2518-2522,共5页Journal of Chinese Computer Systems

基　　金：国家重大科研仪器设备研制专项(51327902)资助;国家自然科学基金项目(61572525)资助

摘　　要：针对复杂物体三维点集的建模问题,提出一种基于几何计算的最小体积的封闭有向包围盒生成算法.对点集所构成的凸包进行分析,总结了凸包和其最小体积有向包围盒的4种边面接触类型.通过枚举凸包边的所有可能的组合,唯一确定包围盒的最优方向.实验证明,该算法可以快速生成符合模型体积特征的最小有向包围盒,且拟合效果良好.A new method is presented for computing tight-fitting enclosing minimum volume oriented bounding boxes for co〖JP2〗mplex objects point sets in three dimensions.The relationship between the convex hull and its minimum volume oriented bounding box with the smallest volume is analyzed and 4 kinds of edge contact types are summarized.The algorithm is based on enumerating all box orientations that are uniquely determined by combinations of edges in the convex hull of the input point set.Empirical evidence shows that this process always yields the globally minimum bounding box by volume,which leads to a conjecture that this method is in fact optimal.

关 键 词：有向包围盒 几何计算 凸包 三维点集 图搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]