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

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

作　　者：刘永和[1] 冯锦明[2] 郭维栋[3] 田根[1] 金毅[1] 

机构地区：[1]河南理工大学资源环境学院,焦作454000 [2]中国科学院东亚区域气候-环境重点实验室全球变化东亚区域研究中心中国科学院大气物理研究所,北京100029 [3]南京大学气候与全球变化研究院/大气科学学院,210093

出　　处：《中国图象图形学报》2012年第10期1283-1291,共9页Journal of Image and Graphics

基　　金：国家自然科学基金项目(41105074,40975048,40975049);中国科学院数字地球重点实验室开放研究基金项目(2011LDE010);河南理工大学博士基金项目(B2011-038);淮河流域气象开放研究基金项目(HRM200904)

摘　　要：Delaunay三角网在未来地学数值模拟中将发挥重要作用。分治算法是一种著名的经典构网算法,但其子网合并过程十分复杂,限制了其应用。提出使用通用算子的概念,并用从以往算法中独立出来的算子和3个新算子来简化分治算法的子网合并。扩展三角形算子用于构造每个新三角形并维护三角网的拓扑关系和边界链表。凹边界填充算子对边界链表用递归来自动完成凹边界的智能三角形填充。子网合并算子先用一个新三角形连接两个子三角网,再合并边界链表,调用凹边界填充算子填充子网间的缝隙区域。所有算子都基于有向边的数据结构和用链表管理的三角网外边界,借助链表操作,使算法的构建简洁而又高效。除分治法外,这些算子还被成功用于构建其他算法。由随机点集以及LiDAR点云的测试表明,所有算法的构网均准确无误且分治算法的执行效率较高。Delaunay triangulation will play an important role in numerical simulation of the geophysical process in the fu ture. The divideconquer algorithm is one of the wellknown traditional fast Delannay algorithms, but its c0mplicatied mer ging procedure has limited the applicability of this algorithm. In this study, we propose the concept of universal opera tors, 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 divideconquer al gorithm. The operator of expanding a triangle is developed for construct^ng 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 devel oped for automatically filling the basins by creating new triangles using recursions. The triangulationmerging operator is de veloped for linking two subtriangulations using one new triangle, transforming the two original linked list of border edgesinto 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 opera tions 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 divideconquer al gorithm. Large point datasets generated stochastically as well as LiDAR point clouds are used for testing the operatorbased algorithms, and the result shows that the algorithms can correctly generate triangulations. Meanwhile, it is shown that the divideconquer algorithm based on the operators are almost as fast as the horizontal expanding algorithm.

关 键 词：DELAUNAY三角网 通用算子 子网合并 凹边界填充 分治法 

分 类 号：P283[天文地球—地图制图学与地理信息工程]