Merging planar Delaunay triangulations based on universal operators and the implementation of a divide-conquer algorithm
Delaunay三角网通用合并算子及分治算法的简化

Delaunay triangulation will play an important role in numerical simulation of the geophysical process in the future. The divide-conquer algorithm is one of the well-known traditional fast Delaunay algorithms,but its complicatied merging procedure has limited the applicability of this algorithm. In this study,we propose the concept of universal operators,which are used to simplify the construction of the Delaunay triangulation algorithm. Several operators are extracted from some previous Delaunay algorithms,and three new operators are used in the merging process of the divide-conquer algorithm. The operator of expanding a triangle is developed for constructing each new triangle and for managing the topology information and the linked list which represents the border edges of the triangulation. The operator of filling basins is developed for automatically filling the basins by creating new triangles using recursions. The triangulation-merging operator is developed for linking two sub-triangulations using one new triangle,transforming the two original linked list of border edges into one new linked lists with a new sequential order,and filling the two basins by calling the operator of filling basins. All these operators are based on the same set of data structures and the linked list represented triangulation hull. Using operations on the linked list,all search operations in the triangulation hull are avoided,which make the final algorithm very concise and fast. The operators are successfully used for construct other Delaunay algorithms besides the divide-conquer algorithm. Large point datasets generated stochastically as well as LiDAR point clouds are used for testing the operator-based algorithms,and the result shows that the algorithms can correctly generate triangulations. Meanwhile,it is shown that the divide-conquer algorithm based on the operators are almost as fast as the horizontal expanding algorithm.