Digital Terrain Modeling

Slides:



Advertisements
Similar presentations
加強輔導課程家長簡介會 時間: 9 月 30 日(二) 晚上 : 6:45 至 8 : 00 地點:禮堂.
Advertisements

1.2 应用举例 ( 一 ). 复习引入 B C A 1. 什么是正弦定理? 复习引入 B C A 1. 什么是正弦定理? 在一个三角形中,各边和它所对 角的正弦的比相等,即.
九十五年國文科命題知能 研習分享.
第二节人口的空间变化.
10、11.資料分析.
第一部分 微专题强化练.
欧洲西部 要点·疑点·考点 欧洲西部 1. 自然环境 位置:欧洲西半部,北临北冰洋,西临大西洋,南临地中海
2011年10月31日是一个令人警醒的日子,世界在10月31日迎来第70亿人口。当日凌晨,成为象征性的全球第70亿名成员之一的婴儿在菲律宾降生。 ?
黄金分割理论在股市中的应用 包头营业部.
初级会计实务 第八章 产品成本核算 主讲人:杨菠.
中考阅读 复习备考交流 西安铁一中分校 向连吾.
财经法规与会计职业道德 (3) 四川财经职业学院.
中央广播电视大学开放教育 成本会计(补修)期末复习
第2讲 流域的综合治理——以美国田纳西河流域为例
人教版义务教育课程标准实验教科书 小学数学四年级上册第七单元《数学广角》 合理安排时间 248.
第一课 神奇的货币 第二框 信用工具和外汇 1-2 信用工具和外汇.
金字塔原理 Pyramid Principle 职场能力差距的本质 海盈丰人力资源出品 HYF HUMAN RESOURCE PRODUCE.
-Artificial Neural Network- Hopfield Neural Network(HNN) 朝陽科技大學 資訊管理系 李麗華 教授.
崇拜即將開始,請大家安靜片刻, 預備心靈敬拜上帝。
中考语文积累 永宁县教研室 步正军 2015.9.
小学数学知识讲座 应用题.
勾股定理 说课人:钱丹.
倒装句之其他句式.
第二章 CATIA V5 草图绘制.
文化生活第三单元 中华文化和民族精神.
政治第二轮专题复习专题七 辩 证 法.
XI. Hilbert Huang Transform (HHT)
3-3 Modeling with Systems of DEs
Thinking of Instrumentation Survivability Under Severe Accident
第四章第一节 增值税法律制度2 主讲老师:梁天 经济法基础.
第 22 课 孙中山的民主追求 1 .近代变法救国主张的失败教训: “师夷之长技以制 夷”“中体西用”、兴办洋务、变法维新等的失败,使孙中山
Manifold Learning Kai Yang
Differential Equations (DE)
微積分網路教學課程 應用統計學系 周 章.
第十章 基于立体视觉的深度估计.
第二章 共轴球面系统的物像关系 Chapter 2: Object-image relations of coaxial spheric system.
Digital Terrain Modeling
创建型设计模式.
Simulated Annealing 報告者:李怡緯 OPLAB in NTUIM.
實驗室通風.
第 12 章 交流電源 …………………………………………………………… 12-1 單相電源 12-2 單相三線式 ※ 12-3 三相電源.
Depixelizing Pixel Art 像素风格画的矢量化
组合逻辑3 Combinational Logic
XBRL未來發展趨勢 2009年12月 For information on applying this template onto existing presentations, refer to the notes on slide 3 of this presentation. The Input.
3D Object Representations
Network Planning Algorithms in CATV Networks
圖表製作 集中指標 0628 統計學.
材料力学 刘鸿文主编(第5版) 高等教育出版社 教师:朱林利/赵沛,副教授, 航空航天学院 应用力学研究所
人教版数学四年级(下) 乘法分配律 单击页面即可演示.
網路遊戲版 幸福農場168號.
《2015考试说明》新增考点:“江苏省地级市名称”简析
Version Control System Based DSNs
指令篇 Draw 作圖 6-1 Lines(直線) Line by Centers(中心連線)
每周三交作业,作业成绩占总成绩的15%; 平时不定期的进行小测验,占总成绩的 15%;
3.5 Region Filling Region Filling is a process of “coloring in” a definite image area or region. 2019/4/19.
计算机问题求解 – 论题 算法方法 2016年11月28日.
01 FISHBONE DIAGRAM TARGET PART ONE PART TWO PART THREE PART FOUR
An Efficient MSB Prediction-based Method for High-capacity Reversible Data Hiding in Encrypted Images 基于有效MSB预测的加密图像大容量可逆数据隐藏方法。 本文目的: 做到既有较高的藏量(1bpp),
Q & A.
第3章 二维图形的创建 常用二维图形的创建 复杂二维图形的构建.
Efficient Query Relaxation for Complex Relationship Search on Graph Data 李舒馨
9.1.2不等式的性质 周村实验中学 许伟伟.
5. Combinational Logic Analysis
坚持,努力,机会留给有准备的人 第一章 四大金融资产总结 主讲老师:陈嫣.
美丽的旋转.
序偶及直角坐標系統.
畢氏定理(百牛大祭)的故事 張美玲 製作 資料來源:探索數學的故事(凡異出版社).
Principle and application of optical information technology
Voronoi Diagram and Delaunay Triangulation
102年人事預算編列說明 邁向頂尖大學辦公室製作.
Presentation transcript:

Digital Terrain Modeling 第5章 不规则三角网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算法 表面拓扑的不确定性问题:点群与表面形态联系的内在机理,必要的约束条件及其实现

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