| Delaunay三角网的并行构网算法 |
| |
| 引用本文： | 黄诠,刘浩,梁平元.Delaunay三角网的并行构网算法[J].测绘科学,2017,42(6). |
| |
| 作者姓名： | 黄诠 刘浩 梁平元 |
| |
| 作者单位： | 湖南人文科技学院信息学院,湖南娄底,417000 |
| |
| 基金项目： | 国家自然科学基金项目，湖南省教育厅科研优秀青年项目，湖南省教育厅科研项目，湖南省计算机应用技术重点建设学科资助项目，湖南人文科技学院“信息与通信工程”重点学科项目 |
| |
| 摘 要： | 针对传统的Delaunay三角网的并行构建算法负载均衡性不高、运行效率较低等问题,该文在综合逐点插入算法和分治算法各自优点的基础上,提出了一种Delaunay三角网并行构建算法。该算法首先使用动态格网剖分点要素集,从而得到若干点要素子集;然后根据点要素子集数量初始化线程池,每个点要素子集由一个线程按照插入点法构建Delaunay子网;当所有线程完成子三角网构建,最后使用逐点插入法合并所有子网,从而实现所有点要素的Delaunay三角网构建。分析与实验结果表明,相对于传统的并行算法,该并行算法的负载均衡性好、运行时间少、加速比高,具有较好的构建效率,而且构建结果满足Delaunay规则。
|
| 关 键 词： | 并行 分治算法 Delaunay三角网 格网 负载均衡 逐点插入 |
Parallel construction algorithm of Delaunay triangulated irregular network |
| |
| HUANG Quan,LIU Hao,LIANG Pingyuan.Parallel construction algorithm of Delaunay triangulated irregular network[J].Science of Surveying and Mapping,2017,42(6). |
| |
| Authors: | HUANG Quan LIU Hao LIANG Pingyuan |
| |
| Abstract: | Aiming at the problem of poor load balance performance and lower efficiency of traditional parallel construction algorithm of Delaunay triangulated irregular network,based on research on point by point insertion and divide-conquer algorithm,a parallel constructing algorithm of Delaunay triangulated irregular network based on point by point insertion and divide-conquer algorithm was presented.Firstly,the data set was divided into blocks by dynamic grids,and then thread pool was initialized according to the grid number,the point set in a grid by a thread was constructed into a network according to the method of point by point insertion.After all sub threads constructed their sub triangulated networks,all sub triangulated networks were treated by point by point insertion method.The analysis and experimental results showed that,comparing with traditional parallel algorithm,this parallel algorithm had better performance of load balance,less running time,high speed-up ratio,higher construction efficiency.Moreover,the structured results meet the Delaunay rules. |
| |
| Keywords: | parallel divide-conquer algorithm Delaunay triangulated irregular network grid load balance point by point insertion |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
