几何对象统一表示的R~＊-tree结点分裂算法  

Node splitting algorithm for R＊ -tree based on united expression of all geometry objects

作　　者：孙殿柱[1] 李延瑞[1] 朱昌志[1] 孙永伟[1] 

机构地区：[1]山东理工大学机械工程学院,山东淄博255091

出　　处：《华中科技大学学报（自然科学版）》2010年第2期55-58,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家高技术研究发展计划资助项目(2006AA04Z105)

摘　　要：针对R*-tree应用到逆向工程领域时遇到的适用性差等问题,提出一种新的R*-tree点分裂算法.该算法将R*-tree索引结点表示为最小包围盒,依据最小包围盒外接球间的重叠度衡量结点间的相似值,结合k-means算法,随机提取两个结点作为初始分簇中心,依据结点间的相似值计算新的分簇中心并迭代分簇,直到分簇中心不再变化,实现R*-tree的结点分裂.实例表明,该算法可处理各种复杂几何对象的R*-tree结点分裂问题,并可优化R*-tree结构,显著提高结点的分裂效率.Aimed at the problems that R＊-tree is used in reverse engineering,a new node splitting algorithm of R＊-tree is proposed,which has three steps： first,the nodes of R＊-tree are all expressed as their minimum bounding boxes;second,the nodes′ comparability value is weighed with circum-sphere of their minimum bounding boxes;third,two random nodes are chosen as initial clustering centers,and the clustering process is iterate updated until the clusters′ centers do not change,which is proved that it has strong adaptability of data type,can optimize the structure of R＊-tree and improve the efficiency of node splitting.

关 键 词：逆向工程 R＊-tree 最小包围盒 结点相似值 K-MEANS算法 结点分裂 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]