Three-dimensional dispersion point cloud topological neighbor data query method

Abstract

The invention provides a three-dimensional scattered point cloud topological near neighbor data query method which is characterized in that: three-dimensional scattered point cloud data is collected, a dynamic hollow ball expansion algorithm is adopted to query a k-near neighbor point set based on a dynamic spatial index structure of R<*>-tree tissue three-dimensional scattered point clouds, sample point topological near neighbor reference data is obtained by the eccentric expansion and the self-adaptive expansion, a Voronoi diagram of the sample point topological near neighbor reference data is generated, data points which are corresponding to a sample point Voronoi neighborhood are queried, and the data points are the topological near neighbor data of the sample points. The use of the method can rapidly and accurately obtain the topological near neighbor data of any complicated mass scattered point clouds.

Description

Technical field [0001] The invention provides a method for querying three-dimensional scattered point cloud topological neighbor data, which belongs to the field of computational geometry. Background technique [0002] 3D scattered point cloud nearest neighbor data query is widely used in the fields of surface reconstruction and interpolation, geographic information system and differential geometry in reverse engineering. Its query efficiency and accuracy directly affect the speed and quality of data processing. [0003] At present, the commonly used methods for querying 3D scattered point cloud nearest neighbor data mainly include k nearest neighbor query and local Delaunay nearest neighbor query. Among them, k-nearest neighbor query mainly adopts spatial partitioning strategy. Xiong Bangshu et al. published the academic paper "k nearest neighbors of three-dimensional scattered data in the academic journal "Journal of Computer Aided Design and Graphics" 2004, 16(7), P909-912 In ...

AI Technical Summary

Problems solved by technology

Among them, the k-nearest neighbor query mainly adopts the spatial block strategy. Xiong Bangshu et al. published an academic paper on the academic journal "Journal of Computer-Aided Design and Graphics" 2004, 16(7), P909-912 "The k nearest neighbors of three-dimensional scattered data In the "Domain Fast Search Algorithm", the data space is divided into many cubic subspaces of the same size, and each point in the scattered point cloud is classified into the corresponding subspace. k-nearest neighbors; however, the k-nearest neighbors in the 3D scattered point cloud are only geometric neighbors, and for non-uniform point clouds, the k-nearest neighbors cannot reflect the local topological relationship at the sample point

Shan Dongri and Ke Yinglin proposed a two-dimensional Delaunay nearest neighbor query algorithm in the academic paper "Surface Reconstruction Algorithm Based on Two-Dimensional Delaunay Neighbors for Spatial Scattered Data" published in the academic journal "China Mechanical Engineering" 2003, 14, P756-758, based on k The nearest neighbor query algorithm obtains the k-nearest neighbor point set of the sample point, projects it to the least square plane, finds the Delaunay neighbor of the sample point from the projected points, maps it to the three-dimensional space, and obtains the original point corresponding to the projected point as a local model Based on the reference data, the Delaunay neighbors obtained by the algorithm are also the neighbors in the topological relationship of the sample point (i.e. topological neighbors). However, since the algorithm obtains its Delaunay neighbors based on the k-nearest neighbor point set query of the sample point, it cannot guarantee accurate acquisition Topological neighbor data of all sample points

Images