• 地球信息科学理论方法 •

### 面向D-TIN并行构建的动态条带数据划分方法与实验分析

1. 1. 南京师范大学地理科学学院, 南京 210046;
2. 南京师范大学虚拟地理环境教育部重点实验室, 南京 210046;
3. 地理信息科学江苏省重点实验室, 南京 210046
• 收稿日期:2011-04-27 修回日期:2011-12-14 出版日期:2012-02-25 发布日期:2012-02-24
• 通讯作者: 沈婕(1969-),女,博士,副教授。主要研究方向为地图自动综合、电子地图与网络地图。 E-mail: shenjie@njnu.edu.cn。 E-mail:shenjie@njnu.edu.cn。
• 作者简介:齐琳(1988-),女,硕士,主要研究方向为地图综合并行算法。E-mail:qilin04043224@126.com

### Dynamic Strip Partitioning Method Oriented Parallel Computing for Construction of Delaunay Triangulation

QI Lin1,2,3, SHEN Jie1,2,3*, GUO Lishuai1,2,3, ZHOU Tong1,2,3

1. 1. School of Geographic Science, Nanjing Normal University, Nanjing 210046, China;
2. Key Laboratory of Virtual Geographic Environment, MOE, Nanjing 210046, China;
3. Key Laboratory of Geographic Information Science of Jiangsu Province, Nanjing Normal University, Nanjing 210046, China
• Received:2011-04-27 Revised:2011-12-14 Online:2012-02-25 Published:2012-02-24

Abstract: Data partitioning is an important step of parallel algorithm design. The load balance and efficiency of data partitioning is the precondition for improvement of parallel algorithm efficiency. For aggregated distributed point sets, the traditional Delaunay triangulation parallel algorithm can't ensure the balance and the execution's efficiency of the partitioning result. In view of the problems above, this paper we proposed a partitioning method using dynamic strips based on the idea of equally strips partitioning method in traditional Delaunay Triangulation construction and we titled it Dynamic Strip Partitioning Method. The detailed steps of this algorithm are as follows. First, the minimum bounding rectangle of the point data set should be obtained and the point set is roughly split using regular slim strips in the same direction. Then the number of points in every strip would be counted and the neighbor strips are merged into a partition region from the first strip in the sequence following a certain regulation. The boundaries of some strips should be moved dynamically if the total amount of points in these strips reached the load threshold value. In order to promote the efficiency of partitioning and reduce the boundaries movement, a rule of "move half points a time" has been used. We tested the speed-up of the Delaunay Triangulation parallel algorithm using the artificial point sets and tested the performance of the Delaunay triangulation parallel algorithm using the real test area point sets in the multi-kernel parallel computing systems. The results of the experiments showed that the method of dynamic strips partitioning can help to get high and stable speed-up of the Delaunay triangulation parallel algorithm and the data distributional pattern and size has less influence to it. Delaunay triangulation parallel algorithm based on dynamic strips partitioning method can get high efficiency and the speed-up effect is superior to the traditional method.