三维物体的准最小包围盒快速求解方法

摘要

Aiming at high cost of solving the accurate minimum bounding box of 3D shape, a fast solution method for the quasi minimum bounding box based on sampling point set of the object surface was proposed.In this method, an incremental clustering algorithm was proposed to simplify the non-feature region of the point set.Then to solve the exact minimum bounding box of the simplified point set, which was used as the location space of the original point set.Finally, regard the minimum axial bounding box of the location space as the quasi minimum bounding box of 3D shape.The results show that, under the premise of accuracy requirement, the computational efficiency of this method is increased by 90% and 30% respectively compared with the O'Rourke method and genetic algorithm.%针对现有求解精确三维物体最小包围盒算法的时间复杂度过高这一问题,提出一种基于物体表面采样点集的准最小包围盒快速求解方法.该方法首先提出一种增量式聚类简化算法对物体表面采样点集的非特征区域进行大幅简化,并将简化后点集的精确最小包围盒作为求解原始采样点集准最小包围盒的定位空间,以该空间下的最小轴向包围盒作为原始三维物体的准最小包围盒.试验结果表明,在满足求解精度要求的前提下,该方法与采样点集的精确最小包围盒求解方法相比,其计算效率提高90%左右,与基于遗传算法的求解方法相比,其计算效率最大可提高30%.