基于四维聚类的R^＊-树结点分裂算法

摘要

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出一种新的R*-树结点分裂算法,该算法以R*-树结点最小边界矩形外接球半径为权值,对点、三角形、矩形等多种三维几何对象进行加权处理,将其统一表示为四维点对象,选定距离最远的两个四维点作为初始分簇中心,根据点到两分簇中心的距离进行分簇,结合k-means算法以结点外接球半径为权值计算新的分簇中心,并迭代分簇过程,直到各分簇中心不再变化,结束R*-树的结点分裂过程。试验证明,采用该结点分裂算法可处理复杂数据对象的分簇,并在提高建树效率的同时,优化R*-树结构,提高空间查询效率,对提高逆向工程数据预处理效率具有重要意义。