Digital Terrain Modeling 第５章　不规则三角网TIN的产生

Contents 5.1 Triangulated irregular network formation:Principles 5.2 Vector-based static Delaunay triangulation 5.3 Vector-based dynamic Delaunay triangulation 5.4 Constrained Delaunay triangulation 5.5 Triangulation from contour data 5.6 Delaunay triangulations via Voronoi diagrams

5.1 Triangulated irregular network formation:Principles 建立TIN的算法多种多样 Delaunay三角网或其他三角网 静态或动态方法 无约束或有约束的方法 直接或间接方法 删格法 静态式 矢量法 动态式 TIN Voronoi 图

Delaunay 三角网 The most widely used method for the construction of triangles is the Delaunay triangulation 狄洛尼三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包含其它的点

(b) Point D used to form the triangle 空圆法则 同样的点集可能生成不同的TIN (a) A set of data (b) Result 1 (c) Result 2 (d) Result 3 Delaunay三角网的 “empty circumcircle” principle A C B D A B C D (a) Circumcircle containing point D; (b) Point D used to form the triangle

“局部等角” 法则 由两相邻三角形构成的凸四边形中，交换此四边形的两条对角线，不会增加这两个三角形六个内角总和的最小值 最小角将最大化而最大角将最小化，因此又称MAX-MIN angle principle 局部最优方法LOP （Local Optimization Procedure），交换凸四边形的对角线，可获得等角性最好的三角网

LOP process for local equiangularity Maximum Minimum D C A B Maximum Minimum D C A B Before swapping the diagonal (b) After swapping the diagonal Local Optimization Procedure

5.2 Vector-based static Delaunay triangulation 考虑所有点，在构网过程中没有点的增加或删除 递归生长法 凸闭包收缩法

数据区域的最小凸多边形（凸壳） 在凸闭包中，连接任意两点的线段必须完全位于多边形内 凸闭包是数据点的自然极限边界，相当于包围数据点的最短路径 A B C D E F G H 在凸闭包中，连接任意两点的线段必须完全位于多边形内 凸闭包是数据点的自然极限边界，相当于包围数据点的最短路径 显然，凸闭包是数据集标准Delaunay三角网的一部分

The process of Delaunay triangulation (a) First triangle starting from the boundary (b) Subsequent triangles formed near the boundary 一旦提取出数据区域的凸闭包，就可以从其中的一条边开始逐层构建三角网

Delaunay triangulation starting from an imaginary boundary 随着数据点分布密度的不同，边界收缩后一个完整的区域可能会分解成若干个相互独立的子区域 当数据量较大时如何提高顶点选择的效率是该方法的关键

5.3 Vector-based dynamic Delaunay triangulation 数据逐点插入法 保证相邻的数据点渐次插入，并通过搜寻加入点的影响三角网（Influence Triangulation），现存的三角网在局部范围内得到动态更新 Dynamic Delaunay triangulation by the insertion of points into the initial coarse triangles

Boundary definition Delaunay三角形连网可以从任意虚拟边界点开始 凸多边形意味着任意线段上的所有点都将落入其中 (a) A set of random points (b) Minimum bounding rectangle (c) Imaginary boundary box Delaunay三角形连网可以从任意虚拟边界点开始 凸多边形意味着任意线段上的所有点都将落入其中

插入法生成Delaunay三角网 快速定位插入点所在的三角形 三角形分裂 三角形优化 (b) Splitting the C D p (C) C (b) Splitting the enclosing triangle (c) The “swap” operation (a) Initial triangulation

Local “面积坐标” to determine whether a point is inside a triangle 根据面积的正负来判定方向关系 For a point P inside or outside a triangle (123) to be checked, three equations can be established 如果三个面积坐标均为正，则点 p 落在三角形里面

穿行算法：三角形快速定位 从任意三角形出发，计算该点与三角形三边对应的齐次座标 如果所有的坐标均为正，则该点就落入此三角形  p S 1 2 3 从任意三角形出发，计算该点与三角形三边对应的齐次座标 如果所有的坐标均为正，则该点就落入此三角形 如果不是，则穿过坐标为负的边，并以此邻接三角形为新的重复前面的处理 穿行算法的计算效率为 Sqrt(n)， n是总的点数 可以预先存储若干种子点的三角形信息

边交换的数字准则 After a triangle is split into three triangles by a inserted point, the three exterior triangle edges need to be tested, to see if they conform to the Delaunay (空圆) condition

边交换的数字准则 如果发现另外一个点落在分裂三角形的外接圆内，则要用另外一条对角线来替换这条公共边 新的三角形外边还要记入堆栈供后续检测使用 A C B D  (b) A  D    C B (a) 边AC被BD替换 三角形ABC保持不变

5.4 约束 Delaunay 三角网 Ridge lines are the connected lines of local maxima (points) and the valley lines are the local minima These lines are so special that they should not be broken by any triangle edges

(b) A possible profile across ACB 不考虑地形特征的后果 628 677 453 531 481 490 461 B A C A B C (a) 具有山谷线的点集 (b) A possible profile across ACB 628 677 453 531 481 490 461 B A C 628 677 453 531 481 490 461 A C (c) 不考虑山谷的三角网 (d) 考虑山谷后的等高线

Special process to lines 最简单的处理方法是所谓的“加密法”，即通过加密约束线段上的数据点，将约束数据转换为普通数据 唯一的问题在于如何恰当地确定特征线上加密数据点之间的距离，一般取平均数据点间距的一半或更小即可

Special process to lines 尽管加大了数据量并改变了原始数据集，但简单易行、稳定可靠，在许多情况下可以很好地满足需要 (a) Data with a feature line (b) Point densification (c) Triangulation result

将特征线作为约束 To treat each feature line as a constraint means the predefined lines are not to be crossed by any triangle edges 这是最严密的解 带约束条件的三角网仍然满足Delaunay法则，但其局部等角特性有较小的改变

Inter-visibility of nine points and two constrained line segments 构建 CDT 的两步法 将所有数据包括约束线段上的数据点，建立标准的Delaunay三角网 嵌入线段约束，根据对角线交换法LOP调整每条线段影响区域内的所有三角形 Inter-visibility of nine points and two constrained line segments

CDT生成 插入约束线段ab 提取ab的影响多边形并把所有顶点都与a相连 进行 LOP 交换优化三角形 带约束的三角网

5.5 从等高线生成三角网 Three approaches to form triangulation from contour data : 等高线离散点直接生成TIN方法 将等高线作为特征线的方法 自动增加特征点及优化TIN的方法

简单处理的问题 出现平三角形：三角形的三个顶点落在同一等高线上 三角形的边与等高线交叉 要彻底消除以上问题，即使将等高线都作为约束处理，还要提取骨架点-线并估计高程，然后加入TIN

骨架线提取与高程估计 (a) A branch of skeleton for the valley (b) Skeleton point height estimation using circle ratios

增加骨架线后的TIN (a) 原始数据建立的TIN (b) 增加骨架线后建立的TIN

自主知识产权的DEM生产软件：TINModel 应用精度模型,制定了生产规范 应用DEM数据生产软件TINModel ，提高了生产效率，保证了数据成果质量

5.6 通过Voronoi图间接生成Delaunay三角网 (a) A set of data point (b) Voronoi diagram of the set (d) Triangulation of the set (c) Dual relationship

平面点集的Voronoi图 Voronoi图最早由俄罗斯数学家Voronoi于1908年提出，平面上一个点集P的Voronoi图是对平面的一个划分，每个分区表示一些点的轨迹，这些点到P的一个元素比到其它元素更近 每个点都有一个Thiessen 多边形或Voronoi区域（凸多边形） 所有这些Thiessen多边形的集合（没有缝隙和重叠）完整覆盖整个区域

Insertion of a point into an existing Voronoi diagram 分治算法Divided-Conquer 增长法Incremental 1 2 3 4 5 6 7 Insertion of a point into an existing Voronoi diagram

生成 Voronoi 图的删格方法 为了确定相邻点间的拓扑关系，因而只与点之间的相对距离有关，而与点之间的实际距离无直接关系 用整数形式的删格象素的行列号来定义坐标 并在此基础上计算Euclidean距离

距离变换生成 Voronoi图 距离变换还可以通过数学形态学（mathematical morphology）实现

形态变换：膨胀和腐蚀 膨胀 Dilation 与腐蚀 Erosion 二值形态学（函数值域定义在0或1）是将图形视作集合，通过集合逻辑运算（交、并和补）与集合形态变换（平移、膨胀和腐蚀），在结构元作用下转换到新的形态结构 (a) Original image A (b) 结构元 (c) A dilated by B (d) A eroded by B

Example

离散点集的三维TIN算法 表面拓扑的不确定性问题：点群与表面形态联系的内在机理，必要的约束条件及其实现

第６章　地形表面模拟中的内插技术 第７章　地形数据获取的质量控制