关键词: Delaunay三角网, 子三角网, 串行, 并行, 归并, 复杂度, 加速比

Abstract:

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 processed 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 O (nlogn) and often less than O(n2).

Key words: Delaunay TIN;subTIN;serial；parallel;merge;complexity;acceleration ratio