韦云舰，卢 中

（1.甘肃省地质矿产勘查开发局第三地质矿产勘查院，甘肃 兰州 730050；2.中交第二航务工程勘察设计院有限公司，湖北 武汉 430071）

工程测量中常采用不规则三角网（TIN）模型来表示地形。为了使三角形能更好地对地形变化进行拟合，应尽量使三角形接近等边，三角形的最小角最大。经证实，一般情况下在所有可能形成的三角网模型中，Delaunay三角网是最优的。由于Delaunay三角网构网复杂，因此不同算法的执行效率存在较大差异。现有较成熟的Delaunay三角网构网方法主要包括三角网生长法、逐点插入法和分治法3种，各有利弊[1-4]。本文以经典Delaunay三角网生长法为基础，对三角形寻找第三点的方法进行了优化，明显提升了该方法的执行效率；并将三角网成果用于提取道路断面，分析了其实用性。

1 经典Delaunay三角网生长法

Delaunay三角网生长法是基于Delaunay三角网的空圆特性的，即Delaunay三角网中任意一个三角形的外接圆内不存在其他点。基于此， Delaunay三角网生长法的构网步骤为：①任选点库中的一个点P1；②遍历点库，寻找距点P1最近的点P2，并与之相连构成第一边，添加到边库中；③遍历点库，寻找第三点与P1、P2构成三角形，使之外接圆满足空圆特性，并将第三点与P1、P2的连线添加到边库中，相应的三角形添加到三角形库中（如ΔP1P2P4外接圆内存在点P3，不满足条件，而ΔP1P2P3外接圆内不存在其他点，满足条件，如图1所示）；④遍历边库，判断各边两侧是否应构建新的三角形，若边两侧均存在三角形或不存在其他点，则该边已构建……