Parallel construction method of Delaunay triangulated network

Abstract

The invention discloses a parallel construction method of a Delaunay triangulated network, belonging to the technical field of computer networks. The method comprises the following steps: a host node judges whether input point set data exceeds a set threshold P; if the point set data exceeds the set threshold P, the number n of available nodes is acquired; if the point set data exceeds n*P, n*P numbered data points in the point set data are reserved; the point set data is divided into two parts, one part is reserved for the host node, and the other part is distributed to child nodes; the hostnode and the child nodes thereof respectively judge whether the data distributed to the host node and the child nodes thereof exceeds the set threshold P; if the data exceeds the set threshold P, thehost node and the child nodes continue to distribute the data points until the data point of each node does not exceed the threshold P; if the data does not exceed the set threshold P, each node carries out triangulated network construction on the finally reserved data; a leaf node sends the constructed triangulated network to a father node to be combined until the host node; and the host node combines the constructed triangulated network with the received triangulated networks. The invention fully utilizes the computer node resources and maximizes the parallelization of the construction process of the triangulated network.

Description

technical field [0001] The invention belongs to the technical field of computer networks, and relates to a parallel construction method of a Delaunay triangular network. This method can make full use of computing node resources, maximize the parallelization of the Delaunay triangulation process, and achieve better results. Background technique [0002] In the past ten years, many scholars and experts at home and abroad have proposed many effective algorithms on the construction method of Delaunay triangulation. Generally, various TIN algorithms can be divided into point-by-point insertion algorithm, TIN growth method and divide-and-conquer algorithm. The time complexity of the point-by-point insertion algorithm in the worst case is O(N 2 ). However, if the points are inserted randomly, the performance will be O(NlogN). But because the algorithm process needs to be sorted, its time complexity cannot be further improved. The divide-and-conquer algorithm is very efficient,...

AI Technical Summary

Problems solved by technology

Master-slave structure mode ( figure 1 (b) Although the defects of the peer-to-peer structure have been solved, new problems have been introduced, which are mainly reflected in the following points: (1) The main tasks of the host are resource management, initiation of parallel computing tasks, and node computing results (2) All task division, allocation, and summary are completed by the host, and these processes are not fully parallelized; (3) In addition to communicating with the host, leaf nodes also need to communicate with other The leaf nodes communicate, and the communication overhead is not minimized

Images