摘要
针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出一种新的R*-树结点分裂算法,该算法以R*-树结点最小边界矩形外接球半径为权值,对点、三角形、矩形等多种三维几何对象进行加权处理,将其统一表示为四维点对象,选定距离最远的两个四维点作为初始分簇中心,根据点到两分簇中心的距离进行分簇,结合k-means算法以结点外接球半径为权值计算新的分簇中心,并迭代分簇过程,直到各分簇中心不再变化,结束R*-树的结点分裂过程。试验证明,采用该结点分裂算法可处理复杂数据对象的分簇,并在提高建树效率的同时,优化R*-树结构,提高空间查询效率,对提高逆向工程数据预处理效率具有重要意义。
Aiming at the problems of R＊-tree when it is used in reverse engineering, such as poor applicability, a new R＊-tree node splitting algorithm is proposed. The radius of the circum-sphere of R＊-tree node＇s minimum bounding rectangle regarded as weight value, points, rectangles and triangles in three-dimensional space are treated as weighted objects, which are looked as four-dimensional points uniformly. The two four-dimensional points, the distance of which is largest, are chosen as initial clustering centers. The clustering procedure is carried through according to the distance between point and two cluster centers. When the radius of the node＇s circum-sphere are treated as weight value, the new clustering center is calculated with k-means algorithm. And the clustering process is being iterated to update the clustering centers until the clustering centers do not change. Experimental analysis shows that the node splitting algorithm can deal with the clustering of complex data of different type, and the time of constructing R＊-tree is minimized, the structure of R＊-tree is effectively optimized and the efficiency in spatial querying is improved drastically. The new node splitting algorithm has important significance to improving the effect of data pretreatment in reverse engineering.
出处
《机械工程学报》
EI
CAS
CSCD
北大核心
2009年第10期180-184,共5页
Journal of Mechanical Engineering
基金
国家高技术研究发展计划资助项目(863计划
2006AA04Z105)
