航道工程水深数据三角化及边界生成算法的改进

　　在航道工程设计研究工作中，水深数据是非常重要的基础数据，各种分析计算工作需基于水深数据予以展开。在编制水深数据分析和处理相关的应用程序时，数字高程模型 DEM 的建立十分关键，而其中三角网建立算法的优劣不但会影响到计算效率更会直接影响到计算结果的可信度。Delaunay 三角网与 Voronoi 图是两个被普遍接受和广泛采用的分析研究区域离散数据的有利工具。1908 年，G Voronoi 首先在数学上限定了每个离散点数据的有效作用范围，并定义了二维平面上的 Voronoi 图。1934 年，B Delaunay 由Voronoi 图演化出了更易于分析应用的Delaunay三角网。

　　Delaunay 三角网具有两个特有的性质：空外接圆性质，即每个 Delaunay 三角形的外接圆不包含面内的其它任何点;最大的平均形态比，最小内角尽量最大[1]。以上性质决定了 Delaunay 三角网具有极大的应用价值。Lingas进一步论证了“在一般情况下，Delaunay 三角网是最优的”[2]。

　　Delaunay 三角网构网方法主要有 3 类：逐点加入法[3]，分割-合并法[4-5]以及三角网生长法[6]等。胡金星等[7]在分割-合并法的基础上，采用自适应格网划分方法分割点集构建 Delaunay 三角网，具有较高的执行效率，但算法较复杂;徐明海等[8]采用约束插入点技术，改进了形成三角网过程中插入点的确定等问题，克服了传统方法

　　须用递归调用及在多连通域剖分内边界复杂情况下清理网格的困难的缺点;邬吉明等[9]通过插入点顺序，提出了分级分治 Delaunay 三角剖分算法，减少生成三角形的废品率并提高运算效率;黄地龙[10]基于邬吉明等[9]的思想提出了基于矩形环分级分治的 Delaunay 三角网快速算法，但对于数据点分布不均匀的情况，运行效率将受影响;高晓沨[11]通过广度优先的遍历三角网格方法创建网格，较好地解决了数据加入顺序的影响并避免了生成瘦三角形。

　　通常 Delaunay 三角化需要在给定边界信息的情况下进行，否则生成的网格系统与实际几何体将有较大的出入，特别是对多连通域内的离散点进行三角化时，情况更加明显。周秋生等[12]通过最长边限制下的离散点来生成边界，对于简单多边形区域内离散点边界生成，该算法是有效的;而对于复杂区域内离散点的边界生成，如当多边形区域内含空腔时，离散点的边界还包括内边界的生成，对于内边界生成，该算法并不可行。在航道工程中，水深数据量大，数据可能很规则亦可能极不规则，对于分布复杂并存在多连通的水深数据，三角化要求较低的三角形废品率，并尽可能使得生成的三角网边界符合水深点的实际分布。基于逐点加入法构建 Delaunay 三网的原理，引入栅格索引和三角形拓扑属性，改进了加入点定位和影响域的确定与重构，实现快速 Delaunay 三角化的目的，同时，在三角化的基础上借助三角形链表和拓扑属性，优化三角网并生成水深点边界。整套算法实现简单，时间复杂度良好，通用性较强。