Abstract: 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.

Key words: Four-dimensional clustering algorithm, k-means, Node splitting, R*-tree