改进的Delaunay三角网在风电厂地形三维表面重建中的应用

刘洪华，邓学飞，杨大哲

（1.中国能源建设集团山西省电力勘测设计院有限公司，山西 太原 030001；2.国网山西省电力公司，山西 太原 030001；3.国网山西省电力公司电力科学研究院，山西 太原 030001）

改进的Delaunay三角网在风电厂地形三维表面重建中的应用

刘洪华1，邓学飞2，杨大哲3

（1.中国能源建设集团山西省电力勘测设计院有限公司，山西 太原 030001；2.国网山西省电力公司，山西 太原 030001；3.国网山西省电力公司电力科学研究院，山西 太原 030001）

提出了一种基于等高线的三维地形重建算法，通过等高线数字化获取离散点的三维数据，根据等高线点的三维密度确定离散点的D e la un a y密度值，采用D e la un a y三角网结合离散点的高程值进行三维建模，并计算出每一个内点的坐标及高程，然后在PDM S（工厂三维布置设计管理系统）中进行地形的三维重建，实验证明所述方法速度快，精度高。

等高线；三维地形；D e la unn a y三角网

0 引言

等高线地形图是表示三维地形的重要工具，但等高线地形图不直观形象，不利于非专业人员的理解。近年来，三维地形重建逐渐成为计算机图形学领域的热点，相对于传统的AutoCAD等高线地形图，基于等高线数据构造的三维地形图可视化程度高、拟合局部地貌特征细腻，保证了最大限度的几何精度，可以满足实际需要。Delaunay三角剖分是地形三维绘制中常用的三角剖分方法，文献[1]中采用了基于Delaunay三角剖分和高斯小波函数插值构建了三维表面，文献[2]中基于等高线地形图利用梯度插值的最小二乘方法模拟了三维地形。如果既要满足三维地形的模拟，又要满足地形表面的局部细节的显示，就需要将这两种方法结合起来，用离散点的三维密度确定离散点的Delaunay密度值，然后用Delaunay三角剖分方法进行三维地形模拟，这样能够最大限度地利用等高线地形图的数据，减少数据失真，优化三角形数量，更好地体现地形的局部细节。

1 基于等高线的三维地形构造

1.1 得到等高线数据集

AutoCAD等高线地形图使用数字高程模型DEM(DigitalElevation Model)表达。DEM数据是区域D上一系列离散的测绘数据点组成的三维向量点集，用区域D上地形的三维向量的有限序列｛Vj= ｛（xi， yi，zi），i=1，2，…，n}，j=1，2，…，n }表示，其中 （xi， yi）∈D是平面坐标，zi是平面坐标对应的高程，Vj表示第j条等高线上离散点的集合。该数据点集可以通过对AutoCAD等高线数据的处理得到，从而构成一个完整的数据集。

1.2 等高线地形图的三维建模

AutoCAD等高线地形图中的数据是离散的数据点集，需要建立合适的三维模型，从数据点集中生成三维地形图。但实际测绘点的位置与实际地形有关，通常点的位置和密度不能满足三维模型需要，点集中各向量的点不成规则网格排列，这就需要用数据内插值以生成更多的点。

Delaunay三角剖分的空圆特性和最大最小角特性确保了生成的三角形尽量均匀，避免了狭长三角形的出现，更加符合实际地形特征。所以在地形拟合方面采用Delaunay三角剖分来构建三角网。参考文献[1]中将离散点的三维坐标投影到z=0平面，然后对投影的值进行限制性的Delaunay三角化（CDT）剖分，但是不能够很好地反映在z轴上的落差，例如地形图中的陡坡上过于狭长的Delaunay三角形，在二维平面中的投影可能就符合Delaunay三角网检查条件。为了弥补这一缺点，需要将Delaunay三角剖分与地形图上的z轴坐标相结合进行改进。

本算法依据Delaunay三角形的性质，先根据离散点的密度确定等高线上离散点的Delaunay密度值，再插入等高线上离散点，最后用改进的Delaunay三角剖分方法插入离散点，同时计算插入点的密度。

1.2.1 计算点的密度函数

1.2.2 规格化网格插值

三维空间数据点集进行Delaunay三角剖分时，需要计算插入点的高程值，可以取离这个点最近已知高程的3个点（xi，yi，zi），（xj，yj，zj） ，（xk，yk，zk）做插值计算，将（x，y）代入公式

最后求出的值为插入点的高程值。

1.2.3 计算插入点的坐标

由于地形中离散点含高程值，在插入点的坐标计算时需要对Delaunay三角剖分算法进行改进。设CDTT（V，L），V为点集，L为约束边的集合。

引入约束边后的CDT空外接圆性质和最大最小角性质可表述如下。

a）空外接圆性质的改进：在将三维空间上与t的3个顶点通视的点沿中间的边旋转到所在的平面后，三角形仍然满足空外接圆性质，即T（V，L）中任何一个三角形的外接圆内不包含V中与t的3个顶点通视的点。图1a表示三维空间中2个相邻三角形，在将其中的一个三角形旋转到另一个三角形所在平面后，满足空外接圆性质（见图1b）。

b）最大最小角性质：设t1和t2为T（V，L）中的三角形，且具有公共边e，如果t1和t2构成一个凸四边形，并且e∈L，那么交换凸四边形的对角线，t1和t2的最小内角不会增大。图1c为三维空间中2个三角形，最小内角为30°，在将公共边对换后，最小内角增加（见图1d）。

c）通视性：是指将三角形投影到z=0平面，设p1，p2，p3∈V，如图2，若p1与p2的连线不与L的约束边相交，则称p1与p2不通视，p3与p4相互通视。

图1 空外接圆性质和最大最小角性质示意图

图2 通视性示意图

2 应用实例

以某风电场F06风机AutoCAD地形图为例，见图3。

2.1 计算方法

首先导出AutoCAD（图3）图纸中的地形数据，根据地形数据确定等高线上点的密度函数，以等高线为初始数据，插入等高线上的点，然后利用Delaunay三角剖分规范化网格。这里采用逐步插入的Lawson算法，通过Java语言编程实现。

第一步，生成大的三角形，将所有数据点包围起来，放入三角形链表。

第二步，以等高线为初始数据，将等高线上的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。

图3 风机地形图

第三步，根据改进的Delaunay三角剖分方法，逐个对它们进行空外接圆检测，用局部优化过程进行优化，即通过交换对角线的方法来保证所形成的三角网为Delaunay三角网，直到所有的点插入完毕。

第四步，根据点的密度函数确定需要插入边界上的点，按照第三步的方法进行插入并优化。

第五步，根据密度函数确定内部需要插入的点，按照第三步的方法进行插入并优化，直到所有的三角形满足外接圆检测和密度函数要求。

根据得到的数据，在AVEVA公司的工厂三维设计管理系统（PDMS）中绘制三维地形图。地形图效果见图4、图5。

图4 三维地形俯视图

图5 三维地形侧面图

2.2 结果分析

改进的Delaunay三角剖分方法应用效果较好、精度较高。图4中在平面投影为狭长的三角形表示坡度变化大的陡坡或剧烈变化的地形，稠密的三角形表示密度函数较小的峰谷，与图5和图3吻合，这些三角形在三维空间中均满足1.2.3中改进的空外接圆性质，使网格最大限度地反映实际地形。

3 结束语

本文用AutoCAD等高线地形图生成三维地形图，改进了与高程数据相关的Delaunay三角网格剖分地形的模拟方法。实验表明，改进的方法能够充分利用等高线地理信息，能够根据地形变化程度分配三角形的密度，生成的三维地形表面三角网格更加均匀，能够较好地模拟地形表面的局部细节，三维地形图更加真实细腻，同时由于三角形数量的减少也提高了PDMS等模型的显示速度。

由于同一条等高线上离散点用直线连接，实际地形图的绘制中用三次样条函数插值算法生成的模型更接近于实际，这时可以先对地形图进行三次样条函数插值计算，在插入边界点的时候可以在三次样条函数上进行取值，然后进行Delaunay三角网格剖分。

[1]刘家胜，邹道文,周源华，等.基于Delaunay三角剖分和高斯小波函数插值的三维表面重建算法[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年毕业于山东大学计算数学专业，硕士，工程师，从事电力信息化工作；

邓学飞（1981），男，山东宾州人，2006年毕业于山东大学计算数学专业，硕士，工程师，从事电力管理与秘书工作；

杨大哲（1983），男，河南南阳人，2009年毕业于山东大学热能工程专业，硕士，工程师，从事电力信息安全工作。