第7期 2017年7月
组合机床与自动化加工技术
Modular Machine Tool & Automatic Manufacturing Technique
文章编号：10012265(2017)07005104
D0I:10. 13462/j. cnki. mmtamt.2017.07.012
三维物体的准最小包围盒快速求解方法
尹逊刚"，孙殿柱"，李延瑞2，徐昭
No.7 Jul.2017
（1.山东理工大学机械工程学院，山东淄博255049；2.西安交通大学机械工程学院，西安 711049)
摘要：针对现有求解精确三维物体最小包图盒算法的时间复杂度过高这一问题，提出一种基于物体表面采样点集的准最小包围盒快速求解方法。该方法首先提出一种增量式聚类简化算法对物体表面采样点集的非特征区城进行大幅简化，并将简化后点集的精确最小包图盒作为求解原始采样点集准最小包围盒的定位空间，以该空间下的最小轴向包国盒作为原始三维物体的准最小包图盒。试验结果表明，在满足求解精度要求的前提下，该方法与采样点集的精确最小包围盒求解方法相比，其计
算效率提高90%左右，与基于遗传算法的求解方法相比，其计算效率最大可提高30%。关键词：最小包国金；k均值聚类；定位空间；轴向包围金
中图分类号：TH161;TG506
文献标识码：A
Fast Solution Method of Quasi Minimum Bounding Box for 3D Shape
YIN Xun-gang , SUN Dian-zhu',LI Yan-rui’,XU Zhao
( 1. School of Mechanical Engineering, Shandong University of Technology , Zibo Shandong 255049, China ;2. School of Mechanical Engineering, Xi'an Jiaotong University, Xi'an 710049, China)
Abstract : 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 accura cy requirement, the computational efficiency of this method is increased by 90% and 30% respectively com pared with the O' Rourke method and genetic algorithm.
Key words: minimum bounding box; k means clustering: location space; axial bounding box
0引言
物体的最小包围盒在当今许多实际问题的解决中有着重要的应用。在工业设计领域中，针对产品的包装设计，快速成型等，利用包围盒技术可以为毛坏用料最优化设计提供依据；在机械零件的铸造分型中，利用最小包围盒可获得最优分型方间：碰撞检测中，用实物的最小包围盒代替复的几何物体，可显著提高相交测试的效率-)
国内外许多学者对包围盒求解方法进行了多方面的研究。O'Rourke[+]根据物体的凸包与其包围盒的关系实现了精确最小包围盒的求解方法。文献[5-7]以点集的主元向量作为坐标轴求解其轴向最小包围盒。陈华"}通过固定步长的角度不断旋转模型所在坐标系计算旋转过程中的最小轴向包围盒。孙殿柱"等将遗
收稿日期：20161107：修回日期：20161117
传算法与O'Rourke算法相结合求解物体的最小包围盒。宋洋1]等基于型面特征和均值漂移的算法对原始数据进行二次精简来计算近似最小包围盒
上述算法虽然取得了较好的计算效果，但是时间复杂度过高。因此，本文对物体表面采样点集进行聚类简化，基于简化结果采用O'Rourke算法确定物体准最小包围盒的定位空间，在该空间中求解采样点集的轴向包围盒，将所得结果作为物体的准最小包围盒，试验结果表明，所求解准最小包围盒能准确的逼近其精确最小包围盒，计算效率显著提高。
采样点集特征数据的分离
在求解物体表面采样点集最小包围盒时，特征样点是指边界样点及表面轮廊曲率变化较大的数据点，其与非特征样点的最主要区别在于其近邻点集密度分
*基金项目：国家自热科学基金资助项目（51575326）；山东省自然科学基金项目（ZR2015EM031）
作者简介：尹避则(1990—），男，济南人，山东理工大学硕士研究生，研究方向为CAD/CAM，（E-mail)770186316@q9.com；通讯作者：孙股柱
（1956—），男，山东烟台人，山东理工大学教投，研究方向为CAD/CAM、通向工程，（Email)dianzhus@sdut.edu.cn。
万方数据