下载文档原格式
不规则三角网生成算法及其应用探讨
李梅;张学雷
【期刊名称】《测绘与空间地理信息》
【年(卷),期】2010(33)2
【摘要】不规则三角网(TIN)是数字高程模型的一个重要表示方法,其传统算法一再被优化,也得到广泛地应用.本文在传统算法的基础上总结了一些改进算法,并且提出了相关的应用前景.
【总页数】4页(P44-45,48,51)
【作者】李梅;张学雷
【作者单位】郑州大学,水利与环境学院,河南,郑州,450001;郑州大学,自然资源与生态环境研究所,河南,郑州,450001;郑州大学,水利与环境学院,河南,郑州,450001;郑州大学,自然资源与生态环境研究所,河南,郑州,450001
【正文语种】中文
【中图分类】P235.1
【相关文献】
1.基于不规则三角网的分块地形网格生成算法 [J], 黄争舸;陈建军;郑耀
2.基于栅格局部细分的带约束条件的不规则三角网生成算法 [J], 崔雪森;杨胜龙;樊伟
3.基于凸包切割的不规则三角网及其邻接关系的生成算法 [J], 刘永和;刘玉芳;王燕平
4.平面离散点集的不规则三角网自动生成算法的实现研究 [J], 刘鹏;方勇;钟联炯;
马永社
5.一种非凸包边界约束不规则三角网生成算法 [J], 刘永和;王润怀;齐永安
因版权原因，仅展示原文概要，查看原文内容请购买。
基于基于不规则三角网不规则三角网不规则三角网构建构建构建的的网格生长算法刘 刚，李永树李永树，，张水舰(西南交通大学地理信息工程中心，成都 610031)摘 要：提出一种基于离散点Delaunay 三角网快速构建的网格生长算法，采用分治算法将离散点表达为唯一网格，利用稀疏矩阵完成网格数据的压缩存储，通过标识码实现有值单元格与离散点之间的高效检索，从而提高网格构建的效率。
依据有值单元格的密度获取预设正方形搜索空间，并在三角网扩展时根据需要动态建立正方形搜索空间，从而保证网格生长的准确性。
实验结果表明，该算法的时间复杂度为O (n log n )，对于少量或海量离散点均具有较好的适应性。
关键词关键词：：Delaunay 三角网；不规则三角网；离散点；正方形搜素空间；网格生长算法Grid Growing Algorithm Based onTriangular Irregular Network ConstructionLIU Gang, LI Yong-shu, ZHANG Shui-jian(Geography Information Engineering Center, Southwest Jiaotong University, Chengdu 610031, China)【Abstract 】This paper presents a grid growing algorithm for fast construction of Delaunay irregular network based on discrete point. In this algorithm, a grid is achieved to express discrete point uniquely based on the divide-and-conquer method, which is compressed storage in a sparse matrix, and an efficient retrieval method is established between value cell and discrete point by identification code, which is effectively to improve the efficiency of the construction of Triangular Irregular Network(TIN). According to the density of value cells, a default square search space is acquired, and it is allowed to create the square search space dynamically in the expansion process of TIN, which ensures the accuracy of the grid growing. Experimental results show that the time complexity of the proposed algorithm is O (n log n ), and the algorithm is available to both small and massive amount of discrete points.【Key words 】Delaunay triangular network; Triangular Irregular Network(TIN); discrete point; square search space; grid growing algorithm DOI: 10.3969/j.issn.1000-3428.2011.12.019计 算 机 工 程 Computer Engineering 第37卷 第12期V ol.37 No.12 2011年6月June 2011·软件技术与数据库软件技术与数据库·· 文章编号文章编号：：1000—3428(2011)12—0056—03 文献标识码文献标识码：：A中图分类号中图分类号：：P2091 概述不规则三角网(Triangular Irregular Network, TIN)表面建模是一种很重要的表面建模方法[1-2]。
基于VB语言的不规则三角网构建
高峰
【期刊名称】《新探索》
【年(卷),期】2017(000)006
【摘要】在GIS应用领域中,Delaunay三角网作为一种主要的数字表面模型(DTM)表示法,具有极其广泛的用途.利用VB语言对Delaunay三角网的构建问题进行了相关探讨,程序实现了基本地形图测绘的TIN构建,为快速生成等高线和数字高程模型创造了前提条件.
【总页数】4页(P37-40)
【作者】高峰
【作者单位】甘肃省水利水电勘测设计研究院,甘肃兰州730000
【正文语种】中文
【中图分类】P225
【相关文献】
1.基于多源数据的河道不规则三角网构建方法 [J], 刘兆峰;丁贤荣;程立刚
2.基于不规则三角网构建的网格生长算法 [J], 刘刚;李永树;张水舰
3.基于不规则三角网的水下地形导航数据库构建方法的优化 [J], 王立辉;高贤志;梁冰冰;余乐;祝雪芬
4.不规则三角网数字水深模型缓冲面快速构建的滚动球加速优化算法 [J], 董箭;张志衡;彭认灿;李改肖;王沫
5.基于地性线的不规则三角网优化构建算法 [J], 江帆;王志伟;朱长青;安敏
因版权原因，仅展示原文概要，查看原文内容请购买。
1 引言地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。
于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已经被普遍广泛采用。
数字高程模型即DEM（Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。
由于地理信息系统的普及，DEM作为数字地形模拟的重要成果已经成为国家空间数据基础设施（NSDI）的基本内容之一，并被纳入数字化空间框架（DGDF）进行规模化生产，已经成为独立的标准基础产品[5]。
DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。
格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。
不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。
不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。
基于三角形的表面建模可适合所有的数据结构，且三角形在形状和大小方面有很大灵活性，能很容易地融合断裂线，生成线或其他任何数据，因此基于三角形的方法在地形表面建模中得到了越来越多的注意，已经成为表面建模的主要方法之一。
VB语言简洁易学，对于学习GIS的学生来说无疑是接受很容易而且较快的一门计算机编程和开发语言，也是大多数学生最熟悉和了解的语言。
正是基于对生成不规则三角网算法的研究和满足学GIS的学生对VB 语言的喜爱和熟悉的情况下，本文就主要介绍用三角网生长算法生成不规则三角网及其在VB6.0环境下的实现。
一种生长法快速构造三角网的算法研究王会然【摘要】针对DEM制作过程中大数据量构建三角网效率问题,提出了一种多级索引支持的三角网生长算法,该算法逻辑结构简单,编程实现容易,可以验正该算法比通用软件提供的相应未优化算法速度提高很多.【期刊名称】《城市勘测》【年(卷),期】2010(000)002【总页数】4页(P146-149)【关键词】不规则三角网;Delaunay三角网;索引【作者】王会然【作者单位】河北省地矿局测绘院,河北,廊坊,065000【正文语种】中文【中图分类】P209数字高程模型(DEM)，是一种描述地形起伏的数学模型。
其可分为规则格网、不规则三角网和等高线几种类型。
规则格网具有结构简单、直观的特点，但在对复杂地形特征表达和分析方面，不规则三角网与其他两种方法相比，具有较高的精度和效率，目前Delaunay三角网是公认的最优三角网。
通过离散高程点和特征线、等高线构造生成三角网，已有许多专家进行了算法研究和改进，其方法类型主要有3类；①分而治之法(由Shamos和Hoey提出)，即对大量点分块构网，再合并成一个整体。
构网时采用局部优化(Lop)算法保证其成为Delaunay三角网。
其运算中大量使用递归，故实现起来有困难。
②数据点渐次插入算法(由Lawson提出)，其方法是先找到最外层点作多边形将所有点包括进去形成一个凸壳。
在此基础上构网，将内部点逐一加入，并采用Lop算法保证其成为Delaunay三角网，此算法简单，但效率不高。
③三角网生长算法，该方法算法简便，如果不加优化，则效率亦不高。
本文就针对生长算法，提出了一种优化算法——区域索引加正方形搜索区域的方法。
使生长法具有很高的效率。
Delaunay三角网为相互邻接不重叠的三角形的集合。
每一个三角形的外接圆内不包含其他点。
Delaunay三角形有3个相邻点连接而成，这3个相邻顶点对应的Voronoi多边形有一个公共的顶点，此顶点也是Delaunay三角形外接圆的圆心。
不规则三角网（TIN）生成的算法第五章不规则三角网（TIN）生成的算法在第四章，基于三角网和格网的建模方法使用较多，被认为是两种基本的建模方法。
三角网被视为最基本的一种网络，它既可适应规则分布数据，也可适应不规则分布数据，即可通过对三角网的内插生成规则格网网络，也可根据三角网直接建立连续或光滑表面模型。
在第四章中同时也介绍了Delaunay 三角网的基本概念及其产生原理，并将三角网构网算法归纳为两大类：即静态三角网和动态三角网。
由于增量式动态构网方法在形成Delaunay 三角网的同时具有很高的计算效率而被普遍采用。
本章主要介绍静态方法中典型的三角网生长算法和动态方法中的数据点逐点插入算法；同时，还将给出考虑地形特征线和其他约束线段的插入算法。
而其他非Delaunay 三角网算法如辐射扫描法Radial Sweep Algorigthm（Mirante & Weingarten, 1982）等本文将不再介绍。
5.1 三角网生长法5.1.1 递归生长法递归生长算法的基本过程为如图 5.1.1 所示：3 213 21（a）形成第一个三角形(b) 扩展生成第二个和第三个三角形图5.1.1 递归生长法构建 Delaunay 三角网（1）在所有数据中取任意一点1（一般从几何中心附近开始），查找1距离此点最近的点 2，相连后作为初始基线 1-2；（2）在初始基线右边应用 Delaunay 法则搜寻第三点 3，形成第一个Delaunay 三角形；（3）并以此三角形的两条新边（2-3，3-1）作为新的初始基线；（4）重复步骤（2）和（3）直至所有数据点处理完毕。
该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域点。
一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径来完成对邻域点的搜索。
为减少搜索时间，还可以预先将数据按 X 或 Y 坐标分块并进行排序。
使用外接圆的搜索方法限定了基线的待选邻域点，因而降低了用于搜寻Delaunay 三角网的计算时间。
基于三角网生长法的Delaunay三角网生成算法***************【摘要】论文简要介绍了Delaunay三角网的性质以及基本生成算法，并重点介绍了三角网生长法的基本原理和算法步骤，并通过设计合理的数据结构，对算法进行实现。
对算法进行分析并提出通过构建格网索引，进一步提高三角网生成效率。
【关键词】三角网生长法扩展TIN 格网索引1.引言数字地形模型DTM（Digital Terrain Model）是指对地形表面形态属性信息的数字表达，是带有空间位置特征和地形属性特征的数字描述[1]。
DTM是GIS的基础数据来源，可用于土地利用现状的分析、合理规划及洪水险情预报等。
DTM地形属性为高程时称为数字高程模型(DEM)。
DEM主要的三种表示模型为规则格网模型、等高线模型、不规则三角网模型（Triangular Irregular Network 简称TIN）。
数字化等高线模型不适合计算坡度或制作地貌渲染图等地形分析，规则格网数据结构简单，计算方便；但存在数据冗余，数据采集较麻烦，难以表达复杂地形等缺陷。
TIN即能够避免平坦地形时数据冗余，也能表达复杂地形，可以根据任意地形特征点表示DEM，因此被广泛应用。
Delaunay三角剖分能最大程度的接近等边三角形，避免狭长三角形，并且能保持三角网的唯一性，使其成为生成TIN的最佳选择。
本论文将简要介绍和比较几种常用的Delaunay三角网生成算法（逐点插入法，三角网生长法，分割合并算法等），并且对三角网生长法算法原理进行研究分析和程序实现。
2.Delaunay三角网的性质Delaunay三角网中的三角形必须满足以下几个性质：（1）空圆特性每一个Delaunay三角形的外接圆不包括Delaunay三角网中的任何其他点。
（2）最大最小角特性在三角剖分中，Delaunay三角网的所有三角形的最小角之和最大。
即使得Delaunay三角形最大程度接近等边三角形。
不规则三角网（TIN ）生成算法一、三角剖分的标准：空外接圆法：任意四点不能共圆最大最小角法：三角网内的最小角尽可能的大最短距离和准则：形成的三角形三边之和应满足最优解——三边之和最短张角最大准则：面积比准则： 三角形的内切圆面积/三角形面积或三角形面积/三角形周长的平方的值最小对角线法则：但插入另一个点时，寻找四边形对角线最短的那条边作为新的三角网二、Delaunay 符合的标准：三、递归生长算法的基本思路：四、凸闭包收缩法：先找到包含数据区域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形网络五、逐点插入法生成TIN 的思路：首先提取整个数据区域的最小外边界矩形范围，以此作为最简单的凸闭包->按一定法则将数据区域的矩形范围进行格网划分，限定每个格网单元平均拥有的数据点数->根据数据点的（x,y ）坐标建立分块索引的线性链表->剖分数据区域的凸闭包形成两个超多边形->按照3建立的顺序链表顺序往4的三角形中插入数据点：先找到包含数据点的三角形，进而连接该点与三角形的三个顶点，简单剖分该三角形为三个新的三角形->分别调整新生成的三个三角形及其相邻的三角形，交换公共边->重复5~6，直到所有数据点都被插入到三角网中六、三角网TIN数据类型：无约束数据域——无约束TIN 约束数据域：内部约束及外部约束七delaunay法则：当三角形外接圆内不包含任意其他点，且其三个顶点相互通视时形成的三角网为一个带约束条件的delaunay法三角形八、带约束条件的delaunay Lawson LOP交换：在带约束的delaunay法则满足的条件下，由两相邻三角形组成的凸四边形的局部最佳对角线才被选取九、在TIN生成中如何考虑地形特征线三角剖分时要求TIN三角网中得三角形满足形态最优和无地形线穿越三角形的要求，主要有：三角形初始剖分->判断剖分三角形是否满足三角形形态比最大原则->判断特征线是否穿越剖分三角形->剖分点选择。
基于基于不规则三角网不规则三角网不规则三角网构建构建构建的的网格生长算法刘 刚，李永树李永树，，张水舰(西南交通大学地理信息工程中心，成都 610031)摘 要：提出一种基于离散点Delaunay 三角网快速构建的网格生长算法，采用分治算法将离散点表达为唯一网格，利用稀疏矩阵完成网格数据的压缩存储，通过标识码实现有值单元格与离散点之间的高效检索，从而提高网格构建的效率。
依据有值单元格的密度获取预设正方形搜索空间，并在三角网扩展时根据需要动态建立正方形搜索空间，从而保证网格生长的准确性。
实验结果表明，该算法的时间复杂度为O (n log n )，对于少量或海量离散点均具有较好的适应性。
关键词关键词：：Delaunay 三角网；不规则三角网；离散点；正方形搜素空间；网格生长算法Grid Growing Algorithm Based onTriangular Irregular Network ConstructionLIU Gang, LI Yong-shu, ZHANG Shui-jian(Geography Information Engineering Center, Southwest Jiaotong University, Chengdu 610031, China)【Abstract 】This paper presents a grid growing algorithm for fast construction of Delaunay irregular network based on discrete point. In this algorithm, a grid is achieved to express discrete point uniquely based on the divide-and-conquer method, which is compressed storage in a sparse matrix, and an efficient retrieval method is established between value cell and discrete point by identification code, which is effectively to improve the efficiency of the construction of Triangular Irregular Network(TIN). According to the density of value cells, a default square search space is acquired, and it is allowed to create the square search space dynamically in the expansion process of TIN, which ensures the accuracy of the grid growing. Experimental results show that the time complexity of the proposed algorithm is O (n log n ), and the algorithm is available to both small and massive amount of discrete points.【Key words 】Delaunay triangular network; Triangular Irregular Network(TIN); discrete point; square search space; grid growing algorithm DOI: 10.3969/j.issn.1000-3428.2011.12.019计 算 机 工 程 Computer Engineering 第37卷 第12期V ol.37 No.12 2011年6月June 2011·软件技术与数据库软件技术与数据库·· 文章编号文章编号：：1000—3428(2011)12—0056—03 文献标识码文献标识码：：A中图分类号中图分类号：：P2091 概述不规则三角网(Triangular Irregular Network, TIN)表面建模是一种很重要的表面建模方法[1-2]。
在所有生成TIN 的方法中，Delaunay 三角网最优，它尽可能避免了病态三角形的出现，常被用来生成TIN 。
目前，利用离散点构建Delaunay 三角网的方法有很多，主要有逐点插入法、三角网生长法、分治算法等[1]。
逐点插入算法是Lawson C L [3]提出的，之后Bowyer A [4]、Watson D F [5]等人对其进行发展。
该算法的时间复杂度一般在3/2()O n ~(log )O n n [6-7]，在处理过程中每插入一个点都要判断插入点所在的三角形，随着数据点的不断插入，三角形的个数成倍增加，将花费大量的时间在三角形的定位上，从而直接影响算法效率。
三角网生长法、分治法等算法的时间复杂度的下界为(log )O n n 。
三角网生长法将大部分时间花费在搜索符合要求的给定基线的邻域点过程中，分治算法由于递归执行，算法需要较大内存空间[8]，对海量数据而言，两者的效率都较低。
为提高不规则三角网的构建效率，本文提出一种基于离散点构建不规则三角网的网格生长算法，重点研究如何由离散点生成规则网格，并在此基础上建立TIN 模型。
2 一种一种构建构建构建不规则三角网的不规则三角网的不规则三角网的网格网格网格生长算法生长算法2.1 离散点离散点网格网格网格化化网格由许多单元格组成，通常将单元格看成一个对象。
从处理效率上看，单元格值的情况越少，单元格之间的计算速度越快。
所以，从计算效率出发，针对离散数据确定如下规则网格构建准则：规则网格包含所有离散点，每个离散点对应一个单元格，且一个单元格内的离散点数量小于2。
当单元格内存在一个离散点时表示该单元格有值(用1表示)，称为有值单元格，当不存在离散点时表示该单元格无值(即为Null)，称为空值单元格，并将按照该准则建立的规则网格称为唯一网格，其唯一性体现在离散点与有值单元格的一一对应关系。
原理如图1所示，图1(a)表示一个单元格只包含 1个或0个离散点，图1(b)是对有值单元格进行赋值的结果(其中，黑色表示有值单元格即为1；其余无值即为Null)。
(a)离散点与网格关系 (b)网格化结果图1 离散点离散点网格网格网格化化 基金项目基金项目：：“十一五”国家科技支撑计划基金资助项目(2006BAJ05 A13)作者简介作者简介：：刘 刚(1986－)，男，硕士，主研方向：复杂网络，GIS 原理及其应用；李永树，教授、博士生导师；张水舰，博士 收稿日期收稿日期：：2011-01-08 E-mail ：liugang233666@第37卷 第12期 57刘刚, 李永树, 张水舰：基于不规则三角网构建的网格生长算法2.2 网格网格生长生长生长算法原理算法原理空间自相关理论反映空间相邻对象在地理特性上的相互影响程度，认为距离越近的实体，彼此的影响程度越大(也可理解为共性越多或联系越紧密)。
从空间自相关角度可知，在不规则三角网构建过程中，距离当前基线较近的点对生成三角形的贡献较大，所以，算法采用局部搜索策略进行三角网的扩展，基本思想如下：根据有值单元格在网格中的密度，并以常数C N 表示每次搜索需要参考的有值单元格数量，从而确定一个正方形搜索范围R [X min, Y min, X max, Y max]，之后每次扩展只需在当前基线周围的R 区域内寻找一个与当前基线满足Denaulay 三角形的有值单元格即可。
当引入局部约束条件时，将约束条件范围表达为对应的网格区域并建立相应规则。
网格生长算法原理如图2所示。
图2 网格网格生长生长生长算法原理算法原理在图2中，黑色粗线框为正方形搜索范围R ，其4个参数X min 、Y min 、X max 、Y max 为指定的行、列位置；实线三角形是已有三角形；以该三角形一边为基线并在当前正方形空间内搜索到一个有值单元格满足Delaunay 准则并生成一个新三角形，如虚线所示。
2.3 网格网格生长生长生长算法流程算法流程网格生长算法流程主要分为3个阶段：第1个阶段是由离散点构建唯一网格，建立离散点与有值单元格之间的对应关系；第2个阶段是确定每次搜索需要参考的有值单元格的数量(用N c 表示)，并计算有值单元格在整个网格中的密度，从而获取空间R 的预设大小；第3个阶段是基于所建网格按照Delaunay 准则构建不规则三角网。
网格生长流程见图3。
图3 网格网格生长生长生长算法流程算法流程2.4 网格网格生长生长生长算法实现算法实现 2.4.1 数据结构在算法的整个实现过程中，需要频繁地对网格数据和离散数据进行调度，提高算法效率必须建立离散点与有值单元格之间的高效检索。
为此，建立如下数据结构，其中，Point 表示离散点；Edge 表示三角边；Triangle 表示三角形；HasUnit 表示有值单元格。
typedef struct { long id; /*离散点id 号*/ double X,Y; /*X 坐标、Y 坐标*/ } Point;typedef struct { long id; /*三角形边的id*/ long point_id[2]; /*from-point, to-point*/ long lt_id, rt_id; /*边左右邻接三角形*/ } Edge;typedef struct { long id; /*三角形id*/ long edge_id[3]; /*三角形三条边的id*/ } Triangle; typedef struct { long row, column; /*单元格行、列号*/ long point_id; /*单元格对应的离散点id*/ } HasUnit;按照2.1节中网格构建准则构建的规则网格的单元格数量很大，但有值单元格所占比重极小。
在空间分布上可认为该网格是一个稀疏矩阵，所以，采用三元组顺序表实现网格的压缩存储以及与离散点的高效检索。
网格存储结构见表1。
表1 网格网格存储结构存储结构有值单元格的行号 有值单元格的列号 对应的离散点id 号25 28 3 201 139 … … … mnk2.4.2 基于离散点的唯一网格构建根据离散点数据构建唯一网格的过程如下：(1)求出离散点集合P 的最小矩形范围T [X min, Y min, X max, Y max]。
