南京大学城市与资源学系 第五章不规则三角网(TIN)的生成Voronoi图与Delaunay三角形.pdfVIP

Digital Terrain Model 第五章 不规则三角网(TIN)的生成 Voronoi 图与Delaunay三角形 城市与资源学系 陈刚 chengang_sohu@ 2004.03 第一节 不规则三角网TIN 1.1 不规则三角网的定义 • 不规则三角网（Triangulated Irregular Network，简称TIN ）。 • 对于不规则分布的高程点，可以形式化地描述为平面上的一个无序的 点集P，点集中每个点p对应于它的高程值。 • 不规则三角网是通过从不规则分布的数据点生成的连续三角面来逼近 地形表面。 chengang_sohu@ 1.2 不规则三角网的基本要求 TIN模型根据不规则分布于区域的离散点集P(实测高程点) ，将区域 划分为相连的三角面网络，它要求： (1) TIN是唯一的； (2) 三角网中的每个三角形尽量接近等边形状； (3) 保证是由最邻近的点构成的三角形，即三角形的边长之和最小。 对于点集P存在着多种三角网剖分方式，其中，Delaunay三角网在 地形拟合方面表现最为出色，因此，常被用作TIN的生成。 chengang_sohu@ 1.3 TIN 的数据存储方式 TIN的数据存储方式比格网DEM复杂，它不仅要存储每个点的高程 ，还要存储其平面坐标、节点连接的拓扑关系、三角形编号及其邻接三 角形编号等内容。 1 8 3 I Ⅶ 2 II Ⅵ Ⅷ 4 III 7 Ⅳ V 6 5 chengang_sohu@ 1.4 TIN模型的优缺点 TIN模型是一种表示数字高程模型的有效数据模型，相对于规则格网 DEM而言，它的优点包括： 大大减少了数据冗余，同时有效保持了地面的特征地形； 有利于表达特征地貌、地面细节的表达精度一般较高； 它的精度与地面实测数据的获取方法、密度以及分布特征相关； 可以方便地进行一些地形分析，如坡度坡向分析、地形通视分析、等高线自动生成 与三维显示等； 缺点有： 数据存储方式较复杂且不统一； 数据生成及维护过程复杂，需要大量的计算机资源； 算法的通用程度不高，一般依赖于数据存储结构； chengang_sohu@ 1.5 TIN模型的生成方法 利用离散点集生成TIN —— Delaunay三角网； 根据规则数据生成TIN 直接方式：直接将格网进行分解组合得到三角网； 选择VIPs方式：通过一定法则，选择表示地形曲面“重要” 的点，同时舍去那些“不 重要” 的点，从而来建立TIN模型； 根据等高线生成TIN 等高线离散化直接生成TIN 将等高线作为特征线的方法 自动增加特征点及优化TIN的方法 利用数学形态学方法生成TIN——基于栅格图像处理的方法 chengang_sohu@ 第二节 根据离散点数据生成TIN 2.1 Voronoi图、Delaunay三角网的由来 1908年，俄国学者G.Voronoi完成了一项奠基性研究，从数学上定义了每个观 测点所能代表的空间范围