An Efficient Distributed and Parallel Delaunay Triangle Construction Method

Abstract

The invention discloses an efficient distributed and parallel Delaunay triangle construction method. The method comprises the following steps of firstly, determining the recursive partitioning frequency k of problem solving and the number 2k of leaf problems according to the scale p of a distributed and parallel computing environment; secondly, sorting data sets of to-be-solved problems with the scale of n in a flat scanning sequence mode; thirdly, performing gradual partitioning from top to bottom by adopting a partitioning strategy of a divide-and-conquer method, and recursively partitioning the to-be-solved problems with the scale of n into the 2k leaf problems; fourthly, performing convex-hull-method Delaunay triangular net parallel construction of sub-problems on the 2k leaf problems by using 2k parallel computing nodes; and finally, gradually combining solutions of the sub-problems from bottom to top by adopting a combination strategy of the divide-and-conquer method, and performing distributed and parallel combination processing by using t / 2 computing nodes during combination each time until a global solution of a global problem is obtained, wherein the number of the sub-problems is n. According to the method, the efficiency is remarkably improved.

Description

technical field [0001] The invention relates to the construction of a Delaunay triangular network, in particular to a highly efficient distributed and parallel Delaunay triangular construction method which combines divide-and-conquer and convex hull techniques. Background technique [0002] Delaunay Triangulation Network (D-TIN) is an important content of Geographic Information System (GIS) data expression, management, integration and visualization, and it is also used in geoscience analysis, computer vision processing, target surface reconstruction, finite element analysis, road CAD technology, etc. An important application technology in the field. Many researchers have done a lot of research on the construction of Delaunay triangulation, and several mature methods have been proposed in terms of algorithm implementation, such as point-by-point insertion method (Incremental), triangulation growth method, divide and conquer method (Divide and Conquer). ) and convex hull meth...

AI Technical Summary

Problems solved by technology

[0004] For the task of building a Delaunay triangular network with a scale of n, the existing distributed and parallel methods based on the divide and conquer method inevitably have the following two problems: (1) The CPU overhead of network scheduling and the communication bandwidth and time of data transmission are not considered The cost of the distributed and parallel computing method needs to have enough distributed and parallel computing nodes to ensure that all the leaf problems of the distributed and parallel computing method (2 (log2n-1) ) to achieve parallel computing, so as to obtain the theoretically most efficient solution

From two aspects of computing efficiency and practical application of algorithms, the existing distributed and parallel computing methods are not suitable for the construction of distributed and parallel Delaunay triangulation in the actual big data environment

Images