Optimization Method On Node Self-Adaptive Splitting Of R~*S-Tree

The introduction of R*S-tree into reverse engineering improves efficiency and quality of data processing in every reversing stage which includes reduction of scattered points, inquiring topological neighbors, extraction of scattered data boundary characteristics, surface reconstruction, getting intersection for surface, surface tailoring and stitching,and tool path calculating in CAM, etc. The pros and cons in constructing the indexing structure determine the quality and efficiency of reverse modeling, and node splitting, as a critical step in constructing the indexing structure, determine the node volume, overlap degree and index-efficiency. This paper discusses the methods for node splitting of R*S-tree, and solves problems in producing the number of clustering and the optimal original clustering centers, which makes the node splitting reflects the real distribution of spatial data and avoids local convergence. The main research content and results are listed below:(1) An numerical fitting algorithm to compute the optimal splitting number k, based on the real spatial distribution of R*S-tree, is proposed. The number k is increased successively, for every k, a k-means algorithm is used to cluster the nodes. The class cohesion w(k) corresponds to the final clustering result is recorded. In the end, the discrete class cohesion data is fitted into smooth curve, and the number k corresponds to the data near the inflexion of the curve is the optimal nodes splitting number. Experiments show that this algorithm performs clustering according to the structure characteristics and distribution between nodes, and the resulting adaptive splitting number reflexes the real distribution between nodes.(2) Based on principal component analysis, an algorithm to select the initial point for the k-means clustering in the nodes splitting of the R*S-tree is proposed. The classical algorithm, k-means, is introduced as the basic algorithm for nodes splitting. Firstly, regarding selecting the initial points for k-means algorithm as data reduction process. Then according to principal component analysis,dimensionality reduction is performed on clustering for the data, and the main trend of distribution of the data is found. The class cohesion is used as the evaluation criterion to determine the target cluster in the iterative process. The centre of every cluster is abtained, and these centres are used as the initial points for k-means algorithm. Experiments show that this algorithm gets the initial points that reflex the distribution of the nodes with higher speed and efficiency. Using these initial points for k-means process can reduce the parameters dependence and avoid local convergence, which makes R*S-tree nodes splitting perform according to the real clustering characteristics and reduces the volume and the coincidence degree of nodes of R*S-tree. (3) Finally, R*S-tree nodes splitting and indexing structure construction based on carve fitting and principal component analysis are realized.Since the objects of carve fitting and principal component analysis are point set and the objects of R*S-tree nodes splitting are the minimum bounding boxes of data which have shape and position, so vertices and centres of the minimum bounding boxes are taken as the feature point set and nodes are split based on principal component and carve fitting, and finally the construction of R*S-tree indexing structure is finished without the shortcoming of classical k-means. With this method, both of the efficiency and quality of R*S-tree constructing are improved, and the coincidence degree of nodes of R*S-tree is reduced. This method also improves the spatial query efficiency of R*S-tree.