Delaunay三角网通用合并算子及分治算法的简化

Delaunay三角网在未来地学数值模拟中将发挥重要作用。分治算法是一种著名的经典构网算法,但其子网合并过程十分复杂,限制了其应用。提出使用通用算子的概念,并用从以往算法中独立出来的算子和3个新算子来简化分治算法的子网合并。扩展三角形算子用于构造每个新三角形并维护三角网的拓扑关系和边界链表。凹边界填充算子对边界链表用递归来自动完成凹边界的智能三角形填充。子网合并算子先用一个新三角形连接两个子三角网,再合并边界链表,调用凹边界填充算子填充子网间的缝隙区域。所有算子都基于有向边的数据结构和用链表管理的三角网外边界,借助链表操作,使算法的构建简洁而又高效。除分治法外,这些算子还被成功用于构建其他算法。由随机点集以及LiDAR点云的测试表明,所有算法的构网均准确无误且分治算法的执行效率较高。

Merging planar Delaunay triangulations based on universal operators and the implementation of a divide-conquer algorithm

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.