Fast Delaunay triangulation method for arbitrarily-distributed large-scale point cloud data

Abstract

The invention provides a fast Delaunay triangulation method for arbitrarily-distributed large-scale point cloud data, comprising the following steps: dividing a multi-grid to create an initial triangulated network; inserting points one by one; updating the triangulated network; and deleting auxiliary triangles to complete Delaunay triangulation. Through multi-grid division and a sorting method through sequential grid traversing based on a Hilbert curve, the search step length in the point positioning process and the number of finally-deleted long-narrow triangles produced in the triangulation process are reduced. By adopting a new algorithm in the point positioning process, the process of solving the centers of gravity and intersecting edges of triangles is avoided, and the amount of calculation is reduced. The efficiency of Delaunay triangulation under the condition of a large amount of point cloud data and uneven distribution thereof is improved greatly.

Description

technical field [0001] The invention relates to the technical field of information processing, in particular to a fast Delaunay network construction method for arbitrarily distributed large-scale point cloud data. Background technique [0002] Triangulation is one of the important research contents in the field of computational geometry, and Delaunay triangulation is widely used in geographic information system, digital elevation interpolation, finite element analysis, geometric reconstruction and other fields due to its many excellent properties. [0003] The construction methods of Delaunay triangulation can be mainly divided into three types: point-by-point insertion method, divide-and-conquer algorithm and triangulation growth method. Among them, the triangular network growth method is rarely used at present due to the frequent traversal of data points, low time efficiency and complex algorithm. The advantage of the divide-and-conquer algorithm is that it is time-effici...

AI Technical Summary

Problems solved by technology

[0005] First: The processing object has low requirements on the processing efficiency of the algorithm for a small number of discrete point clouds, but when the number of point clouds is large, the processing efficiency of the algorithm is generally low, which has a great impact on network construction;

[0006] Second: Due to the uneven distribution of point cloud data, the regular grid method will form a lot of grids with too dense or too sparse distribution of point sets in the process of grid division, so that the degree of grid division cannot be unified, which affects the subsequent processing efficiency;

[0007] Third: In the current point positioning process, the process of calculating the coordinates of the center of gravity and finding the intersecting edges greatly increases the amount of calculation and reduces the speed of building a Delaunay network for massive point cloud data.

Images