Delaunay三角网的并行构网算法

摘要：

针对传统的Delaunay三角网的并行构建算法负载均衡性不高、运行效率较低等问题,该文在综合逐点插入算去和分治算法各自优点的基础上,提出了一种Delaunay三角网并行构建算法.该算法首先使用动态格网剖分点要素集,从而得到若干点要素子集;然后根据点要素子集数量初始化线程池,每个点要素子集由一个线程按照插入点法构建Delaunay子网;当所有线程完成子三角网构建,最后使用逐点插入法合并所有子网,从而实现所有点要素的Delaunay三角网构建.分析与实验结果表明,相对于传统的并行算法,该并行算法的负载均衡性好、运行时间少、加速比高,具有较好的构建效率,而且构建结果满足Delaunay规则.

关键词：并行、分治算法、Delaunay三角网、格网、负载均衡、逐点插入

所属期刊栏目：42

分类号：TP309(计算技术、计算机技术)

资助基金：国家自然科学基金项目61571188;湖南省教育厅科研优秀青年项目15B125;湖南省教育厅科研项目12C0743;湖南省计算机应用技术重点建设学科资助项目;湖南人文科技学院“信息与通信工程”重点学科项目

在线出版日期：2017-07-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：171-177