格网划分的Delaunay三角网快速生成算法

针对常见的三角网构建算法效率受查找三角形的约束的问题,该文提出了一种基于格网划分的Delaunay三角网快速生成算法,对传统逐点插入算法的点定位及LOP算法进行了优化。通过对离散点数据进行格网划分,将三角形面积坐标法与直线行走算法相结合,在点定位过程中可大幅度缩短搜索路径,快速定位到插入点所在的目标三角形。实验结果表明,改进后的算法兼顾了时间和空间的性能,执行效率明显提高,定位路径惟一且为最佳路径。     

Delaunay三角网的生成算法研究

Ｄｅｌａｕｎａｙ三角作为一种主要的ＤＴＭ表示法,具有极其广泛的用途。经过二十多年来的研究,它的生成算法已趋于成熟。本文简要介绍了Ｄｅｌａｕｎａｙ三角网的定义及其特性,在简单回顾和评价了分割－归并法,逐步插入法,三角网生长法等三类主流算法的基础上,提出了一个融以上算法优点于一体,兼顾空间与时间性能的合成算法。经测试,一般情况下它的运算速度远快于逐点插入法,与分割－归并法相当,较好的情况下快于分割－归     

约束Delaunay三角网生成算法研究

对约束Delaunay三角网的构建算法进行研究,并提出一种约束Delaunay 三角网生成算法,它充分利用分治算法与生长算法的优点,对离散点、构网中实时生成的边及三角形采用分块进行网格索引,有效地减少了搜索目标点、边及三角形的时间,从而提高构网速度.     

Delaunay三角网建立的改进算法

本文深入研究了Delaunay三角网建立算法中的逐点插入法,详细介绍了算法的实现步骤,分析了其中影响算法效率的关键环节,并采用数据点集分块管理、三角形快速定位、改变点插入顺序等方法进行了算法优化,对三角形快速定位方法进行了改进。测试实验的结果说明,算法改进后Delaunay三角网建立的效率提高了4~6倍。     

Delaunay三角网内插多边形算法研究

针对Delaunay三角网内插多边形的实用性,提出了一种Delaunay三角网快速内插多边形算法,该算法先将多边形的边作为约束数据入网,然后对多边形内部三角形进行清空处理.在影响区域及多边形内部三角形确定上,提出了一种快速解决方法,大大提高了算法的执行效率.     

Delaunay三角网内插多边形算法研究

针对Delaunay三角网内插多边形的实用性,提出了一种Delaunay三角网快速内插多边形算法,该算法先将多边形的边作为约束数据入网,然后对多边形内部三角形进行清空处理。在影响区域及多边形内部三角形确定上,提出了一种快速解决方法,大大提高了算法的执行效率。     

一种生成Delaunay三角网的合成算法

结过２０多年的研究,自动生成Ｄｅｌａｕｎａｙ三角网的算法已趋于成熟。它们基本上可分为分治算法、逐点插入法、三角网生长法等３类。其中前两类较第３类在应用上更加广泛。但即使这两类算法也分别存在着时间和空间效率站的缺陷,使它们的应用受到了一定的限制。提出了一个融以上两类算法优点于一体,兼顾空间与时间性能的合成算法。经测试,它的运算效率大大高于逐点插入法,在大多数情况下,也高于分治算法,在分割阈值约为总数     

基于格网和方向法索引的Delaunay三角网生成算法

Delaunay三角网在地形表达、表面对象重建、数字城市等GIS领域有着广泛的应用。常见的三角网构建算法中的逐点插入法算法简单、灵活,但是其效率受查找三角形的约束。文中提出一种用虚拟格网索引和方向法相结合的方法,改进对三角形的索引、对点定位的算法,能有效提高构建三角网效率。通过实验证明,这种方法对计算机硬件配置要求较低,且效率高,构建Delaunay三角网的效果好。     

基于格网和方向法索引的Delaunay三角网生成算法

Delaunay三角网在地形表达、表面对象重建、数字城市等GIS领域有着广泛的应用。常见的三角网构建算法中的逐点插入法算法简单、灵活,但是其效率受查找三角形的约束。文中提出一种用虚拟格网索引和方向法相结合的方法,改进对三角形的索引、对点定位的算法,能有效提高构建三角网效率。通过实验证明,这种方法对计算机硬件配置要求较低,且效率高,构建Delaunay三角网的效果好。     

一种快速二维 Delaunay 三角网点定位算法

在构建二维Delaunay三角网的逐点插入法中,定位待插点所在三角形的快慢是影响整个算法构网速度的关键因素。针对目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题,结合三角形重心的几何性质,对点定位算法进行改进,避免求三角形重心和相交边的过程。实验结果表明,文中算法较目前其他点定位算法能够有效地缩短搜索路径,减少点定位的计算时间,提高Delaunay三角网构网过程中点定位的效率。     

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

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

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

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

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

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

方向后交最佳点位分析

推导出方向后交点住精度的显函数公式;用解析法导出对称交会时最佳交会角和最佳点精度;用无约束最优化共轭梯度法,求出一般情况下方向后交最佳交会角和点位精度;求出同一三角形三个内角分别作顶角进行后交定位的最佳点位,得出三角形内只有一个最佳点位的结论,给出一种选择近似最佳点位的方法.     

精密单点定位及其精度分析

介绍精密单点定位的原理,并且以我国中部和东部GPS跟踪站精密单点定位为例,分析精密单点定位的精度.结果表明,精密单点定位精度与各跟踪站的误差小于0.2m,可以满足某些工程和海洋测绘的精度要求.     

点集收集分配的Delaunay三角网快速生成算法及实现

针对目前Delaunay三角网生成算法中定位待插点所在三角形效率不高的问题,本文提出一种基于对待插点集反复收集分配来完成待插入点所属三角形快速定位的方法.经过在数据结构和实现方式上的改进,算法总体平均时间复杂度为O(NlogN).实验表明,该方法具有实现简单、内存占用较小、运算效率较高等特点.     

Optimized Triangulation Algorithm in Terrain Modeling

3D reconstruction of terrain model based on digital line graphics (DLG) is discussed. An auto-coupling triangles algo-rithm based on triangle topological relationship is put forward, and the topological data model of complicated terrain is developed. Based on this data model, automatic 3D topological reconstruction of terrain is realized.     

空间关系中两相邻实体间最近距离算法研究

空间距离关系是最基本、最重要的一类空间关系。通过先考虑二维空间中两任意实体之间不同的相对位置关系,再利用构建Delaunay三角网寻找两者的邻近区域,从而计算出两者之间的最近距离。本文还提出了基于约束圆寻找并计算任意两个实体多边形之间的最近距离方法,并给出了约束圆的特征。这种方法适用于不用区分实体多边形的形状与位置的各种情况。     

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

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