论文部分内容阅读
针对传统的Delaunay三角网的并行构建算法负载均衡性不高、运行效率较低等问题,该文在综合逐点插入算法和分治算法各自优点的基础上,提出了一种Delaunay三角网并行构建算法。该算法首先使用动态格网剖分点要素集,从而得到若干点要素子集;然后根据点要素子集数量初始化线程池,每个点要素子集由一个线程按照插入点法构建Delaunay子网;当所有线程完成子三角网构建,最后使用逐点插入法合并所有子网,从而实现所有点要素的Delaunay三角网构建。分析与实验结果表明,相对于传统的并行算法,该并行算法的负载均衡性好、运行时间少、加速比高,具有较好的构建效率,而且构建结果满足Delaunay规则。
Aiming at the problems such as low load balancing and low running efficiency of the parallel algorithm of Delaunay triangulation, this paper proposed a parallel construction of Delaunay triangulation based on the merits of each point insertion algorithm and divide-and-conquer algorithm algorithm. The algorithm first subdivides the set of points using the dynamic mesh to obtain a number of points, and then initializes the thread pool according to the number of points, and each sub-set of elements consists of one thread constructing the Delaunay sub-network according to the insertion point method. When all the threads have completed sub-triangulation, finally all the sub-networks are merged by point-by-point insertion, so as to realize Delaunay triangulation of all the points. The analysis and experimental results show that compared with the traditional parallel algorithm, the parallel algorithm has good load balancing, less running time and high speedup, and has good construction efficiency, and the construction results meet Delaunay rules.