Research On The Method Of Boundary Identification For Sampled Data Of Physical Surface

Sampled data of physical surface is a set of scattered points in space which represents the three-dimensional coordinate information of the physical surface. There are some points in the set that can express the boundary feature of the original surface, which constitute the boundary points of the sampled data. This thesis carries out an extensive and systematic research into the algorithm of boundary identification for sampled data of physical surface, and makes some improvement to the problems existing in current boundary identification algorithms including incomplete boundary extraction, poor adaptability and large identification errors, which improves the efficiency and precision of boundary identification, thus laying a solid foundation for subsequent surface reconstruction. The main research content and results are listed below:(1) A query algorithm of topological neighbors of a point based on reverse mean shift is proposed. Take the k-nearest neighbors as the intial topological neighbors, and convert the iterative process of mean shift from querying the maximum value to the minimum value of the probability density, which can shift neighbors search area toward the sparse region of the sampled data near the objective point, thus realizing the topological neighbors query by obtaining some neighbors in the parse region. The query result can express the boundary feature of the original surface better, and can be obtained rapidly with RR*-tree.(2) A boundary identification algorithm based on kernel density estimation is proposed. The objective point and its topological neighbors constitute the local surface reference data, and the kernel density estimation is applied to the reference data to obtain the mode point which can reflect the distribution feature of the reference data. Boundary points are identified by comparing the deviation extent between the objective point and its mode point with good adaptability for the sample data of non-uniform distribution.(3) Clustering analysis is used to classify the boundary points, and an adapting k-means algorithm via principal components analysis (PCA) guided is proposed in order to improve the clustering goodness. The selection method of initial cluster centers based on the combination of forward stepwise optimization and PCA solves the problem that k-means clustering is prone to get into the local convergence, improves the efficiency of forward stepwise optimization and the stability of clustering results, which provids a foundation for boundary classification.(4) Flatness of the local surface reference data is regarded as the basis for distinguishing the boundary point types, and k-means clustering algorithm is used to estimalate the natural clustering of the data set consist of residual sum of squares of the local surface reference data with its tangent plane, thus solving the classification problem of all kinds of boundary points effectively.