Parallel Construction Algorithm Of Delaunay

Due to the excellent characteristics of Delaunay triangulation such as maximizing the minimum angle,Delaunay triangular mesh model has wide applications in reverse engineering,surface reconstruction and other fields.With the continuous deepening of the application of the Delaunay triangular mesh model,there are higher requirements on the conformation efficiency,accuracy and stability of Delaunay triangular mesh.Therefore,improving the efficiency of Delaunay triangulation has become a research hotspot.In recent years,researchers have applied parallel computing to various algorithms to improve the algorithm efficiency.In order to improve the efficiency of Delaunay triangulation,this paper applies parallel algorithms to Delaunay triangulation algorithm in two dimensions,and the main work is as follows.Aiming at the low efficiency of the existing Delaunay triangulation algorithm,this paper proposes a parallel Delaunay triangulation algorithm.First,the center of gravity and the center point of the two-dimensional point set to be dissected are divided into several relatively uniform subsets in an iterative manner,and then the Delaunay triangular network of each subset is constructed in parallel,and then the triangles of other points in the point set inside the outer circle of the boundary part of the subset Delaunay triangular network are deleted,and then the boundary edges and free points are re-dissected.Finally,the subset Delaunay triangulation network after removing some triangles is directly merged with the triangulation network constructed during re-profiling to obtain the global Delaunay triangulation network.At the point set size of 1000 000,compared with the single-threaded algorithm of grid division proposed by Yang Jun et al,the present algorithm reduces the dissection time by 55.12% in four-thread parallel experiments.To address the problem that some triangles need to be deleted when subset Delaunay triangle networks are merged,an adaptive dichotomous parallel Delaunay triangle network growth algorithm is proposed in this paper.First,we construct a guide line for point set dichotomy according to the distribution of points in the point set,then construct Delaunay triangles along the guide line,and divide the point set into two subsets according to the position relationship between points and triangles,then dichotomize each subset in parallel until the number of points in each subset is less than the segmentation threshold,then construct Delaunay triangle nets for each subset in parallel.Finally,the global Delaunay triangulation network is obtained by combining the triangle generated at bisection point set and the triangulation network constructed by subnet.When the point set size is 30 000,compared with the single-thread algorithm of Delaunay triangulation network growth proposed by You Lei et al,this algorithm reduces the segmentation time by 66.11% in four-threaded parallel experiments.