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-），男，湖北廣水人，本科，工程師，研究方向：架空輸電線路勘測設計。