论文部分内容阅读
逆向工程中R*S树索引结构的引入有效提高了产品逆向过程中各环节数据处理的效率和质量,包括海量点云数据精简、散乱点云拓扑近邻查询、边界特征提取、曲面重建、曲面求交、剪裁及拼接以及CAM环节中刀路的计算等。索引结构的优劣直接影响逆向建模效率与精度,而结点分裂作为R*S树索引构建过程中的关键步骤,对索引结点的体积、结点重叠度以及最终索引查询的效率起到决定性的作用。本文深入系统地对R*S树结点分裂方法进行了研究,解决了结点分裂过程中分裂数和最优初始聚类中心的选取问题,使结点分裂更能体现数据的真实空间分布,并有效避免了结点陷入局部收敛问题。主要研究内容与研究成果如下：(1)提出一种可以根据R*S树索引结点的真实空间分布准确计算结点最优分裂数k的数值拟合算法。采用逐次增加结点分裂数k的方法,每次运用k均值算法进行迭代分簇,并记录最终分簇结果相对应的类内聚w内,最后利用曲线拟合思想把离散的类内聚数据集拟合成光滑曲线,所得曲线拐点附近对应的分裂数k作为最优结点分裂数。实例证明该算法能够根据各结点之间的结构特征和分布特征进行聚类分簇,所得的自适应分裂数能最大化地体现结点之间的真实空间分布。(2)提出一种基于主元分析的R*S树结点k均值聚类分裂初始点选取算法。引入k均值算法作为结点分裂的基本算法,把k均值算法初始点的选取作为数据简化问题,并基于主元分析思想对数据对象进行降维聚类,找到数据对象的主要分布趋势,并以类内聚为评价规则自动判断迭代过程中主元分析的目标簇,计算各簇的中心并以簇中心为k均值算法的初始值进行聚类分簇。实例证明该算法可快速、高效地获取体现结点空间分布的初始点,有效避免k均值算法的参数依赖性缺陷和局部收敛问题,使得R*S树结点能够根据真实的聚类特征进行分裂,有效减小了结点的体积,降低了结点之间的重叠度。(3)基于曲线拟合和主元分析对R*S树结点进行分裂,并构建R*S树索引。由于主元分析和曲线拟合思想处理对象都是点集,而R*S树结点分裂的处理对象是数据对象的最小包围盒,具有一定的形状和位置,因此把结点包围盒的顶点和中心作为特征点集,利用曲线拟合和主元分析进行结点分裂,最终实现R*S树索引构建。此种方法构建的R*S树在构建时间和精度上都得到有效的提高,大幅降低结点之间的重叠度,提高R*S树索引的数据查询效率。