DELAUNAY三角网的算法详述及其应用发展前景

在GIS应用领域中,Delaunay三角网通常被用于生成不规则三角网(TIN)模型,并用于描述地表形态。本文详细叙述改进了的现有国内外Delaunay三角网的生成算法,并发现Delaunay三角网不但在描述地表形态上有很大的优势,而且在图像处理、模式识别领域也将有很大的优势。而且国内外已经有部分学者专家作出一定的尝试,并且取得了较好的效果。所以作者进一步提出将Delaunay三角网用于地图符号信息识别,将是一个很有发展前景的应用方向。     

TIN模型在温度场研究中的应用

论述了TIN模型在表达区域温度分布状况中的应用,并着重介绍了应用中涉及到的各种算法。采用将连续的空间区域离散化,以点温度值代替微小面元温度的方法来表达区域温度状况。将温度特征点通过Delaunay三角剖分方法生成TIN三角网来对区域温度场进行建模,从而通过内插方法来获取区域各位置的温度值,并在生成的三角网基础上生成等温线和区域温度颜色渐变图来形象、直观反映区域温度状况。为了考察应用效果,作者在成都理工大学主校区进行实地检验,采集了15个温度特征点,通过编程来实现对采样点进行TIN三角网的构建、等温线和区域温度图的生成。实验的结果表明TIN模型在温度场中的应用效果良好。     

基于数学形态学的TIN和GRID自动生成研究

在分析了数学形态学的基本原理的基础上,提出了一种基于数学形态变换自动生成Delaunay三角网(TIN)和规则格网(GRID)的数字高程模型的算法,这种算法将离散的地面点的图像集合进行骨架化并自动构成Thiessen多边形,然后,通过序贯条件形态变换,自动建立TIN和GRID.在建立Thiessen多边形的过程中,提出了用逐点生成数字圆盘的方法来保证变换过程的各向同性;在建立Delaunay三角网的过程中,提出了利用正交结构元素进行条件膨胀,从而保证了相邻点之间的正确位置关系.该方法能保持Thiessen多边形和Delaunay三角网的拓扑关系,因而能保证DEM 的高精度,而且具有数据结构简单、运算速度快的特点.最后,给出了试验结果并与有限元法的结果进行了比较.结果表明,这种方法用于建立DEM具有良好的应用前景.     

海量低空机载LiDAR点云的地形断面快速生成算法

针对现有算法二次插值造成的精度损失问题,结合新兴的低空机载LiDAR技术,提出了一套高精度地形断面快速、自动生成算法。该算法通过内存映射和断面线缓冲区分析,从海量点云数据中快速提取构TIN点集;优化了逐点插入法,实现局部Delaunay三角网的快速构建;根据三角网拓扑关系,实现断面线与TIN的快速求交,生成并优化地形断面图。实验结果表明,算法克服了海量数据处理时计算机内存不足的瓶颈问题,并有效避免了二次插值造成的精度损失,且运行高效。     

GIS中DelaUnaY三角网的快速建立及拓扑自动生成

Delaunay三角网（TIN）是GIS中DTM模型的重要表示方法和分析处理手段。提出了一种构网、自动生成拓扑关系的整体思路，并利用面向对象的技术具体设计了算法，具有建模快、误差小、效率高等优点。     

基于MapX二次开发生成Delaunay三角网

Delaunay三角网作为诸多不规则三角网中结构最优的三角网,被广泛应用于GIS、地学分析、有限元分析等领域.基于三角形生长算法,提出了一种适合于在MapX二次开发环境下生成Delaunay三角网的数据组织方法并给出程序.实现流程及实例,证明了该数据组织方法的可行性,为Delaunay三角网在基于MapX的二次开发应用和研究提供了有益的参考.     

顾及特殊地物的等高线自动生成浅析

以自定义实体作为等高线自动生成的载体,构造了以AcDbEntity为基类的CContour实体．通过该实体自动生成所需要的等高线。在讲述了等高线自动生成的一般过程后,强调在构造Delaunay三角网时,应考虑到地性线和特殊地物对Delaunay三角网构造的影响,利用它们对构造好的Delaunay三角网进行修正,从而构造出准确的Delaunay三角网。这对等高线生成设计有参考意义。     

基于Delaunay三角网的等高线树生成方法

研究如何利用Delaunay三角网构建等高线树,提出一种新的等高线树生成方法。该方法充分利用Delaunay三角网在领域分析中的优势,通过两次利用Delaunay三角网来判明等高线的空间关系进而达到统一被图廓截断的等高线以生成等高线树的目的。本文将等高线作为约束边构建约束型Delaunay三角网,利用Delaunay三角网查找具有邻接关系的等高线,在此基础上结合邻近等高线的高程关系判明、识别,最终统一被截断的等高线;然后对统一后的等高线再次利用Delaunay三角网查找具有邻接关系的等高线对,利用等高线对的高程关系判断出其为父子关系或兄弟关系,据此将等高线插入到相应的位置,逐步生长成等高线树。同时给出了基于Delaunay三角网的等高线树生成方法的算法设计及试验结果。     

一种高阶Delaunay三角网生成算法

Delaunay三角剖分是构建数字地形模型的有效方法,但是该方法可能产生人工大坝和局部极小问题,使得地形模型不能很好地反映原始地形的真实面貌。本文在Delaunay三角网的基础上引入了高阶Delaunay三角网,并给出了一种高阶Delaunay三角网生成算法。实验表明,高阶Delaunay三角网能够有效地减少地形的局部极小数量,是建立数字高程模型的一种新方法。因此,采用高阶Delaunay三角网建立的地形模型更接近于实际地形。     

一种基于Delaunay三角网的地形要素接边检查方法

接边检查是地形要素生产质量检查中必不可少的重点检查项之一,为此各单位也有很多接边质量检查软件,这些软件大多数是通过缓冲区分析或者空间邻近查询的方式完成的。本文提出了一种基于Delaunay三角网的地形要素接边检查新方法,该方法利用Delaunay三角网的优越的空间分析性能,借助于ArcGIS的TIN(Triangular Irregular Network)和二次开发功能,准确、快速地实现了地形要素的接边检查。该方法已用于国家基础地理信息数据库更新项目的成果质量检查。     

基于地图代数的最小生成树实现方法

本文介绍了最小生成树及其常见的算法,对比栅格算法分析了基于矢量的最小生成树算法的缺点,介绍了地图代数的距离变换和基于地图代数的距离变换图生成Voronoi图、Delaunay三角网,然后根据最小生成树MST是Delaunay三角剖分的一个子集,逐次删掉Delaunay三角网中每个三角形的最长边,从而得到最小生成树,该方法不仅适用于欧氏非障碍空间,同样也适用于障碍空间的情况,解决了以往最小生成树在障碍空间下(尤其是当障碍空间中的障碍是全形态的条件下)难以求解的问题,具有一定的理论意义。     

基于等高线构建TIN模型的平三角形修正算法

设计了一种平三角形修正算法来修正TIN模型中可能出现的平三角形区域。该算法通过对由平三角形组成的区域进行分类,并针对不同的平区域采用交换边、增加点甚至不处理的修正方法,同时对由于等高线数据错误产生的一些特殊情况进行了分析处理。实验结果表明,该算法能够去除约束型狄洛尼三角网中所有应修正的平三角形,并生成对地形描述更为精确的三角网。     

基于栅格局部细分的带约束条件的不规则三角网生成算法

采用数学形态学和局部细分的方法生成非凸壳三角网,再通过边界搜索和迭代处理,逐步添补三角网边缘三角形,最终得到具凸壳的Ddaunay三角网。在此基础上,加入内部和外部的边界条件,生成具有复杂边界的带约束条件的Delaunay三角网。     

基于Delaunay三角网的空间邻近关系推理

空间邻近关系是一种重要的空间关系,对这种关系的识别是任何空间建模系统所必须的。Delaunay三角网是根据最小角最大规则建立的一种三角剖分,可以较好地表达空间目标之间的邻近关系。利用Delaunay三角网对空间邻近关系进行了描述,在此基础上提出了空间邻近关系推理方法。     

大量约束边条件下Delaunay三角网的快速生成

讨论了建立约束Delaunay三角网算法的研究现状,采用“逐点插入法”和“多对角线交换算法”构成“两步法”,在此基础上,从建立高精度三角网模型的需求出发,研究以大数据量等高线为约束边进行Delaunay三角剖分的改进算法。针对“逐点插入法”,采用网格分块的方法对构网点集和已生成的三角网建立索引,提高了点的查询速度和点在三角网中的定位速度,提高了三角网的生成效率;针对“多对角线交换算法”,增加了一些特殊情况的处理,提高了算法的健壮性和交换速度。     

集聚型空间点模式结构信息提取研究

空间点模式是一个2维离散点集,点集中的每一个元素代表地球表面一个点状目标的空间位置。当2维离散点集具有集聚特征时,称其为集聚型空间点模式,它与空间聚类、制图综合和空间分析的许多具体应用紧密相关。如何提取集聚型空间点模式的结构信息(集聚子群的个数和对应的集聚中心)是其中尚未彻底解决的问题。作者以几何概率为理论基础,提出测度正方形区域内2维离散点集分布特征的H函数并推导其解析表达式,运用H函数设计和实现了集聚型2维离散点集结构信息提取的通用算法。利用该算法处理一个由居民地坐标数据得到的具有集聚特征的空间点模式,提取出其结构信息并进行可视表达。分别以该空间点模式中的各离散点为顶点和发生元生成Delaunay三角网和Voronoi图,在Delaunay三角网中保留面积最小的前1/10、前1/100三角形的顶点,在Voronoi图中保留面积最小的前1/10、前1/100邻近多边形的发生元,将可视表达的点集结构信息分别与依据Delaunay三角网和Voronoi图得到的结果进行对比分析。结果表明,运用H函数能够有效地提取出集聚型空间点模式的全局性结构信息,而Delaunay三角网和Voronoi图虽然能够反映其局部密度,但在提取全局结构信息时存在局限性。     

基于TIN的半自动多影像同名线段匹配算法研究

提出了根据同名像点构成三角网(TIN)来进行同名直线的匹配。依据TIN预测左影像上一条给定直线在右影像上同名直线的搜索范围，计算给定直线与候选直线的灰度相关系数．取最大相关系数所对应的直线为同名直线。实验证明，该算法简单、可行。     

三角形增长算法构建Delaunay三角网DEM的原理与实现

本文主要论述了三角形增长算法建立Delaunay三角网DEM.首先通过最优边找首三角形,其次通过直线与点几何关系来寻找可能扩展点,通过找最大夹角来判断满足狄洛尼法则的扩展点,最后通过新加入边与已扩展边的数目来判断是否为重复狄洛尼扩展点,符合条件则构建三角网.然后通过空外接圆法则验证了所构三角网符合狄洛尼三角网的条件.狄洛尼三角网的建立和空外接圆的验证程序采用M语言来编写.