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

摘要：

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

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

所属期刊栏目：17

分类号：P283(地图制图学（地图学）)

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

在线出版日期：2012-12-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1283-1291