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

Parallel generation algorithm for Delaunay TIN with massive data

对并行环境下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）.