本文選題：并行 + 分治算法　； 參考：《測繪科學(xué)》2017年06期

【摘要】：針對傳統(tǒng)的Delaunay三角網(wǎng)的并行構(gòu)建算法負(fù)載均衡性不高、運行效率較低等問題,該文在綜合逐點插入算法和分治算法各自優(yōu)點的基礎(chǔ)上,提出了一種Delaunay三角網(wǎng)并行構(gòu)建算法。該算法首先使用動態(tài)格網(wǎng)剖分點要素集,從而得到若干點要素子集;然后根據(jù)點要素子集數(shù)量初始化線程池,每個點要素子集由一個線程按照插入點法構(gòu)建Delaunay子網(wǎng);當(dāng)所有線程完成子三角網(wǎng)構(gòu)建,最后使用逐點插入法合并所有子網(wǎng),從而實現(xiàn)所有點要素的Delaunay三角網(wǎng)構(gòu)建。分析與實驗結(jié)果表明,相對于傳統(tǒng)的并行算法,該并行算法的負(fù)載均衡性好、運行時間少、加速比高,具有較好的構(gòu)建效率,而且構(gòu)建結(jié)果滿足Delaunay規(guī)則。
[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