改進的Delaunay三角網(wǎng)在風電廠地形三維表面重建中的應用

劉洪華，鄧學飛，楊大哲

（1.中國能源建設(shè)集團山西省電力勘測設(shè)計院有限公司，山西 太原 030001；2.國網(wǎng)山西省電力公司，山西 太原 030001；3.國網(wǎng)山西省電力公司電力科學研究院，山西 太原 030001）

改進的Delaunay三角網(wǎng)在風電廠地形三維表面重建中的應用

劉洪華1，鄧學飛2，楊大哲3

（1.中國能源建設(shè)集團山西省電力勘測設(shè)計院有限公司，山西 太原 030001；2.國網(wǎng)山西省電力公司，山西 太原 030001；3.國網(wǎng)山西省電力公司電力科學研究院，山西 太原 030001）

提出了一種基于等高線的三維地形重建算法，通過等高線數(shù)字化獲取離散點的三維數(shù)據(jù)，根據(jù)等高線點的三維密度確定離散點的D e la un a y密度值，采用D e la un a y三角網(wǎng)結(jié)合離散點的高程值進行三維建模，并計算出每一個內(nèi)點的坐標及高程，然后在PDM S（工廠三維布置設(shè)計管理系統(tǒng)）中進行地形的三維重建，實驗證明所述方法速度快，精度高。

等高線；三維地形；D e la unn a y三角網(wǎng)

0 引言

等高線地形圖是表示三維地形的重要工具，但等高線地形圖不直觀形象，不利于非專業(yè)人員的理解。近年來，三維地形重建逐漸成為計算機圖形學領(lǐng)域的熱點，相對于傳統(tǒng)的AutoCAD等高線地形圖，基于等高線數(shù)據(jù)構(gòu)造的三維地形圖可視化程度高、擬合局部地貌特征細膩，保證了最大限度的幾何精度，可以滿足實際需要。Delaunay三角剖分是地形三維繪制中常用的三角剖分方法，文獻[1]中采用了基于Delaunay三角剖分和高斯小波函數(shù)插值構(gòu)建了三維表面，文獻[2]中基于等高線地形圖利用梯度插值的最小二乘方法模擬了三維地形。如果既要滿足三維地形的模擬，又要滿足地形表面的局部細節(jié)的顯示，就需要將這兩種方法結(jié)合起來，用離散點的三維密度確定離散點的Delaunay密度值，然后用Delaunay三角剖分方法進行三維地形模擬，這樣能夠最大限度地利用等高線地形圖的數(shù)據(jù)，減少數(shù)據(jù)失真，優(yōu)化三角形數(shù)量，更好地體現(xiàn)地形的局部細節(jié)。

1 基于等高線的三維地形構(gòu)造

1.1 得到等高線數(shù)據(jù)集

AutoCAD等高線地形圖使用數(shù)字高程模型DEM(DigitalElevation Model)表達。DEM數(shù)據(jù)是區(qū)域D上一系列離散的測繪數(shù)據(jù)點組成的三維向量點集，用區(qū)域D上地形的三維向量的有限序列｛Vj= ｛（xi， yi，zi），i=1，2，…，n}，j=1，2，…，n }表示，其中 （xi， yi）∈D是平面坐標，zi是平面坐標對應的高程，Vj表示第j條等高線上離散點的集合。該數(shù)據(jù)點集可以通過對AutoCAD等高線數(shù)據(jù)的處理得到，從而構(gòu)成一個完整的數(shù)據(jù)集。

1.2 等高線地形圖的三維建模

AutoCAD等高線地形圖中的數(shù)據(jù)是離散的數(shù)據(jù)點集，需要建立合適的三維模型，從數(shù)據(jù)點集中生成三維地形圖。但實際測繪點的位置與實際地形有關(guān)，通常點的位置和密度不能滿足三維模型需要，點集中各向量的點不成規(guī)則網(wǎng)格排列，這就需要用數(shù)據(jù)內(nèi)插值以生成更多的點。

Delaunay三角剖分的空圓特性和最大最小角特性確保了生成的三角形盡量均勻，避免了狹長三角形的出現(xiàn)，更加符合實際地形特征。所以在地形擬合方面采用Delaunay三角剖分來構(gòu)建三角網(wǎng)。參考文獻[1]中將離散點的三維坐標投影到z=0平面，然后對投影的值進行限制性的Delaunay三角化（CDT）剖分，但是不能夠很好地反映在z軸上的落差，例如地形圖中的陡坡上過于狹長的Delaunay三角形，在二維平面中的投影可能就符合Delaunay三角網(wǎng)檢查條件。為了彌補這一缺點，需要將Delaunay三角剖分與地形圖上的z軸坐標相結(jié)合進行改進。

本算法依據(jù)Delaunay三角形的性質(zhì)，先根據(jù)離散點的密度確定等高線上離散點的Delaunay密度值，再插入等高線上離散點，最后用改進的Delaunay三角剖分方法插入離散點，同時計算插入點的密度。

1.2.1 計算點的密度函數(shù)

1.2.2 規(guī)格化網(wǎng)格插值

三維空間數(shù)據(jù)點集進行Delaunay三角剖分時，需要計算插入點的高程值，可以取離這個點最近已知高程的3個點（xi，yi，zi），（xj，yj，zj） ，（xk，yk，zk）做插值計算，將（x，y）代入公式

最后求出的值為插入點的高程值。

1.2.3 計算插入點的坐標

由于地形中離散點含高程值，在插入點的坐標計算時需要對Delaunay三角剖分算法進行改進。設(shè)CDTT（V，L），V為點集，L為約束邊的集合。

引入約束邊后的CDT空外接圓性質(zhì)和最大最小角性質(zhì)可表述如下。

a）空外接圓性質(zhì)的改進：在將三維空間上與t的3個頂點通視的點沿中間的邊旋轉(zhuǎn)到所在的平面后，三角形仍然滿足空外接圓性質(zhì)，即T（V，L）中任何一個三角形的外接圓內(nèi)不包含V中與t的3個頂點通視的點。圖1a表示三維空間中2個相鄰三角形，在將其中的一個三角形旋轉(zhuǎn)到另一個三角形所在平面后，滿足空外接圓性質(zhì)（見圖1b）。

b）最大最小角性質(zhì)：設(shè)t1和t2為T（V，L）中的三角形，且具有公共邊e，如果t1和t2構(gòu)成一個凸四邊形，并且e∈L，那么交換凸四邊形的對角線，t1和t2的最小內(nèi)角不會增大。圖1c為三維空間中2個三角形，最小內(nèi)角為30°，在將公共邊對換后，最小內(nèi)角增加（見圖1d）。

c）通視性：是指將三角形投影到z=0平面，設(shè)p1，p2，p3∈V，如圖2，若p1與p2的連線不與L的約束邊相交，則稱p1與p2不通視，p3與p4相互通視。

圖1 空外接圓性質(zhì)和最大最小角性質(zhì)示意圖

圖2 通視性示意圖

2 應用實例

以某風電場F06風機AutoCAD地形圖為例，見圖3。

2.1 計算方法

首先導出AutoCAD（圖3）圖紙中的地形數(shù)據(jù)，根據(jù)地形數(shù)據(jù)確定等高線上點的密度函數(shù)，以等高線為初始數(shù)據(jù)，插入等高線上的點，然后利用Delaunay三角剖分規(guī)范化網(wǎng)格。這里采用逐步插入的Lawson算法，通過Java語言編程實現(xiàn)。

第一步，生成大的三角形，將所有數(shù)據(jù)點包圍起來，放入三角形鏈表。

第二步，以等高線為初始數(shù)據(jù)，將等高線上的散點依次插入，在三角形鏈表中找出其外接圓包含插入點的三角形（稱為該點的影響三角形），刪除影響三角形的公共邊，將插入點同影響三角形的全部頂點連接起來，從而完成一個點在Delaunay三角形鏈表中的插入。

圖3 風機地形圖

第三步，根據(jù)改進的Delaunay三角剖分方法，逐個對它們進行空外接圓檢測，用局部優(yōu)化過程進行優(yōu)化，即通過交換對角線的方法來保證所形成的三角網(wǎng)為Delaunay三角網(wǎng)，直到所有的點插入完畢。

第四步，根據(jù)點的密度函數(shù)確定需要插入邊界上的點，按照第三步的方法進行插入并優(yōu)化。

第五步，根據(jù)密度函數(shù)確定內(nèi)部需要插入的點，按照第三步的方法進行插入并優(yōu)化，直到所有的三角形滿足外接圓檢測和密度函數(shù)要求。

根據(jù)得到的數(shù)據(jù)，在AVEVA公司的工廠三維設(shè)計管理系統(tǒng)（PDMS）中繪制三維地形圖。地形圖效果見圖4、圖5。

圖4 三維地形俯視圖

圖5 三維地形側(cè)面圖

2.2 結(jié)果分析

改進的Delaunay三角剖分方法應用效果較好、精度較高。圖4中在平面投影為狹長的三角形表示坡度變化大的陡坡或劇烈變化的地形，稠密的三角形表示密度函數(shù)較小的峰谷，與圖5和圖3吻合，這些三角形在三維空間中均滿足1.2.3中改進的空外接圓性質(zhì)，使網(wǎng)格最大限度地反映實際地形。

3 結(jié)束語

本文用AutoCAD等高線地形圖生成三維地形圖，改進了與高程數(shù)據(jù)相關(guān)的Delaunay三角網(wǎng)格剖分地形的模擬方法。實驗表明，改進的方法能夠充分利用等高線地理信息，能夠根據(jù)地形變化程度分配三角形的密度，生成的三維地形表面三角網(wǎng)格更加均勻，能夠較好地模擬地形表面的局部細節(jié)，三維地形圖更加真實細膩，同時由于三角形數(shù)量的減少也提高了PDMS等模型的顯示速度。

由于同一條等高線上離散點用直線連接，實際地形圖的繪制中用三次樣條函數(shù)插值算法生成的模型更接近于實際，這時可以先對地形圖進行三次樣條函數(shù)插值計算，在插入邊界點的時候可以在三次樣條函數(shù)上進行取值，然后進行Delaunay三角網(wǎng)格剖分。

[1]劉家勝，鄒道文,周源華，等.基于Delaunay三角剖分和高斯小波函數(shù)插值的三維表面重建算法[J].計算機工程與應用，2003（23）：76-78.

[2]王仁坤，閆紅菱.建立三維地形模型的方法研究[J].水利水電科技進展，1996,16（6）：25-27.

The Application of Improved Delaunay Triangulation on the Reconstruction of Threedimensional Surface ofW ind Farm Terrain

LIU Honghua1，DENG Xuefei2，YANG Dazhe3
（State Grid Taiyuan Power Supply Company，Taiyuan，Shanxi 030009，China）

This paper introduces contour-based three-dimensional terrain reconstruction algorithm.The three-dimensional data of discrete points are obtained by digitized contour lines.Delaunay density of discrete points is determined by the density of three-dimensional of contour line points.Three-dimensionalmodel is established by using Delaunay triangulation with the height of discrete points,and then the coordinatesand heightofeach interior pointare then calculated.The three-dimensional terrain reconstruction is carried out in PDMS（Plant Design Management System），through which themethod described in this article has been proved to be efficientand precise.

contour line；three-dimensional terrain；Delaunay trianglenet

P208

A

1671-0320（2015）05-0045-03

2015-06-10，

2015-07-23

劉洪華（1981），女，山東濟南人，2007年畢業(yè)于山東大學計算數(shù)學專業(yè)，碩士，工程師，從事電力信息化工作；

鄧學飛（1981），男，山東賓州人，2006年畢業(yè)于山東大學計算數(shù)學專業(yè)，碩士，工程師，從事電力管理與秘書工作；

楊大哲（1983），男，河南南陽人，2009年畢業(yè)于山東大學熱能工程專業(yè)，碩士，工程師，從事電力信息安全工作。