（5）空间分析--TIN.ppt

第四章泰森多边形分析 授课单位 天津师范大学城市与环境科学学院授课人 崔铁军 空间分析 4 1概念4 2基于矢量方式构建TIN4 3基于栅格方式构建TIN4 4约束条件的TIN生成 授课内容 1 Voronoi图给定一个二维Euclidean空间E和一个n点mi集M 那么 关联的Voronoi图为覆盖的一个凸多边形序列 V m1 V m2 V mn 其中 V mi 包括E中所有以M为中心的mi为近点的点 即 4 1泰森多边形概念 V mi p E Vj 1 j n d p mi d p mj 其中 d表示Euclidean距离 2 Thissen多边形1911年 荷兰气候学家A H Thissen应用V 图进行了大区域内的平均降水量研究 提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法 即将所有相邻气象站连成三角形 作这些三角形各边的垂直平分线 于是每个气象站周围的若干垂直平分线便围成一个多边形 并称这个多边形为Thissen多边形 4 1泰森多边形概念 根据上述定义可得到Thissen多边形的如下性质 1 在空间E上给定的n个离散点 将空间E分成n个Thissen多边形的分法是惟一的 2 Thissen多边形是凸多边形 位于Thissen多边形边上的点到其两边的离散点的距离相等 Thissen多边形内的点到相应离散点的距离最近 3 Thissen多边形的每个顶点是每个三角形的外接圆圆心 4 任意两个Thissen多边形不存在公共区域 5 由Thissen多边形获得的三角形在数据点均匀分布的情况下 可以避免产生狭长和小角度三角形 4 1泰森多边形概念 3 Delaunay三角网1934年 俄国数学家B Delaunay由V 图演化出了更易于分析应用的DelaunayTriangulation 简称Delaunay三角形 4 1泰森多边形概念 给定一个d维Euclidean空间和一个点集 那么 关联的Voronoi图 又称Thissen多边形 为覆盖的一个凸多边形序列 其中 包括中所有以中的为最近点的点 即 表示Euclidean距离 Voronoi图的几何对偶即把点联结起来而得到的邻接格网称为的Delaunay三角网 从此 V 图和Delaunay三角形就成了被普遍接受和广泛采用的分析研究区域离散数据的有力工具 4 1泰森多边形概念 Delaunay三角形具有以下性质 1 惟一性 UniqueProperty 即不论从何处开始联网 最终将得到一致的结果 2 空圆性质 EmptyCircleProperty 任何一个Delaunay三角形的外接圆内不能包含任何其他离散点 Delaunay三角形外接圆内不包含其他点的特性被用作一系列不重合的平面点建立Delaunay三角网的基本法则 称作空圆法则 它选择最邻近的点形成三角形 并使得特征线段均成为三角形的边 3 最大最小角性质 Max MinAngleProperty 即任意两个相邻的Delaunay三角形组成的凸四边形在交换对角线之后 六个内角的最小值不再增大 该性质说明三角形具有最佳形状特征 4 1泰森多边形概念 Voronoi图与Delaunay三角形相互间的几何对偶关系 Delaunay三角形与V 图以几何对偶形式而出现 其中虚线构成的多边形就是Thissen多边形 4 1泰森多边形概念 狄洛尼三角形外接圆内不包含其它的点 建立狄洛尼三角网的基本法则 称为空圆法则 狄洛尼法则 1 在三角形内 2 在三角形外 3 在三角形外接圆上 4 在外接圆外 4 1泰森多边形概念 根据随机分布的原始高程点建立连续的覆盖整个研究地区的不规则三角网 TIN 需要解决的最根本的问题就是如何确定哪三个数据点构成一个三角形 也称为自动联结三角网 对于平面上的离散数据点 将其中相近的三点构成最佳三角形 使每个数据点都成为三角形顶点 4 2基于矢量方式构建TIN 1 三角网生长法Green和Sibson 1978 首次实现了一个生成Dirichlet多边形的生长算法 Brassel和Reif 1979 稍后也发表了类似的算法 McCullagh和Ross通过把点集分块和排序改进了点搜索方法 减少了搜索时间 Maus也给出了一个非常相似的算法 三角网生长算法的基本思路是 首先找出点集中相距最短的两点连线成为一条Delaunay三角网的边 然后按Delaunay三角网的判断法则找出包含此边的Delaunay三角网的另一端点 依次处理所有新生成的边 直至最终完成 各种不同的实现方法多表现在搜寻 第三点 的方法不同 4 2基于矢量方式构建TIN 三角网生长算法的基本步骤是 1 以任一点为起始点 找出与起始点最近的数据点相互连接形成Delaunay三角形的一条边作为基线 按Delaunay三角网的判别法则 即它的两个基本性质 找出与基线构成Delaunay三角网的第三点 2 基线的两个端点与第三点相连 成为新的基线 3 迭代以上两步直至所有基线都被处理 a 形成第一个三角形 b 扩展生成第二个和第三个三角形 4 2基于矢量方式构建TIN 2逐点插入法Lawson提出用逐点插入法建立Delaunay三角网的算法思想 Lee和Schachter Bowyer Watson Sloan Macedonio和Pareschi Floriani和Puppo Tsai等人先后改进和完善了这一算法 逐点插入算法的思路非常简单 先在包含所有数据点的一个多边形中建立初始三角网 然后将余下的点逐一插入 用LOP算法确保其成为Delaunay三角网 各种实现方法的差别在于其初始多边形的不同以及建立初始三角网的方法的不同 逐点插入算法的基本步骤是 1 定义一个包含所有数据点的初始多边形 2 在初始多边形中建立初始三角网 然后按以下步骤迭代计算 直至所有数据点都被处理 第一步 插入一个数据点P 在三角网中找出包含P的三角形t 把P与t的三个顶点相连 生成三个新的三角形 第二步 用LOP算法优化三角网 4 2基于矢量方式构建TIN 3分治算法Shamos和Hoey提出了分治算法思想 并给出了一个生成V 图的分治算法 Lewis和Robinson将分治算法思想应用于生成Delaunay三角网 他们给出了一个 问题简化 算法 递归地分割点集 直至子集中只包含三个点而形成三角形 然后自下而上地逐级合并生成最终的三角网 以后Lee和Schachter又改进和完善了Lewis和Robinson的算法 分治算法的基本思路是使问题简化 把点集划分到足够小 使其易于生成三角网 然后把子集中的三角网合并生成最终的三角网 用LOP算法保证其成为Delaunay三角网 不同的实现方法可有不同的点集划分法 子三角网生成法及合并法 4 2基于矢量方式构建TIN Lee和Schachter算法的基本步骤是 把点集 以横坐标为主 纵坐标为辅按升序排序 然后递归地执行以下步骤 1 把点集分成近似相等的两个子集VL和VR 2 在VL和VR中生成三角网 3 用Lawson提出的局部优化算法LOP优化所生成的三角网 使之成为Delaunay三角网 4 找出连接VL和VR中两个凸壳的底线和顶线 5 由底线至顶线合并VL和VR中的两个三角形 4 2基于矢量方式构建TIN Lawson提出的局部优化算法LOP LocalOptimizationProcedure 即交换凸四边形的对角线 可获得等角性最好的三角网 它是所有生成Delaunay三角网算法都要用到的关键过程 理论上说 不论用何种方法生成的三角网 只要用LOP过程进行处理 就能使它变为Delaunay三角网 这样的一个过程其实很简单 它就是运用Delaunay三角网的性质对由两个有公共边三角形组成的四边形进行判断 如果其中一个三角形的外接圆包含第四个顶点 则将这个四边形的对角线交换 4 2基于矢量方式构建TIN 局部形状最优的三角网可根据最大最小角度法则建立 Lawson 1977 在由相邻三角形构成的凸四边形中 交换四边形的两条对角线 不会增加这两个三角形六个内角的最小值 六个内角中最小的最大 最优 局部最优方法 LOP 交换凸四边形的对角线 六个内角中最小的最大 得到更接近等边的三角形 等角性更好 a 新点插入 b 对角线交换 c 三角网LawsonLOP交换的完成 4 2基于矢量方式构建TIN 随着近几年计算机的存储和计算能力的提高 人们把在矢量环境中难以解决的问题转化到栅格环境中来解决 基于栅格方式的Delaunay三角形算法是严格按照Voronoi图和Thissen多边形定义来实现的 首先 根据Voronoi图的定义求取Thissen多边形 在Thissen多边形基础上构建Delaunay三角形 基本思路 首先进行矢量 栅格转换 在栅格距阵中求取Voronoi图 最后从Voronoi图中提取Delaunay三角形 4 3基于栅格方式构建TIN 1 矢量 栅格转换 4 3基于栅格方式构建TIN 2 计算Voronoi图在二值图象环境中 Voronoi图可以采用图像减薄 侵蚀 变换获取 以图2中 b 图像为例 图像取补后进行减薄运算 图3 a 直到求出Voronoi图 然后再进行栅格矢量变换 获取矢量的Voronoi图 图3 b 4 3基于栅格方式构建TIN 3 由Voronoi多边形求取Delaunay三角形根据Voronoi图与Delaunay三角形相互间的几何对偶关系 建立邻近多边形间的点的Delaunay三角形 图4求取Delaunay三角形 4 3基于栅格方式构建TIN 给定的各种点线 由离散点生成的泰森多边形 由离散点生成的Delaunay三角形 等高线补影象的骨架化 4 3基于栅格方式构建TIN 1基于矢量方式约束条件下TIN的构建Delaunay三角网建立起来 便可加入预先给定的约束线段以完成带约束条件的Delaunay三角网的构建 当新的约束线段加入时 通过搜索约束线段的相交三角网及相交点 现有的Delaunay三角网在局部范围内被更新与加密 4 4约束条件的TIN生成 多对角线交换循环算法对每一条地性线或其它约束线段检测其在基本网中是否存在 如果不存在 则使用 多对角线交换循环算法 加入网中 如果存在 则不须加入 多对角线交换循环算法 的基本思想是从起始点出发 对遇到的每条对角线的可交换性进行判断 可交换就交换 不可交换就判断下一条 到达最后一条对角线后 第一轮交换结束 然后从头再来 开始下一轮 直到将约束边嵌入为止 4 4约束条件的TIN生成 4 4约束条件的TIN生成 2基于栅格方式约束条件下TIN的构建与在矢量环境中明显不同 在栅格环境构建约束条件的TIN主要是考虑的约束条件次序 基于矢量方式约束条件下构建TIN 是先建立离散点Delaunay三角形 然后再考虑约束条件 与此相反 在栅格环境中是先考虑约束条件 然后建立三角网 核心问题是在栅格环境中如何对约束边编码 如何栅格化 矢量数据栅格化所遵循的原则与基