發(fā)布時(shí)間：2018-06-14 09:37

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

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

本文編號(hào)：2016926