23
TIN的生成算法研究（续）
2.1.3.2 逐点插入法
定义一个包含所有数据点的初始多边形，外包络多边形;
从离散数据集中任意的选择一个点P，插入到初始多边 形中，将初始多边形的各顶点与该点相连接，建立初始 的三角网； 按以下步骤进行迭代计算，直到所有的离散数据点都插 入到三角网中：
变换结果1
通过量测沟谷网长度，计算得到沟谷切割密度图：
13
变换结果2
根据单位面积上的沟源数分级变换为谷源密度图：
14
4.3.5 变换为质量形式
用新的质量特征的表现形式，代替原地图上包含数 量特征的地图表象。 依据带有数量指标的地图进行区划，例如，根据坡 度图、切割程度图、形态示量图和其它有关地图进 行地貌区划；根据雨量、温度、光照等条件地图 (带有数量指标)进行气候区划；根据土壤肥力、土 地评级、农作物播种面积以及气候、供水等条件进 行农业区划，都是把许多的数量指标转化为区划 这—质量形式。
35
由TIN到等值线生成算法（续）
3.3 等值点的游走 对每条等值线值Zc,等值线的游走可按如下3个步骤进行：
一是边界约束条件，指数据点被一多边形包围，该多边形即为边界约 束条件; 另一为内部约束条件，是数据点之间存在的限制条件。
带约束条件的Delauny TIN称为CDT(Constrained Delauny triangulation缩写为CDT)。
30
31
TIN的生成算法研究（续）
CDT三角网具有下述性质: (l)通视性：若两点的连线不与约束条件中的边相交， 则称两点是可见的； (2)空外接圆性质：如果组成三角形t的三条边不是约束 边，则t为Delaunay三角形，当且仅当过t三顶点是相 互可见的。 (3)最大最小角性质：若某条边不属于约束边，则该边 的左右三角形构成一个凸四边形后，其最小内角达到最 大。 (4)局部优化性质：对T中任一三角形t，如果三边均不 在约束边中，则t一定满足空外接圆性质或最大最小角 性质。
18
TIN的生成算法研究（续）
二、TIN的三角化方法对比
19
TIN的生成算法研究（续）
2.1 Delaunay三角剖分法 2.1.1 Delaunay三角网 空外接圆性质:在由点集v所形成的Delaunay三角网中，任 一三角形的外接圆均不包含点集V中的其他点； 最大最小角性质:在点集v可能形成的所有三角网中， Delaunay三角网中三角形的最小角度是最大的。
32
由TIN到等值线生成算法
三、由TIN生成等值线的算法 在一个三角形中如果某边上存在等值 点A,那么必然在另两条边上还存在一 个等值点B或C。这就是说对于一给定 值Zc,在一个三角形内要么等值线为0 条,要么有1条等值线通过,只要等值线 从三角形的一边进入,那么它必然会从 另外两条边中的一条游出并进入到另 一个三角形中,按此性质追踪,只有当等 值线闭合或已达到三角形网格的边界 才会停止。这个性质可确保等值线在 三角形网格中游走时不会出现半途中 止的情况,保证游走算法正确。
21
TIN的生成算法研究（续）
2.1.3 Delaunay三角剖分算法
Delaunay三角网可以最大限度地避免狭长三角 形的出现并且可以不管从何处开始都能保持三角 形网络的唯一性，被广泛的应用于数字地面模型 建立、空间邻近分析、数字地图自动综合、地学 分析以及有限元分析等领域。根据Delaunay三 角网的最大最小角或外接空圆的特性，己经出现 了许多三角剖分算法，根据其实现过程主要分为 三角网生长法、逐点插入法和分割一合并算法。
26
TIN的生成算法研究（续）
2.1.3.3.1 四叉树分割方法
平面的四叉树划分是一种常用的索引结构，四叉树索引由一系 列正方形块组成树形结构，规定每个叶子节点中所能包含的样 本点的数目上限为np。根据地形采样点的分布特征，与其他网 格索引相比，它对不均匀分布的平面数据具有较强的自适应能 力。建立四叉树时，将样本点按照其坐标值逐个加入到所属的 叶子节点t中，如果t中的点多于np个，则将t均匀分割成4个子 块，并将t中的点加入其子块中。算法速度受离散点分割算法、 三角网合并算法的影响。
27
TIN的生成算法研究（续）
三角网的合并算法
将分割数据域的三角网合并成整个离散点集的完整Delaunay三角网需要 考虑两个问题，
其一、分割数据域按照什么样的顺序进行合并; 其二、两个分割数据域如何进行合并。
可采用先进先出的队列方式生成四叉树，使叶结点不同层按其四叉树的层 次由浅到深排列，同层按逆时针顺序排列，层次最深的叶结点存储于队列 最末尾位臵。每次合并时只需取最后四个结点，依次进行合并，生成新数 据域;将原标志位去除最末两位得到新的合并数据域对应结点标志，然后可 以根据新结点标志从队尾向前搜索，插入相应位臵。依次合并完队列中所 有结点，得到最终三角网。这样就实现了以层次遍历的顺序合并各个结点。 其次，两个四叉树结点数据区域中的三角网进行合并，显然是对其两个三 角网的外边界即凸壳上点进行连接，又由于在实际合并过程中，有可能某 个四叉树结点数据区域中的点可能少于3个或位于同一条直线上，不能构 成三角网，所以结点间的三角网合并，可以分为点和凸壳的合并和凸壳的 两两合并两种情况。
(2)最大最小角准则:在TIN中的 两个相邻三角形形成的凸四边形 中，这两个三角形中的最小内角 一定大于交换凸四边形对角线后 所形成的两三角形的最小内角；
(3)最短距离和准则:最短距离和 就是指一点到基边两端的距离和 为最小；
17
TIN的生成算法研究（续）
(4)张角最大准则:一点到基 边的张角为最大； (5)面积比准则:三角形内切 圆面积与三角形面积或三角 形面积与周长平方之比最小; (6)对角线准则:两三角形组 成的凸四边形的两条对角线 之比，比值限定值须给定， 即当计算值超过限定值才进 行优化。
3.2等值点计算
等值点就是等值线与三角形边的交点,等值点的计算就是求出等 值点在三角形上的具体位臵。判断一条边上是否存在等值点,可 用f=(zi-zc)*(zj-zc)算式。其中zi,zj为边两端点pi,pj的要素 值,zc为等值线值。当f<0时,pipj边上存在唯一等值点,此时利 用线性内插可求出等值点的坐标;当j>0时,pipj边上没有等值点; 当f=0时,等值点在pi或pj上,这时容易引起等值点游走的困难,因 此在寻找zc等值点之前,需要对所有等于zc的三角形顶点的值进 行微小的改动。下面是等值点的计算公式：
地图分析的图形变换
季民
1
主要内容
地图表象图形变换的类型 地图表象的量度变换 地图表象的结构变换 不同表示方法的地图表象变换
2
4.1 地图表象图形变换的类型
根据地图实现的涉及地图内容基本要素的变换是多种多样的。它 们可以归纳为三类，即量度变换、结构交换和表象方法交换。
3
4.2 地图表象的量度变换
33
由TIN到等值线生成算法（续）
3.1 等值线起点的搜寻
三角形等值线游走的起始点 存在两种情况:
起始点在整个三角形网格的 凸边上,此时等值线游走后必 定会在网格的另一凸边游出。 起始点在网格内三角形的一 条边上,此时等值线游走后必 定会回到原来的三角形上形 成闭合等值线。
34
由TIN到等值线生成算法（续）
10
变换结果
通过变换，可以把河 系的形态、大小及其 它特征方面的一些数 量关系表现出来，如 上图四级河流的规律 大致为2的指数关系， 支流的长度也按照一 定的几何级数变化等。
11
4.3.4 变换为数量形式
即把被研究现象的质量特征变换为数量形式的 地图表象，如下图所示的谷源及沟谷平面图：算法研究（续）
2.1.3.1 三角网生长法
先在点集中任取一点，找到与其相距最短的点连接成为三 角网的一条边，然后按Delaunay三角网的判别法(最大 最小角或者外接空圆)则找出包含此边的Delaunay三角 形的另一个端点，依次处理所有新生成的边，直至所有的 边找不到能形成合理Delaunay三角形的端点。
20
TIN的生成算法研究（续）
2.1.2 Voronoi图
Voronoi图是通过切 分一个中心点和它周 围点之间的连线来定 义的。切分线和连线 之间互相垂直。当对 整个区域中的所有点 都应用这种方法时， 整个区域就会被相邻 的多边形所覆盖。
Delaunay三角网是 Voronoi图的对偶。
三角网生长算法思路简单、清晰，但实现效率不高。算法 的主要计算在于寻找满足D一三角网判别法则的第三点上。 所以各种不同的实现方法多在搜寻“第三点”上做文章。 建立数据栅格索引，对数据进行分块排序，改进点的搜索 方法，减少点的搜索时间。有的研究者提出了闭合点的概 念，对三角网增长算法作出了一些改进，较大地减少了搜 索时间。
一、量度变换形式
1、扩大量度表的等级 （如：文化程度划分） 2、从绝对指标变换为相对指标或相反
3、改变计量单位
二、区域形状度量变换
指的是区域范围大小及轮廓形状的变换，但不 改变区域间的拓扑关系，也称拓扑地图、变体 地图、或变态地图
4
5
4.3 地图表象的结构变换
4.3.1 截断法 面状地理要素的剥离截断：就是将某一成分从原地理要素中剥 离出来，将其变换成显而易见的形式。
28
TIN的生成算法研究（续）
29
TIN的生成算法研究（续）
2.1.3.4
带约束条件的不规则三角网构造算法 地学领域中大量的离散数据不是相互独立的，它们之间存在着一定
的相互约束关系，比如地表的山脊线、山谷线、断裂线等，构建三 角网，如果三角网中没有带约束数据，则生成的数字地面模型是不 能正确地表达地表的复杂关系，也不能满足实际应用的需要。 TIN的原始数据根据点之间的约束条件可分为无约束数据域和约束 数据域两种类型。空间数据点分布完全呈离散状态，数据点之间在 物理上互相独立，数据点之间不存在任何关系，即为无约束数据域。 而部分数据点存在某种联系的数据区域我们称之为约束数据域，这 种联系一般通过线性特征来维护，约束条件又有两类: