The Three-Dimensional Index Structure Of R~*-tree Based On The Minimum Bounding Box And The Adaptive Clustering

For the index structure problems of the poor adaptability, low utilization of space in the reverse engineering, The three-Dimensional index structure of R*-tree based on the minimum bounding box and the adaptive clustering(R*OA-tree) was proposed, the point cloud divided Index structure according to the different distribution of point cloud point cloud will be divided into normal and abnormal distribution point cloud according to the different distribution of point cloud, and the minimum bounding box of point cloud was construction using the principal component analysis algorithm and the minimum cylindrical fitting algorithm, and the local coordinate was construction by the minimum bounding box, established the axis bounding box under the local coordinate; The best number of clusters of node splitting was got based on the gap statistics to achieve the node splitting by k-means, which is proved that it has strong adaptability of data type, can optimize the structure of R*OA-tree and improve the R*OA-tree spatial query efficiency.This issue presents a highly efficient and stable spatial index structure R* OA-tree, to meet the data in the field of reverse engineering of space to store, manage and query needs, main contents and results are as follows:1. The traditional gap statistics was optimized, to solve the problem of Tedious calculations, the low efficiency at the time of obtaining the best number of clustering, mathematical expression access of gap calculation was proposed, and the accuracy of obtaining the best number was increased; and simplify the calculation procedure of gap statistics, improve the efficiency of the frequency to obtain the best clustering.2. For the problem of dependence for the parameters in the process of node splitting, the algorithm of the adaptive splitting was proposed, the best number of clusters was obtained based on the overall similarity for clustering evaluation function and the variation of the gap function, and the adaptive clustering was achieved by the k-means, which can Reduce the dependence of the clustering parameters.3. For the problems of the current node overlap high and low utilization of space of R*-tree, the algorithm of R*OA-tree which the overall minimum bounding box and the local axial bounding box was proposed, the minimum bounding box of data was construction, and the of local coordinates achieve was achieved, so as to achieve the R*OA-tree in the local coordinate system.