在航道工程设计研究工作中，水深数据是非常重要的基础数据，各种分析计算工作需基于水深数据予以展开。在编制水深数据分析和处理相关的应用程序时，数字高程模型 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 三角化的目的，同时，在三角化的基础上借助三角形链表和拓扑属性，优化三角网并生成水深点边界。整套算法实现简单，时间复杂度良好，通用性较强。
1 算法描述
1.1 Delaunay 三角化
三角化的基本步骤如下：首先根据给定离散点集的包容盒(XMin, YMin, XMax, YMax)建立一个初始三角形。然后依次加入点，定位包含该点的三角形并确定外接圆包含该点的三角形集合，即影响域，随后删除影响域，依据 Delaunay准则，在影响域内重构三角形，直至离散点集内的所有点均被加入到三角网中。最后，根据约束
性条件，标记不符合约束性条件的三角形(如空腔内部三角形等)并进行三角网局部优化。1.2 边界生成完成三角化后，开始边界生成。外边界生成从任意一个外边界三角形开始，利用三角形属性和拓扑关系，生成离散点边界;内边界生成从标记为不符合约束性条件的三角形开始，算法与外边界生成类似。复杂离散点集，可能包含多个外边界和内边界，需要遍历整个三角网完成所有可能边界的生成。
2 算法关键问题
2.1 主要数据结构
三角化过程中需要进行大量的三角形定位和三角形邻边三角形信息访问，为了便于对形成的三角形进行组织管理，设计了栅格单元内三角形索引和三角形链表。栅格单元内三角形索引采用二维整形数组，记录属于该栅格元的三角形索引号;三角形链表负责记录所生成的三角形属性信息及其相邻三角形的索引号。在核心算法的
实现上，采用了基于三角形的数据结构，其伪代码描述如下：
栅格单元内三角形定义如下：若点 A 属于某栅格单元，则顶点包含点 A 的三角形即是该栅格单元内三角形集合的元素。同一栅格单元可以包含一系列内三角形，而在三角形快速定位时所需的初始三角形可以是该栅格单元内三角形的任意一个。在实际应用中，当加点较为有序时，加入点位置较接近，使得包含下一加入点的三角形接近当前加入点生成的局部三角网。因此，为了提高定位效率，将栅格单元内最新生成的三角形作为初始三角形。
通过栅格索引和三角形拓扑，可以方便地完成算法中可能用到的拓扑访问，包括：已知点定位包含该点的栅格单元，已知栅格单元查询该栅格单元内的三角形，已知三角形查找它的 3 个顶点，已知三角形查找各边相邻的三角形，已知点查询以它为顶点的三角形，查找所有边界三角形及边界边等。
由此可得到任意离散点对应的栅格单元号。图 1(a)为整个栅格中原始点分布图，图 1(b)为引入新加入点时搜索初始三角形示意图，图中Ⅰ、Ⅱ、Ⅲ表示已经生成的栅格单元内三角形。根据点所在的栅格单元号和栅格单元内三角形索引，可快速取出搜索的初始三角形。当点所在的栅格单元包含三角形时，如图 1(b)点 i，则直接取三角形Ⅰ作为初始三角形;当网格内不存在三角形时，则向该网格的外围网格遍历，只到搜索到包含三角形的网格为止，如图 1(b)点j 沿路径②搜索到三角形Ⅱ(当三角形Ⅲ比三角形Ⅱ晚形成时，取三角形Ⅲ)，点 k 沿路径③搜索到三角形Ⅲ;当加入第一点时，直接将初始三角形赋为生成三角网中的第一个三角形。采用这样的搜索方式可以使得搜索到的起始三角形尽可能靠近加入点，提高三角形的定位效率。当加入点较少而网格总数相对较多时，可以直接从已生成的三角网中取出最新一个作为初始三角形，避免遍历网格的时间消耗。顶点、栅格、三角形关系如图 2 所示。
找到初始三角形后，需要快速定位包含新加入点的三角形。成基华等[13]采用有向边的方法来定位新加入点的三角形，由于新加入点常位于一个三角形两条有向边的同一侧，使得这样的搜索路径可能不是最优的。采用外法线方向搜索技术，以三角形重心(GP)和新加入点(NP)的连线为指示方向，计算三角形的三边朝外法矢，沿法矢方向最接近指示方向所在边的相邻三角形搜索，可快速定位包含新加入点的三角形Tfirst。对于特殊离散点数据，特别是对于较规则有序数据，在三角化的过程中常生成较多的瘦三角形(即最小角小于某一角度如 30o的三角形)，使得该方法搜索的可能陷入死循环中，如图 3 所示。此时，需要将搜索方向跳转到沿法矢方向次接近指示方向所在边的相邻三角形上。
2.3 影响域的快速确定与重构
搜索出 Tfirst后，就可以将它作为初始多边形向其周围扩张，寻找出所有外接圆包含插入点的三角形，删除影响域内三角形同时修改原三角形链表，最后重构三角形。该过程由一个递归函数完成，示意图如图 4 所示.
2.4 边界生成
边界生成包含外边界生成和内边界生成。由离散点构成最小凸多边形时，边界是唯一确定的，而当构成凹多边形时，边界具有不确定性。边界生成算法在离散点三角化及优化的基础上，利用三角形链表和拓扑属性构建。
在三角形数据结构中，若顶点 A 所对的边为外边界，则顶点 A 所对的三角形索引定义为-1，内边界三角形按其标记属性进行判断。
以外边界生成算法为例，如图 5 所示，步骤如下：
步 1 如果三角形个数=1，则按逆时针返回三角形 3 个顶点，程序结束;否则，令 i=0;
步 2 判断 triangles(i)是否为外边界三角形，如为是(如存在边界 BA)，执行步 3;如为否，i++，重新执行步2;
步 3 取 triangles(i)边界，将边界起点(B)添加到边界点集中，将边界终点(A)作为标记点 , 按 逆 时 针 方 向 判 断 下 一 三 角 形triangles(iNext)，其中 iNext=当前判断三角形中标记点的下一点所对的三角形索引号(如当前判断△ABC 中，标记点为 A，则标记点下一点为 B，其所对的三角形索引号为△ACD 的下标)。当
triangles(iNext)为边界三角形时，i=iNext，重新执行步 3;当该三角形非边界三角形时，执行步4;当标记点为边界点集起始点 B 时，执行步 5;
步 4 以标记点(A)为搜索中心，判断下一三角形 triangles(iNext)，当该三角形为边界三角形时，i=iNext，执行步 3;当该三角形非边界三角形时，重新执行步 4;
步 5 保存边界点集，继续遍历其它未搜索过的三角形，执行步 2;当三角网中所有三角形均已搜索过时，结束。
内边界的生成算法与外边界生成算法类似
3 效率与实例
算法在 PC 机上利用 C#.net 编程实现，并对随机离散点进行效率分析，时间效率测试结果如图 6，图中纵坐标为相对运算机时，即对 N 个散点构网总耗时与生成一个三角形平均耗时之比。相 对 运 算 机 时 与 散 点 数 的 关 系 为y= 0.613x1.396，其中 x 为散点数，y 为相对运算机时，相关系数为 0.999。
利用上述算法，对某航道水深数据进行Delaunay 三角化及边界生成，结果如图 7 所示，生成的三角网边界与原始水深点吻合，构建合理，优于未进行边界生成的原始三角网外边界。
4 结论与展望
改进的 Delaunay 三角化算法，在传统的逐点加入算法的基础上进行了改进，采用栅格索引和三角形拓扑使得该方法对大尺度复杂的散乱数据集的处理具有更大的优势，不会因为数据的纵横尺度差异较大或数据点分布不均匀而影响运行效率。在三角化的基础上，利用三角形链表和拓扑属性生成边界的算法，适应了航道工程水深数据
分布复杂特别是多连通情况下水深点三角网边界构成。该算法的应用提高了航道工程水深数据三角网生成效率和生成质量，从而保证了相关计算成果的可信度。
