不规则三角网(TIN)生成的算法
-
第五章
不规则三角网（
TIN
）生成的算法
5.1.1
递归生长法
递归生长算法的基本过程为如图
5.1.1
所示：<
/p>
2
1
3
2
1
3
（
a
）形成
第一个三角形
(b)
扩展生成第二个和第三个三角形
图
5.1.1
递归生长法构建
Delaunay
三角网
（
1
）在所
有数据中取任意一点
1
（一般从几何中心附近开始）
，查找
距离此点最近的点
2
，相连后作为初始基线
1-2
；
<
/p>
（
2
）在初始基线右边应用
Delaunay
法则搜寻第三点
3
，形成第一个
Delaunay
三角形；
（
3
）并以此三角形的两
条新边（
2-3
，
3-1
）作为新的初始基线；
（
4
）重复步骤（
2
）和（
3
）直至所有数据点处理完毕。
< br>该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域
点。一种比较简
单的搜索方法是通过计算三角形外接圆的圆心和半径来完
成对邻域点的搜索。
为减少搜索时间，
还可以预先将数据按
X
或
Y
坐标分
块并进行排
序。使用外接圆的搜索方法限定了基线的待选邻域点，因而降
低了用于搜寻
Delaunay
三角网的计算时间。
如果引入约束
线段，
则在确定
第三点时还要判断形成的三角形边是否与约束线
段交叉。
1
5.1.2
凸闭包收缩法
与递归生长法相反，凸闭包搜索法的基本思想是首先找到包含数据区
域的最
小凸多边形，并从该多边形开始从外向里逐层形成三角形网络。平
面点凸闭包的定义是包
含这些平面点的最小凸多边形。在凸闭包中，连接
任意两点的线段必须完全位于多边形内
。
凸闭包是数据点的自然极限边界，
相当于包围数据点的最短路
径。
显然，
凸闭包是数据集标准
Del
aunay
三角
网的一部分。计算凸闭包算法步骤包括：
（
1
）搜寻分别对
应
x-y
，
x+y
最大值及
x-y
，
x+y
最小值的各二个点。
这些点为凸闭包的顶点，且总是位于数据集的四个角
上，如图
5.1.2
（
a
）中的点
7
，
9
，
12
，
6
所示；
（
2
）将这些点以逆时针方向存储于循环链表中；
（<
/p>
3
）对链表中的点
I
及其后续点
J
搜索线段
IJ
及其右边的所有点，
计
算对
< br>IJ
有最大偏移量的点
K
作为<
/p>
IJ
之间新的凸闭包顶点，
如点
11
对边
7-9
。
（
4
）重复（<
/p>
2
）
-
（
3
）直至找不到新的顶点为止。
（
a
）初始边界
7
，
9
，
12
，
6<
/p>
；
（
b
）搜索凸
闭包顶点
11
，
5
，
4
；
（
c
）凸闭包
图
5.1.2
凸闭包的计算
(
引自
Tsai
，
1993)
一旦提取出数据区域的凸闭包，就可以从其中的一条边开始逐层构建
三角网，
具体算法如下：
2
(a)
第一个三角形
(b)
第一层三角形
图
5.1.3
凸闭包收缩法形成三角网
(1)
将凸多边形按逆时针顺序存入
链表结构，左下角点附近的顶点排
第一；
(2)
选择第一个点作为起点，与其
相邻点的连线作为第一条基边，如
图
5.1.3
（
a
）中的
9-5
；
(3)
从数据点中寻找与基边左最邻近的点
8
作为三角形
的顶点。这样
便形成了第一个
Delaunay
三角形；
(4)
将起点
9
与顶点
8
的连线换作基边，重复<
/p>
(3)
即可形成第二个三
角形；
(5)
重复第
(4)
步，
直到三角形的顶点为另一个边界点
11
。
这样，
借助
于一个起点
9
便形成了一层
Delaunay
三角形；
(6)
适当修改边界点序列，
依次选取前一层三角网的顶点作为新起点，
重复前面的处理，便可建立
起连续的一层一层的三角网。
该方法同样可以考虑约束线段。
但随着数据点分布密度的不同，实际
情况往往比较复杂。比如边界收缩后一个完整的区域
可能会分解成若干个
相互独立的子区域。当数据量较大时如何提高顶点选择的效率是该方
法的
关键。
5.2
数据逐点插入法
5.1
节介绍的三角网生长算法最大的问题是计算的时间复杂性，
由于每
个三角形的形成都涉及所有待处理的点，且难于通过简单的分块或排
序予
以彻底解决。数据点越多，问题越突出。本节将要介绍的数据逐点插入法
在很大程度上克服了数据选择问题。其具体算法如下（见图
5.2.1
）
：
（
1
）
首先提取整个数据区域的最小外界矩形范围，
并以此作为最简
单的凸闭包。
（
2
）
按一定规则将数据区域的矩形范围进行格网划分，
为了取得比
较理想的综合效率，
可以限定每个格网单元平均拥有的数据点
数。
（
3
）
根据数据点的（
x,y
）坐标建立分块索引
的线性链表。
（
4
）
剖分数据区域的凸闭包形成两个超三角形，
所有的数据点都一
定在这两个三角形范围内。
3
（
5
）
按照
（
3
）
建立的数据链表顺序往
（
4
< br>）
的三角形中插入数据点。
首先找到包含数据点的三角形
，
进而连接该点与三角形的三个
顶点，简单剖分该三角形为三个
新的三角形。
（
6
）
根据
Delaunay
三角形的空圆特性，
分别调整新生成的三个三
角形及其相邻的三角形。
对相邻的三角
形两两进行检测，
如果
其中一个三角形的外接圆中包含有另一个
三角形除公共顶点
外的第三个顶点，则交换公共边。
（
7
）
重复（
5
）
-
（
6
）直至所有的数据点都被插入到三角网
中。
（
a
）第一
分块数据插入后
(b)
第二分块数据插入后
(c)
全部三角形
图
5.2.1
逐点插入法构建
Delaunay
三角网
可见，由于步骤（
3
）的处理，保证相邻的数据点渐次插入，并通过搜
寻加入点的影响三角网（
Influence Triangulation
）
，现存的三角网在局部范
围内得到了动态更新。从而大大提高了寻找包含数据
点的三角形的效率。
5.3
带约束条
件的
Delaunay
三角网
当不相交的地形特征线、特殊的范围边界线等被作为预先定义的限制
条
件作用于
TIN
的生成当中时，必须考虑带约束条件的
Delaunay
三角网。
最简单的处理方法是
所谓的“加密法”
，即通过加密约束线段上的数据点，
将约束数
据转换为普通数据，
从而按标准
Delaunay
三角形剖分即可。
尽管
该方法加大了数据量并改变了
原始数据集，但由于简单易行、稳定可靠，
在许多情况下可以很好地满足需要。该方法唯
一的问题在于如何恰当地确
定特征线上加密数据点之间的距离，一般取平均数据点间距的
一半或更小
即可。以下内容主要介绍直接处理约束线段的算法。
4
5.3.1
带约束条件的
Delaunay
三角网的定义
定义
1
：
给定一个
d
维欧基里德空间
E
和一个
N
点
mi
集
M
。
那么，
关
联的
V
oronoi
图
(
又称
Thiessen
多边形
)
为覆盖
E
的一个凸多边
形序列
(V(m1
)
，
V(m2
)
，…，
V(m N))
，其中，
V(mi)
包括
E
中所有以
M
中的
mi
为最近点的点，即
V(mi)=p
∈
E
∶<
/p>
Vj
，
1
≤
j
≤
N
，
d(p
，
mi)
≤
d(p
，
mj)
，
d
表示欧
基里德距离。
Voronoi
图的几何对偶
(dual)
，
即把点
mi
联结起来而
得
到的邻接格网称为
M
的
Delauna
y
三角网。显然，
Delaunay
三
角网的元
素之并等于
M
的凸包之内部。
Delaunay
三角网自然推广到输入数据不仅包
括点集
M
，还包括不相
交叉的直线段集
L
。在计算几何里，这类问题称约
束
Delaunay
三角网（
Constrained
Delaunay
Triangles
，简称
CDT
）问题。
对地形数据来说，
L
即地形特征线段集（朱庆，陈楚江，
1998
）
。
定义
2
：令
单点集
M
和线段端点集
E
之并为
V
（
V=M
∪
E
）
，如果在
V
的每个
Delaunay
< br>三角形的外接圆范围内不包含任何与三角形的顶点均通
视的其它点，而点
Pi
与
Pj
（
Pi
，
Pj
∈
V
）当且仅当连线
PiPj
< br>不与
L
中的任
何约束线段相交叉
（除在端点处外）
时才互相通视，那么称这个
Delaunay
三角网为
V
由
L
约束的
Delaunay
三角网（朱庆，陈楚江，
1998
）
。
5.3.2
带约束条件的
Delaunay
法则
带约束条件的三角网仍然满足
Delaunay
法则，
但其局部等角特性有较
小的改变。
当需要考虑约束条件时，
可视图
有助于重新定义
Delaunay
法则
和
Lawson
LOP
交换原则。对
数据点及作为约束条件的断裂线，可视图由
互相可视的任意两点连接而成。在可视图中，
除在断裂线的端点处外，连
接线与任一断裂线都不相交
（图
5.3.1
）
。
由
此
Delaunay
法则及
Lawso
n LOP
交换可以重新定义为：
带
约束条件的
Delaunay
法则
：只
有当三角形外接圆内不包含任何其
它点，
且其三个顶点相互通视
时，
此三角形才是一个带约束条件的
Delaunay
三角形。
带约束条件的
DelaunayLawson
LOP
交换
：只有在带约束条件的
Delaunay
法则满足的条件下，由两相邻三角形组成的凸四边形的局部最佳<
/p>
对角线（
Locally Optimal
Diagonal
）才被选取。
5
图
5.3.1
9
个点与两条约束线段的通视图
(
引自
Tsai
，
1993)
5.3.3
顾及线段约束的三角网生成算法
考虑线段约束可以在形成
Delaunay
三
角形的同时进行，
如根据带约束
条件的
Delaunay
法则建立静态三角网的生长算法就是如此。
而
采用更多的
方法是在动态生成三角网的基础上，
采用两步法实现
CDT
的建立。
所谓两
步法即分以下两步完成：
（
1
）
将所有数据包括约束线段上的数据点，建立标准的
Delaunay
三角网。
（
2
）
嵌入线段约束，根据对角线交换法
LOP
调
整每条线段影响区
域内的所有三角形。
在作为约束条件的地形特征信息存在时，
当标准
Delaun
ay
三角网建立
起来后，
便可加入预先
给定的约束线段以完成带约束条件的
Delaunay
三角
网的构建。如图
5.3.2
所示，下面步骤
用于完成约束线段的插入：
（
1
）
在三角网中插入一约束线段；
（
2
）
确定边界与约束线段相交的三角形，如果两个这样的三角形有
公共边
，
则将此公共边删除，
最后形成约束线段的影响多边形；
（
3
）
将影响多边形其它各顶点与约束线段的起始节点相连；
（
4
）
应用带约束条件的
LOP
交换，
更新影响多边形内的三角网，
使
约束边成为三角网
中的一边；
（
5
）
重复步骤
1-4
，直至所有约束线段都加入
三角网中。
6
<
/p>
(a)
插入线段
ab
，
搜索其影响多边形；
（
b
）
连接节点
a
与影响
多边形的所
有顶点；
（
c
）
应用带约束条件的
Lawson LOP
交换对三角网进行优化；
（
d
< br>）
带约束线段
ab
的三角网
图
5.3.2
约束线段
ab
插入到已有
Delaun
ay
三角网的过程
(
引自
Tsai
，
1993)
5.3.4
从等高线生成三角网
等高线是一种特殊的特征线，等高线也可以作为约束线段。从等高线
生成三角网一般有三种算法：等高线离散点直接生成
TIN
方法
、将等高线
作为特征线的方法、自动增加特征点及优化
TIN<
/p>
的方法。等高线离散点直
接生成
TIN<
/p>
方法直接将等高线上的点离散化，
然后采用上面所讲的从不规
则点生成
TIN
的方法。
< br>但是由于这种算法只独立地考虑了数据中的每一个
点，而并未考虑等高线数据的特
殊结构，所以会导致很坏的结果，如出现
三角形的三个顶点都位于同一条等高线上
（即所谓的
“平三角形”
）
< br>或者三
角形某一边穿过了等高线这样的情况（图
5.3.
3
）
。这些情形按
TIN
的特性
都是不允许的。因此，在实际应用中，这种算法很少直接使用。通常将
等
高线作为特征线来构建三角网。
（
a
）
三
角形与等高线相交；
（
< br>b
）
三角形的三个顶点都位于同一条等高线上
图
5.3.3
对等高线进行不合理三角化的例子
将
等高线作为特征线生成三角网一般有两种算法：将等高线作为特征
线的方法、自动增加特
征点及优化
TIN
的方法。
7