Delaunay三角网的并行构网算法

发布时间：2018-06-14 09:37

  本文选题：并行 + 分治算法　； 参考：《测绘科学》2017年06期

【摘要】：针对传统的Delaunay三角网的并行构建算法负载均衡性不高、运行效率较低等问题,该文在综合逐点插入算法和分治算法各自优点的基础上,提出了一种Delaunay三角网并行构建算法。该算法首先使用动态格网剖分点要素集,从而得到若干点要素子集;然后根据点要素子集数量初始化线程池,每个点要素子集由一个线程按照插入点法构建Delaunay子网;当所有线程完成子三角网构建,最后使用逐点插入法合并所有子网,从而实现所有点要素的Delaunay三角网构建。分析与实验结果表明,相对于传统的并行算法,该并行算法的负载均衡性好、运行时间少、加速比高,具有较好的构建效率,而且构建结果满足Delaunay规则。
[Abstract]:Aiming at the problems of low load balance and low running efficiency of the traditional parallel construction algorithm of Delaunay triangulation, this paper proposes a parallel construction algorithm for Delaunay triangulation on the basis of combining the advantages of point-by-point insertion algorithm and divide-and-conquer algorithm. The algorithm first uses dynamic grid to divide the point element set to obtain a number of point element subsets, then initializes the thread pool according to the number of point element subsets, each point element subset is constructed by one thread according to the insertion point method to construct the Delaunay subnet. When all threads complete the construction of the sub-triangulation, we use the point-by-point insertion method to merge all subnets, so as to realize the Delaunay triangulation of all point elements. The analysis and experimental results show that compared with the traditional parallel algorithm, the parallel algorithm has better load balancing, less running time, higher speedup, better construction efficiency, and the construction results meet the Delaunay rule.
，

本文编号：2016926