带有边界条件的Delaunay三角网生成算法的研究与实现

宁化展,徐炳喜,田茂义,张 丽

(1.山东科技大学测绘科学与工程学院,山东青岛266510;2.中煤矿山建设集团有限责任公司,合肥安徽230601;2.峡山生态经济发展区太保庄街道水利站,山东潍坊261325)

0 引 言

数字地形模型(Digital Terrain Model,DTM)是以离散分布的平面点来模拟连续分布的地形,是野外地表勘测成果的数字化展现,广泛的应用于地理信息系统各领域中。

Delaunay三角网是DTM的主要实现形式,用一系列互不交叉、重叠的连接在一起的三角形网来表示地形。Delaunay三角网具有很好的特性:构建结果的唯一性;每个三角形的外接圆不包含其它点,即所有样本点都是与其最近的两个点连接组成一个三角形;利用野外勘查测量数据作为网格节点,不改变原始数据精度,很好的展示关键地形特征[1]。

1 主要模块的生成

带有边界条件的基本三角网的生成模块[2]

1)生成凸壳模型:建立一个包含所有数据点的初始凸多边形;

2)生成初始的三角网:利用生成的凸壳;

3)局部优化:对生成的三角网利用LOP算法优化;

4)最终Delaunay三角网的生成:利用边界条件剔除多余的三角形。

2 模块的算法思路

2.1 凸壳的构造

一般的凸壳构造方法只是找到了最少点的多边形,特殊情况如:多点恰巧在凸壳的一条边上一般的算法只是找出了这条边的两端的两个点而中间的点却没找出来。这对于地质体的建模是不利的。

为此本文设计了一种“夹角与距离最小”的查找凸壳算法[3],下面以图1为例说明凸壳的产生过程(涉及到的坐标以平面二维坐标系为例)。

图1 离散点集

第1步:首先定义一个泛型数组用来存放边界点在初始离散点集数组中的索引值;

第2步:在存放离散点集的数组中找出Y值最小的点(p8)的位置索引值,将此索引值存入定义的泛型数组,求出p8与离散点集中其它点组成的所有向量与x轴的夹角,以夹角最小和距p8的距离最小为条件筛选出下一个点(p10)的位置索引值并添加到定义的泛型数组;

第3步:求出第2步里找出的点p10(泛型数组里的最后一个点)与离散点集数组里其它点(p8、p10除外)组成的所有向量与向量p8p10(即是:泛型数组里倒数第二个点与倒数第一个点构成的向量)的夹角,以夹角最小和距点p10(泛型数组里最后一个点)的距离最小为条件筛选出下一个点(p12),根据在离散点集数组里的位置索引值并添加到定义的泛型数组;

第4步:重复循环第3步,直到筛选出的索引值为第二步找出的Y值最小点的索引值时退出循环。

2.2 三角网的构造及优化

根据前一部分生成的凸壳多边形利用逐点插入法[4]生成三角网,如图2所示。

1)在初始多边形中建立一个最大三角形,其构造方法为,找出离散数据的x,y最大、最小值,形成一个矩形,做出该矩形的外接圆,然后做出该外接圆的等边三角形;然后迭代以下步骤,直至所有点被处理;

2)插入一个数据点P,在三角网中找出包含P的三角形t,把P与t的三个顶点相连,生成三个新的三角形;

3)利用Lop算法优化三角网。

图2 逐点插入法示意图

局部优化算法[5](Local Optimization Procedure,Lop)是为了生成Delaunay三角网。算法的基本含义:对由两个公共边组成的四边形进行判断,如果其中一个三角形的外接圆包含第四个顶点,则这个四边形的对角线互换,如图3所示。

2.3 三角形的剔除

目前有些文献提出了处理凹形区域的算法,但仍先假设制图区域为凸形的,待联网结束后去掉那些三角形三点都为边界点的三角形。通过研究发现,此算法是具有局限性的,它可能去掉那些合法的三角形(图4中的三角形ABC)。为此设计了一种新的算法用以处理这种会剔除合理三角形的情况。(图5中的三角形ABC不会被剔除,三角形BCD会被剔除)

图3 Lop算法示意图

图4 三角形剔除示意图

算法描述如下:

1)判断三角形的三个顶点是否位于边界上。

2)如果均位于边界上,求出其内切圆的圆心,判断该圆心是否位于边界内[6],如果圆心位于边界内,三角形保留,否则剔除。

图5 三角形剔除示意图二

3 程序的实现

此算法已经用java语言实现,经多次测试(测试方法:把要测试的离散点以及边界点坐标＜x,y,z＞放到或从存放数据的txt、excel文档中读到定义好的数组里,然后调用定义好的方法即可。注意:数组里先存放边界点的坐标后面存放其它的离散点坐标),此算法是有效的。下图为用特殊(边界上的点有多点在一条边上的)的一些点测试,生成的凸壳边界(图6),无边界条件的Delaunay三角网(见图7),有边界条件生成的Delaunay三角网(见图8)。

4 结 论

在Delaunay三角网生成算法的基础上,研究了带有边界约束条件的Delaunay三角网的构建,并对查找“凸壳”的算法进行了改进,改进后的算法对凸壳的查找更简单更全面。目前对于大区域内带有小区域漏洞的Delaunay三角网构建还不能实现,将在后续的学习研究中实现这类Delaunay三角网的构建。

[1] 刘永和,王润怀,齐永安.一种非凸包边界约束不规则三角网生成算法[J].测绘科学,2008,33(3):79-81.

[2] 吴燕来,朱 莉.Delaunay三角网生成算法的研究与实现[J].计算机与信息技术,2007,31(4):21-22.

[3] 陈 涛,李光耀.平面离散点集的边界搜索算法[J].计算机仿真,2004,21(3):21-23.

[4] 徐道柱,刘海砚.大量约束边界条件下Delaunay三角网的快速生成[J].测绘工程,2007,16(3):6-10.

[5] 袁 翰,李伟波,陈婷婷.对构建Delaunay三角网中凸壳算法的研究与改进[J].计算机工程,2007,33(7):70-72.

[6] 孙家广.计算机图形学[M].北京:清华大学出版社,1995.