R-tree Construction And Topology Nearest Neighbor Query With Out-of-Core For Massive Point Cloud

A spatial index with good performance and good reference data of local surface has great influence on surface reconstruction.On the present,the results of choosing subtree and node splitting of popular R-tree can be not well due to optimize indicator with single target serial optimization.The k nearest neighbor set can't be used to reflect the feature of local surface when the point cloud is non-uniform distribution and k is small.Because the scale of point set is so large,even overtop memory limit,the mechanism of R-tree building and k nearest neighbor searching can be invalid.Based on multi-objective optimization,the algorithm of choosing subtree and splitting node for the R-tree can be improved.The topology nearest neighbor set can be obtained by optimize the k nearest neighbor set with extending the search bounding sphere followed the result of principal component analysis.Based on the strategy of Out-of-Core,the Out-of-Core hierarchical storage mechanism of R-tree and the Out-of-Core query mechanism of region nearest neighbor can be achieved with database SQLite.The key research contents include:(1)The algorithm of form and position,multi-objective optimization,clustering for R-tree can be proposed.The choosing subtree can be treated as the multi-objective optimization,and the decision-making vector includes the girth increment and overlap increment of node bounding box after inserting object.The splitting axis can be chose based on the form and position of child node for overflow-node at each axis.Based on the overlap,the candidate splitting solutions can be filtered with clustering algorithm,and the candidate solution corresponding to minimal sum of perimeter can be regarded as the optimum solution of overflow-node splitting.The problem that the performance of R-tree fails due to optimize indicator with single target serial optimization can be solved.The distribution of nodes and the distribution of data points can be consistent and the performance of R-tree can be improved.(2)The Out-of-Core strategy of R-tree can be proposed.The hierarchical storage mechanism of point cloud can be achieved by combined the database SQLite and R-tree.The R-tree index structure can be stored in the main memory and the data points can be stored in the secondary storage.The problem that the R-tree can't be build due to that the scale of massive point cloud is largely or even exceed the memory limit can be solved effectively.(3)The algorithm of region nearest neighbor searching of principal component analysis orientation and adaptive extension can be proposed.The k nearest neighbors set can be segmented into two subsets by the second principal element plane through target point.The ration between smaller subset and the k nearest neighbors set and the preset threshold can determine whether the search bounding sphere could be increased.The adaptive topology nearest neighbors query can be achieved for every point,which can improve the query efficiency.The upper limit of radius of search bounding sphere can be set up,which can solve the problems that unlimited query of points in the boundary or edge and cross-border query of points in the different surface.The topology nearest neighbors set can effectively reflect the local surface feature.(4)The Out-of-Core query of region nearest neighbor can be proposed.Firstly,search nearest leaf nodes in the main memory.Secondly,load data points corresponding to the nearest leaf nodes from the secondary storage into the main memory with the database SQLite.Finally,the nearest neighbor points of target point can be obtained.For searching the nearest leaf nodes in the main memory,some pruning strategies can be made,which can reduce the number of node traversal and lead to improve the query efficiency.For searching the nearest point set,the strategy of using and then search?deleting after used can be proposed,which can make the memory usage to be minimum.The Out-of-Core query strategy of topology nearest neighbors can be adapt to the Out-of-Core hierarchical storage mechanism of R-tree and reduce memory usage when searching the nearest neighbors set.