Delaunay三角网点定位算法在输电线路设计中的应用

摘 要：目前山区线路的施工图设计中仍采用人工配置长短腿的方法，作业效率低下。本文通过引入Delaunay三角网点定位算法，提出长短腿自动配置的设想并编程实现，极大提高了作业效率。

关键词：输电线路；长短腿；Delaunay三角网

DOI：10.16640/j.cnki.37-1222/t.2019.08.188

1 引言

山区输电线路的设计要求作业人员根据不同的塔基地形进行长短腿配置，人工判读各接腿范围内的高程及动态使工作量非常大。若引入测绘的数据处理方法，利用计算机技术实现高程信息的自动化读取和配腿工作的程序化表达，则能大大提高作业效率。

2 铁塔长短腿自动配置的核心算法

长短腿自动配置的核心算法分两类，一类是DEM重构和任意插入点定位算法，决定软件的工作效率；另一类是长短腿配置算法，决定配置结果的准确性。

2.1 DEM重构算法

在数字地形的描述中，不规则三角网模型（简称TIN）是被公认为一种最基本和最重要的DEM模型，TIN是通过离散的数据点生成连续的三角面来逼近真实的地形表面。由于Delaunay三角网具有空外接圆及最大化最小角的良好性质，被公认为是TIN最优的表达，它数据结构简单，能够对特殊地形进行灵活处理，受到了广泛应用，本软件采用Delaunay三角网对塔基地形离散数据进行DEM重构。

一个三角形只有符合以下两条基本准则才可称为Delaunay三角，准则1：任意一个三角形的外接圆内部不包含其他任何点；准则2：在所有可能形成的三角网中Delaunay三角的最小角度最大。

Delaunay三角网生成算法中比较常用的有三角网生长算法、分治算法、逐点插入算法等。由于塔基地形的数据量较小（一般不超过7000个点），处理时间均较为快速，本软件进一步研究提升Delaunay三角网生成效率意义并不大，采用经典的三角网生长算法可以满足用户要求。

三角网生长算法的基本描述如下：

（1）在离散点序列中任意取一初始点，在剩余点中找出与其相距最近的点，以这两点构建矢量化的初始基线；（2）在初始向量基线的右侧找出与该基线构成Delaunay三角形的第三点，把该点与原来两点连接形成初始化Delaunay三角形，以第三点与基线两端点构建两条新的基线；（3）对上述第2步进行迭代操作，直至离散点集合内所有的点和形成的基线均参与构建Delaunay三角网。

2.2 基于Delaunay三角网的任意插入点定位算法

本软件对目前较为成熟的任意点定位算法从效率和健壮性两方面进行比较，采用了高莉等人提出的插入点混合定位算法[1]，该算法利用三角形的拓扑关系，将三角形面积坐标定位算法與直线行走定位算法[2]相结合，在定位过程中可大幅缩短搜索路径，如下：

（1）计算插入点P的平面坐标并任意选择一个三角网作为当前目标三角形Ts ；（2）从目标三角形Ts开始，利用三角形面积坐标公式判断插入点P是否在首三角形Ts中，若三边面积坐标都非负，则插入点P位于三角形内，算法结束，若不在则执行步骤3；（3）利用三角形的面积坐标公式继续判断插入点P与当前目标三角形Ts的关系，若其中某一边的面积坐标为负，则以该边右侧的三角形Ti的作为当前目标三角形Ts（即Ts=Ti），执行步骤2；若某两条边的面积坐标为负则结合直线行走算法，将两边延长线交点与插入点P联接生成向量线，找出包含交点且与方向线相交的三角形并将该三角形作为当前目标三角形Ts，从该三角形出发找出向量线与其相交的边Ei，相交边Ei右侧的三角形Tj即为当前目标三角形Ts，返回步骤2。

2.3 长短腿配置算法

（1）获取待配置铁塔的各项参数；（2）根据铁塔根开和位移数值确定各接腿中心位置并利用2.2章节算法计算各接腿中心的地面高程点；（3）取各接腿地面高程点最小值为基准值，计算其他接腿中心高程与基准值之差，如果差值小于设置阈值，则该接腿配置满足要求，否则按照减腿级差调整长短腿至满足要求，当最短接腿仍不能满足要求时，自动降基；（4）当接腿值发生变化时，对应的基础根开也将发生变化，此时重复第2、3步至各接腿均满足配置要求；

3 程序实现及效率对比

本软件在设计上既注重执行效率和稳健性，又充分考虑到了用户的使用习惯，能够实现与AutoCAD的交互通信进行草图的自动绘制，也可输出Excel格式的配置成果。

通过对代表性工程进行测试，可以测算采用软件自动配腿的效率是人工作业效率的36倍之多，使用软件后该道设计工序耗时几乎可以忽略不计，极大提升了设计效率。

本软件运用了多专业交叉互补的优势解决了工程实际问题，利用了测量专业的数据处理方法提升了作业效率，具有良好的借鉴意义。

参考文献：

[1]高莉.改进的Delaunay三角剖分算法研究[J].兰州交通大学硕士学位论文，2015.

[2]张咏，刘长星，杨瑜华等.基于融合算法的二维Delaunay三角网任意点定位研究[J].测绘科学，2010，2（35）：84-87.

作者简介：何雄（1988-），男，湖北广水人，本科，工程师，研究方向：架空输电线路勘测设计。