海量数据Delaunay三角网的并行构建算法  

Parallel generation algorithm for Delaunay TIN with massive data

作　　者：张真[1] 

机构地区：[1]中国科学院计算技术研究所,中国科学院大学,中国北京100190

出　　处：《计算机工程与科学》2013年第4期1-7,共7页Computer Engineering & Science

基　　金：国家863计划资助项目(2009AA12Z226,2011AA120300)

摘　　要：对并行环境下Delaunay三角网的构建进行了研究。针对海量数据处理的高效性要求,提出了一种归并构网方法。该方法根据构网数据的实际分布特点,对数据点按x坐标进行排序,并将排序后的数据按给定的阈值点数依次分配给各工作线程,构建出一系列的初始子三角网,然后逐轮对相邻的子三角网进行两两归并,直至最终归并为一个三角网。该构网方法过程中子三角网间的相关性小,易于并行处理和流水线作业。该算法既适用于单机串行、多线程和多核并发环境处理,同时也适用于集群计算模式下的分布式并行处理。实验表明,该算法的时空效率较高,最坏的串行时间复杂度为O(nlogn),一般情况下不超过O(n2)。The paper studied a parallel generation algorithm for Delaunay TIN with massive data. To meet the efficient demands of processing massive data, the paper proposed a merge method of generating the Delaunay TIN. According to the spatial distribution of data points, the method firstly sorts the data by their x coordinates, allocates the sorted data to the corresponding threads, generates a series of initial sub-TINs, and merges two adjacent sub-TINs recursively. All the sub-TINs are finally merged to a TIN. The relativity between sub-TINs is weak in the process of merging, so that it is easy to be pro- cessed in parallel and pipelined. The algorithm can run in the serial mode. the multi-thread mode.the multi-core mode, and the distributed parallel computing environment. The experiment proves that the algorithm is efficient and the worst serial time complexity is 0 （n log n） and often less than O（n2）.

关 键 词：DELAUNAY三角网 子三角网 串行 并行 归并 复杂度 加速比 

分 类 号：TP393.027[自动化与计算机技术—计算机应用技术]