不规则三角网的建立与应用.doc

摘 要 作为空间数据基础设施中的“4D”产品之一和地理信息系统的核心数据库，数字高程模型（DEM）已在测绘、遥感、农林规划、城市规划、土木水利工程、地学分析等各个领域都有了广泛的应用。数字高程模型的表达方法重要有规则格网模型、不规则三角网模型和等高线模型三种，而不规则三角网(TIN)是数字高程模型中最基本和最重要的一种模型，它能以不同层次的分辨率来描述地形表面，并可以灵活的解决特殊地形。因此，围绕基于TIN 的 DEM 的构建，本文重要论述了基于 TIN 结构的数字高程模型建模原理和方法，离散点的 Delaunay 三角网生成算法，建立有约束条件的约束三角网，最后分析了建立的 TIN模型在土方计算方面的应用。 在本论文论述的过程中，针对传统算法进行了对比和分析后，在逐点插入法的基础之上，提出了一些新的细部改善的实现方法。局部优化操作和改善的算法实现使得对大容量离散点的三角网构建速度更快，效率更高；对限制条件的嵌入满足由此计算出来的土方量更接近实际盼望值。本论文中重要的研究成果和内容如下： 1）在离散点的 Delaunay 三角网生成方面，本文中在插入点算法的基础上，建立凸包和矩形包容盒，建立虚拟网格，对原始离散点进行一级格网自适应分块，并建立索引关系。在定位点所在三角形时引入快速点定位算法，简易的空外接圆及圆内测试公式，通过这些改善使得 Delaunay 三角网的剖分更加高效。 2）在约束 Delaunay 三角网理论基础之上，结合上面散点域的剖分方法，对已有的两步算法基础上改善，完毕约束 Delaunay 三角网的构建。在其过程中应用矢量点积等数学工具改善了计算中的凹凸点判断，继续采用上章的快速索引和最速定位方法，并且对约束线相切等特殊情形进行了解决，进一步完善了算法的稳健性。 3）对于在约束三角网构造基础上的 TIN 模型的应用，文中对其在土方量计算方面精度的优越性进行了分析，在可视化表达方面最后结合广东省东莞市某高尔夫球场工程给出了例证。 关键词：不规则三角网（TIN）;逐点插入法;土方计算 Abstract As one of the 4D products in spatial data infrastructure and the core database of GIS, digital elevation model (DEM)in mapping, remote sensing, agriculture, forestry planning, urban planning, civil engineering,geological analysis and other fields to have a wide range of applications. Digital elevation model has three representations that are regular square grid model, triangulated irregular network model and contour model , and TIN is the most basic and most important model, it can be described terrain surface at different levels of resolution, and can be flexible to handle special terrain.Thus, based on the DEM-based TIN construction,this paper discusses the structure of TIN-based digital elevation modeling principles and methods and the discrete points of the Delaunay Triangulation Algorithm for the establishment of a binding constraint triangulation, Finally, it analysis the establishment of TIN model in the application of earthwork calculations. In the course of this paper discusses, through the traditional method were compared and analyzed, the insertion point by point basis,put forward some new detail to improve the implementation method. Local optimized operations and improved Algorithm makes the construction of the large capacity of discrete points Triangulation faster and more efficient; on the embedded restrictions thus calculated to meet more realistic expectations of earthwork. Therefore, this thesis the main research and content as follows: 1) when create discrete points of the delauney tribulation, the paper create convex and rectangular tolerance box, a virtual grid , The original grid of discrete points of a block adaptive and index relations. When located the triangle that contains the point,it make use of the fast point location algorithm,simple empty circucircle and the circle test the formula. these improvements make the Delaunay triangulation mesh is more efficient. 2) Constrained Delaunay triangulation based on the theory of light scatter domain subdivision above method, the two-step algorithm has been improved based on the completion of construction of constrained Delaunay triangulation. Application in the process of mathematical tools such as vector dot product to improve the calculation of the rough spots to judge, to continue to use the fast indexand most quickly positioning method, and the line tangent to the constraints and other special cases were dealt with, to further improve the algorithm robustness. 3) For the triangular structure constrained on the basis of the TIN model is applied, the text of the TIN model Earthwork calculations analyzed the advantages of accuracy, the final combination of a golf course project in Dongguan City, gives an example. Keywords: TIN;Incremental Insertion; Earthwork calculation第一章 绪论 1.1 研究背景 地球是人类生活和活动的承载体。数年以来，我们为了更充足的结识自然客体和改造自然，总在不懈的努力尝试用不同的方式方法来描述、表达人所处的环境，其中地形图就是一个有代表性的测绘表述变迁的缩影。从最开始的象形符号抽象的雏形到后来的在二维介质上对三维表面进行地形写景图，地貌写景图等描述是一个进步，但写景方式不具有可量测性，所以还是很局限的。随着测绘技术发展，地形的表达也由写景式的定性表达过渡到了以等高线为主的矢量化表达。航空摄影测量，遥感技术提供的影响都在对三维现实世界的模拟。但是有一个矛盾体，那就是对于地形表面形态而言，一方面我们尽也许的从几何角度去理解和描述以解决实际应用中的可量测性；此外一个方面它自身是一种三维景观现象，对于其表述要考虑生理视觉感受，我们总是希望可以尽也许的直观形象逼真。从 20世纪四十年代开始的计算机图形学、计算机辅助制图等相关学科和理论的发展，使得在测绘领域，在图形表达表述方面发生了从模拟表达时代走向了数字表达时代，有了质的奔腾。其中地理信息系统（GIS）及数字高程模型（DEM）学科或技术显得尤为重要。 地理信息系统，简称 GIS（Geographical Information System）, 它源于 20 世纪 60 年代初期加拿大测量学家 Tomlinson 的“把地图变成数字形式的地图，以便计算机进行解决与分析”的观点，但是在技术工具解决中，则是运用计算机存贮、解决地理信息，并且在计算机软、硬件支持下，把各种资源信息和环境参数按空间分布或地理坐标，以一定的格式或者分类输入、解决、存贮、输出，用以满足其应用需要的人机交互系统。因此 GIS 的本质是在二维地理空间基础上实现对地下、地表和空中诸地理信息的数字化表达和管理。当然地理信息系统技术发展到当前，功能不再是当初的局限于查询、检索和制图，而是丰富到空间分析、建模、决策等诸多方面，在数据管理上则从简朴的栅格数据、矢量数据管理转向多元数据融合，在现实生活中应用的很活跃，也很充足。 美国 MIT 摄影测量实验室主任 Chaires.L.Miller20 世纪 50 年代在解决道路工程的计算机辅助设计问题这一课题时，初次提出数字地面模型概念。后来的发展对于其概念有如下的定义，数字地面模型(DTM，Digiatl Terrain Mode)是以数字形式存储的地球表面上所有信息的总和，是描述地面诸特性空间分布数值的集合，是地形表面形态等多种信息的一种数字表达。若只考虑 DTM 的地形分量，通常称其为数字高程模型 DEM(Digiatl Elevation Model) 。 DEM 是表达区域 D 上的三维向量有限序列，用函数的形式描述为：( , , ) 1, 2,3,i i i iv = x y z i = n其中，,i ix y是平面坐标， iz是( , )i ix y相应的高程值。当该序列中各平面向量的平面位置呈规则格网排列时，其平面坐标可省略，此时，DEM 就简化为一维向量序列【3】【4】。 从数字化表达这一意义上来讲，数字高程模型（DEM）是地理信息系统（GIS）在概念和方法上的萌芽【47】。DEM 作为地表信息的集合，自然是 GIS 空间数据库的核心和各种地学分析的基础数据，也成为 GIS 的分析对象。虽作为 GIS 的原型系统和雏形，但 DEM在 GIS 的发展中对 GIS 的数据采集、数据组织、数据分析和可视化方面的奉献却是非常大， DEM 中的许多算法和方法可以不加修改地应用到 GIS 数据解决中，DEM 不仅仅是“4D”产品之一和简朴的数据集合，更是一种地理信息数据解决的技术和方法。 数字高程模型做为一种数字表达形式，它的优越性是传统的表现方式比如等高线地形图等所无法比拟的。一方面是其数据可以直接输入计算机来应用。第二，普通的地形图表现信息相称的唯一，比如纸质的旅游图、交通图、专题图、工程施工用的地图等都是有一个方面的侧重但是不能涵盖其它数据，但是数字高程模型可以多层数据结构来存贮丰富的信息。第三是便于修改，可以及时更新，很好管理以及作为产品来输出。第四是不管时间怎么推移，精度恒定不会损失。诸如以上的优点，在我们国家的灾害防治、资源管理、环境治理、国防建设等各个与地形分析相关的领域，应用甚是广泛，已经成为当前政府决策的有效辅助工具和分析问题的手参考手段。 数字高程模型的理论和技术由数据采集、数据解决和应用三部分组成。对于其研究的内容也重要涉及以下几个方面：1）地形数据采样；2）地形建模与内插；3）数据组织与管理；4）地形分析与地学应用；5）DEM 可视化；6）不拟定分析和表达。在进行 DEM 表面建模时，根据数据类型的特定结构，大体上可以分为两种基本方法：即基于三角形的建模方法和基于格网的建模方法。通常三角形被认为是最基础的一种网络，由于它既可以适应规则分布数据，也可以适应不规则分布数据；既可以通过对三角网的内插生成规则格网网络，也可根据三角网建立连续或光滑的表面。 在数字地形建模中，不规则三角网（TIN）通过不规则分布的数据点生成的连续三角面来逼近地形表面。TIN 模型与规则格网模型相对比，能用更少的空间和时间更加精确地表达复杂表面，反映原始地形细节，并且具有地表重构精度高和对不规则分布区域数据点适应能力强的特点。构造 TIN 的过程事实上就是对离散点进行三角剖分的过程，而在其构造过程中，Delaunay 三角网是被普遍接受并广泛应用于分析研究区域离散数据的有效工具，由于二维任意域内点集的 Delaunay 三角剖分具有最小角最大的良好性质，被公认为最优的三角剖分，在科学计算可视化，有限元分析，路线选择，地学分析，地理信息系统，虚拟现实，地图综合和计算机视觉等领域有着广泛的应用。因此，对于 Delaunay 三角网算法进行进一步研究，提高算法执行的时间效率和空间复杂度，有着重要的意义。 可视化（Visualization）,作为一种技术与方法，得益于当代科技的飞速发展。可视化，计算机动画和虚拟现实技术是近年来在计算机图形学领域的三大热门研究方向，其核心都是三维真实感图形。当前，三维图形应用广泛，在三维游戏，CAD 设计及地质勘探等诸多方面都是有所体现，使得表达更加的直观和丰富。OpenGL 作为一个性能优越的图形应用程序设计界面（API），具有广泛的可移植性，它独立于硬件系统，操作系统和窗口系统。由于 OpenGL 能实现高性能的三维图形功能，使得计算可视化、仿真可视化计算发展迅速，应用广泛。1.2 国内外研究现状 长期以来，很多学者对于 Delaunay 三角网的算法进行了进一步细致的研究，使得该算法日趋成熟，研究从不同的角度来改善算法的执行效率，并且随着计算机硬件的发展，也在一定限度上加快了算法的执行速度。 在算法的改善方面，根据离散点的数据分布特性和约束条件，研究重要集中在无约束三角剖分（Delaunay triangulation,简称 DTIN）和约束三角剖分（Constrained Delaunay triangulation,简称 CDTIN）两种算法。所有的 Delaunay Trangulation 算法都是对矢量结构的三角剖分，事实上也可对栅格影象数据进行三角剖分，这就是基于数学形态学的三角剖分；同时 Delaunay Trangulation 算法也可分为间接 Delaunay 三角网算法和直接 Delaunay 三角网算法。间接 Delaunay 三角剖分算法的基本思想是先生成 Voronoi 图，再根据 Voronoi图和 Delaunay 三角网的对偶关系生成 Delaunay 三角网。而直接 Delaunay 三角剖分算法中则没有 voronoi 图的生成过程。间接 Ddaunay 算法复杂并且内存开销大且效率低下，现今很少使用。直接 Delaunay 三角网生成算法根据离散点插入方式的不同，可分为逐渐插入算法（Lawson，1977），三角网生长算法，分治算法（Lewis 和 Robinson,1978）,凸包算法等；除此之外，越来越多的研究专注于对常用算法的某些环节做的完善和改善。 （1）快速建立凸包，锁定有效数据；比较经典的有格雷厄姆扫描法（Graham,1972）、增量法、卷包裹法和分治算法等。其实一般情况下凸包顶点只是占点集的一小部分，绝大部分的点都是在凸壳内部。显然，我们可以尽也许多的去掉不在凸包上的点来缩减点集规模，以提高效率，这就是快速凸包技术【15】。由此出现了 Floyd 四边形法、余翔宇16提出的八边形法，刘广忠17基于二叉树构建凸包都是基于这样的思考。但是上述方法在计算中关键环节往往涉及到角度或者欧氏距离以及其他的类似于“前瞻回溯法”中碰到的计算问题,计算费时费力，复杂性大。郝建强18提出了运用正负划分性求平面点集凸包的算法，金文华【30】算法中也有基于点在线段左侧，右侧判断而对平面点集进行分类的考虑。 （2）改善算法的存储结构，值之更为紧凑，更有效地反映出数据之间的拓扑关系及其高效的索引建立；对于数据的自适应分块及其存储结构等也有两种思绪：第一，建立多级自适应格网。对于现实世界地形数据点来说，分布不均匀，所以有疏有密，为了更加灵活的管理这些数据，便于检索应用，多级自适应网格构造就产生了。李华蓉19、石松20等就提出了基于线性四叉树思想的算法，吕英英21则提出了基于二叉树分块方法。多级自适应网格划分使得网格宽度适应点的疏密变化，嵌套深度浅，花费空间小，划分速度快。在规定好的阈值范围类，四叉树结构等都“自下而上”合并子块，使得最后的子块包含数据链长度相称，数目匀称，但是在算法结构构建上比较复杂。第二，一级自适应网格。通俗来说就是把矩形分割成为规则的小正方形。由于图形简朴，容易存贮，在不是很极端地形条件下，这样的规则格网其实应用是更加广泛。刘少华22、夏少芳23等都提到了规则格网划分，但是计算公式推导中有错误。宋占峰【32】提出的“网格点三角形”的点定位策略已经成为共识，后来的很多研究多有对此的改善。 （3）限定插入点定位的搜索范围，减少数据的搜索量；Mucke 先于 1996 年提出了“先跳后走”（jump-and-walk）的 TIN 定位算法，下面的研究都是继承了“先跳后走”两步的思想。刘学军47按照有限元理论，运用三角形面积和拓扑关系来解决定位问题。宋占峰2527、蒲浩26提出基于重心的方向法及最速方向定位法。刘少华28的改善也是基于上面文献的基础，完善了最速方向定位算法。张咏29也提出了差不多相同的思想。 （4）经典算法的归并算法及凸壳技术的构网；武晓波12在国内较早提出了逐点插入算法和分治算法的归并算法，吴晓宇13则在此基础上进行了中间操作环节的一些改善。刘永和14提出生长算法和分治算法的组合算法，这也是一种拓展方法。基于凸壳技术的构网，其中最早的是 Tsai 于 1993 年提出了在 n 维欧拉空间中构造 Delaunay 三角形的通用算法凸包插值算法。国内学者研究有代表性的有程效军【8】，章孝灿【9】在算法中充足运用有序点子集的凸壳特性，避免了所有的交点测试。陈学工10进行了进一步地补充，提出了最优凸壳技术，三角网联结过程中参与判断的凸边的条数平均不大于 4。杜丽美11基于凸壳提出了二维离散点的三角划分新算法。宫煦利7等借鉴构造 Delaunay 三角网的生长法思想，提出了采用限制区域生长法，解决了凸包插算法中三角剖分不惟一的缺陷。 （5）约束边嵌入的算法。目前众多研究者是以“两步法”为基础框架，结合前面已经出现的其余的方法形成三个方向；第一，点插入算法。点插入算法中我们总是希望插入点尽也许的少，对本来DT的网格改变尽量小。梅承力【35】运用“圆准则”通过在特性线上添加附加点，易法令【36】算法思绪和上述一致，卢朝阳【37】提出了“对半划分增量型附加点插入算法”，简宪华【38】提出了“中点插入法”恢复约束边界。崔汉国【39】提出“三角形交点”插入算法，田峰敏【40】提出了“端点外接圆法”。李刚【41】提取新的附加点，和特性点一起进行优化进行构网。第二，递归算法。以Floriani为代表的算法核心是简朴多边形的Delaunay三角剖分，其实现过程是递归执行。宋占峰【42】依“角度最大原理”从约束线由内向外递归生成三角形。张景涛【43】提出了相同的思绪，以约束线为基边按空外接圆法则或最大最小角法则由内向外递归进行剖分。蒋红斐【44】以影响域为基础选择凸结点及其前后相邻两点构成三角形，后删除此凸点。循环判断，从外向内生成三角形。蒲浩【45】提出对于约束线的特性点和端点依LOP算法watson的数据相关三角形算法迭代先插入点，然后嵌入约束边界，嵌入算法和文献【42】相同。第三，迭代算法。Sloan运用连续对角线互换实现约束线段的嵌入，但是规定可互换对角线的四变形是严格凸的。李立新【46】基于强可互换对角线的思想进行了证明，并且提出了循环算法。章孝灿【6】则给出了对角线互换的完善证明。汤国安【47】也提出了约束边迭代互换的方法，回溯法来迭代。陈学工【48】则提出了插入点和互换边想结合的方法。钟美【49】也提出了思绪相近的方法。 1.3 论文组织结构 本文重要研究的内容是在.net 平台下基于 vc 编程环境下，实现对 Delaunay 三角网的构建及其某些应用方面的探求。这其中涉及到地理信息系统、应用数学、测绘学、计算几何和计算机图形学的相关理论知识。从基础数学理论的证明到具体思想方法通过程序的实现，这其中涉及到很多细节性的问题需要解决，有大量的工作需要完毕。本论文的组织结构如下： 第一章为绪论。重要介绍了 Delaunay 三角网对于数字地面模型建立的意义，Delaunay三角网研究背景和论文的研究现状，列出本文的组织结构。 第二章重要介绍了地理信息系统中数据模型，从宏观概念到微观概念，层层剥笋样的最后引出不规则三角网模型。并且对于其相关概念和性质进行了介绍，对于不规则三角网TIN 算法进行了分类。 第三章具体的阐述了基于无约束域离散点的不规则三角网的算法思想和优化构建实现过程。先对于 Delaunay 三角网的定义和性质及其传统经典三角网生成算法进行了描述，然后以逐点插入算法为基础，对于其中的环节进行细化和改善。对数据预解决消除冗余，插入额外极值点构建矩形包容盒为自适应分块及网格索引，再构建凸壳约束散点，避免外部三角形的剪切。采用各个网格轮流加点策略，减少插入点影响区域的扰动，构建过程中，对于三角网进行动态管理，设达成设定阈值再对于符合条件三角网建立索引，达成快速定位目的。最后给出了实例及其结论。 第四章介绍了带有约束条件的不规则三角网的生成。先介绍了约束三角网的定义，定理，性质。以“两步法”为基础，然后对于已有的点插入算法、迭代算法和递归算法三种重要算法分析，简化相交、凹凸、圆内测试公式（LOP 优化公式），以m 判断进行迭代互换，假如有相切则分割约束线，进一步完善了算法的健壮性和迭代效率，最后给出了算法分析和例证。 第五章结合工程测绘中土方量计算这一环节，对于常用的软件系统中所采用的计算方法进行了对比和精度分析，以 TIN 数字高程模型为基础进行土方量计算，最后结合广东省东莞市某高尔夫球场进行了仿真。 第六章是结论和展望。对全文的内容进行总结，指出有待于进一步研究方向和完善补充。