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

作者：刘永和; 冯锦明; 郭维栋; 田根; 金毅

来源：中国图象图形学报, 2012, (10): 1283-1291.

• Delaunay三角网
• 通用算子
• 子网合并
• 凹边界填充
• 分治法 Delaunay triangulation
• universal operators
• merging of triangulations
• basin-filling
• divide-conquer algorithm

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

• 单位
  中国科学院; 中国科学院大气物理研究所; 南京大学; 河南理工大学