二维Delaunay三角网的任意点删除算法研究

针对目前基于影响域多边形剖分的点删除算法缺陷,提出一种二维Delaunay三角网点删除算法。首先利用具有拓扑关系的三角网搜索影响多边形,并以三角形矢量面积为工具三角剖分影响域多边形,最后通过镶嵌优化后的剖分三角网完成点的删除,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。     

约束Delaunay三角网点删除的一体化凸耳消元法(IEE)

对Delaunay三角网(CD—TIN)点删除算法——凸耳消元法(EE)进行剖析,提出约束Delaunay三角网的点删除算法——体化凸耳消元法(IEE)。该算法将CD-TIN的点删除转化为点的影响域重构,并保证重构后的CD—TIN满足CD—TIN的可视性与空圆法则,确保了CD—TIN的拓扑完备性,实现了CD—TIN中约束点与非约束点删除的一体化操作和局部更新,并得到实验验证。     

二维Delaunay三角网的任意点插入算法研究

针对目前各种点插入算法的不足,提出一种二维Delaunay三角网任意点插入算法。首先基于凸壳区分点的位置,并利用三角形面积坐标、重心和点与有向线段关系三者构建的融和算法搜索插入点所在三角形,然后通过构建和优化新三角形完成点的插入,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。     

基于线性和岛屿约束的Delaunay三角网构建算法研究

针对基于线性和岛屿约束的Delaunay三角网构建算法的不足,从减少算法计算机实现步骤出发,研究改进了线段相交判断、首三角形确定等影响域多边形搜索相关算法;在分析当前存在的多边形三角剖分算法基础上,给出了存在重复点(悬边)的多边形三角剖分算法;在影响域多边形搜索阶段充分利用多边形间的拓扑关系信息,消除了岛屿约束内部三角形删除时需遍历三角形数据的不足.算法涵盖线性和岛屿约束的构建,综合性强,效率高且易于实现.     

Delaunay三角网约束的Harris-SURF图像匹配算法

Harris算法提取的角点定位精度高,但不具尺度不变性,SURF算法虽具有尺度不变性和旋转不变性,但提取的特征点并非视觉角点。针对此问题,该文提出一种Delaunay三角网约束下的Harris-SURF图像匹配方法。首先,采取阈值评估策略对图像进行SURF粗匹配,利用RANSAC算法进行粗差剔除,得到的匹配点用于构建Delaunay三角网;然后以相似三角形作为约束,将其作为Harris特征点精匹配的限制区域,提高Harris点匹配的可靠性。实验表明,该算法具有匹配准确率高、鲁棒性较好等特点,对无人机影像的匹配效果明显优于其他算法。     

基于四叉树索引构建TIN的高效合成算法

不规则三角网(TIN)可以逼真的模拟地形表面,因此被广泛应用于地学领域。Delaunay三角剖分算法是构建TIN网的最优算法,该文对传统Delaunay三角网构建算法进行分析,提出了一种针对大规模离散数据点生成TIN的高效合成算法。该算法首先根据离散点的分布位置和密度对其进行四叉树区域划分;然后以每个叶子节点的边界四边形为凸包,采用逐点插入法构建三角网;最后采用顶点合并法自底向上合并具有相同父节点的4个子节点,生成Delaunay三角网。实验结果表明,该算法时间复杂度较低,有效提高了TIN网的构建效率。     

等高线约束的Delaunay三角网在土石方量计算中的应用

土石方量计算是工程建设的重要步骤,其计算精度是提高工程质量的首要问题。针对利用无约束不规则三角网计算土石方量时存在的计算精度问题,该文利用三维激光点云数据,根据约束Delaunay三角网的构建原理,探讨了基于等高线约束的Delaunay三角网方法在土石方量计算中的应用。首先,以土石方的等高线作为约束线,利用迭代算法对无约束不规则三角网进行剖分,构建等高线约束Delaunay三角网,并进行土石方量计算。然后,将计算结果与无约束不规则三角网、方格网法计算结果进行对比与误差分析,验证了该方法的计算精度,为基于三维点云数据的土石方量精确计算提供了参考。     

自适应的IDW插值方法及其在气温场中的应用

反距离权重(Inverse Distance Weighting,IDW)插值通常采用距离搜索策略选择插值参考点,当采样点集分布不均匀时,距离搜索策略使得参考点聚集一侧影响插值精度。自然邻近关系具有良好的自适应分布特性,可有效地解决参考点分布不均匀问题。结合自然邻近关系,提出自适应的反距离权重(Adaptive-IDW,AIDW)插值方法。首先对采样数据构建初始Delaunay三角网,然后采用逐点插入法,将待插值点插入初始Delaunay三角网中,局部调整得到新的Delaunay三角网,以待插值点的一阶邻近点作为IDW插值的参考点,使参考点自适应均匀地分布在待插值点周围,再进行IDW插值计算。利用AIDW插值方法对Franke函数、全国气温观测数据进行插值实验,结果表明此方法具有较高的精度,且减少了“牛眼”现象。     

基于众源轨迹数据的道路中心线提取

从众源轨迹数据中提取道路几何数据相对于传统的道路数据获取方法具有低成本、高现势性的优点。然而,由于轨迹数据采样稀疏、数据量大、高噪音等特征使得道路中心线提取仍显困难。针对该问题,提出一种基于约束Delaunay三角网的道路中心线提取方法。首先对预处理后的车辆轨迹线构建约束Delaunay三角网,根据整体长边约束准则删除长边以提取道路面域多边形;然后对道路面多边形二次构建Delaunay三角网,提取道路中心线。利用北京市一天时间的出租车轨迹数据进行算法实验,将实验结果与栅格化方法结果进行定性定量地评价分析。结果表明该方法提取的道路中心线数据在几何、拓扑精度方面比栅格化方法提高约10%以上。另外,以复杂环形道路为例,证明了该方法比栅格化方法更适合于复杂道路结构、较大密度差异的轨迹数据。因此,该方法不仅适合大数据处理、结果精度高,且算法成熟、易于实现。     

一种高准确度的约束Delaunay三角网生成算法研究

约束线段的嵌入是CDT两步法的关键步骤之一,目前该方面的研究还不够完善,主要忽视了影响区域是凹多边形和影响区域内包含悬挂点的情况.该文研究带有约束条件的Delaunay三角网的生成问题,考虑了约束线段影响区域的特殊情况,采用递归割耳法嵌入约束线段,先将影响区域调整为简单多边形,再递归寻找并割去多边形的耳,最终将影响区域重新三角剖分.该方法可有效提高约束DIelaunay三角网的质量.     

基于Hash函数的TIN拓扑关系重建

STL模型是CAD、景观造型器等图形处理软件中常用的三角形网络文件格式,该文件由于不带有三角形的拓扑关系,使其不便与GIS中的地形模型(如TIN)进行叠置分析等操作。提出一种基于Hash函数的STL模型的三角形拓扑重建算法,讨论Hash函数设计和评价,给出基于Hash函数的TIN拓扑重建算法和拓扑检查方法,并通过实例对该算法进行验证。     

A TIN compression method using Delaunay triangulation

This study introduces a new Triangulated Irregular Network(TIN) compression method and a progressive visualization technique using Delaunay triangulation. The compression strategy is based on the assumption that most triangulated 2.5-dimensional terrains are very similar to their Delaunay triangulation. Therefore, the compression algorithm only needs to maintain a few edges that are not included in the Delaunay edges. An efficient encoding method is presented for the set of edges by using vertex reordering and a general bracketing method. In experiments, the compression method examined several sets of TIN data with various resolutions, which were generated by five typical terrain simplification algorithms. By exploiting the results, the connecting structures of common terrain data are compressed to 0.17 bits per vertex on average, which is superior to the results of previous methods. The results are shown by a progressive visualization method for web-based GIS.     

Comparison of existing triangulation methods for regularly and irregularly spaced height fields

Over the last two decades, the Delaunay triangulation has been the only choice for most geographical information system (GIS) users and researchers to build triangulated irregular networks (TINs). The classical Delaunay triangulation for creating TINs only considers the 2D distribution of data points. Recent research efforts have been devoted to generating data-dependent triangulation which incorporate information on both distribution and values of input data in the triangulation process. This paper compares the traditional Delaunay triangulations with several variant data-dependent triangulations based on Lawson's local optimization procedure (LOP). Two USGS digital elevation models (DEMs) are used in the comparison. It is clear from the experiments that the quality of TINs not only depends on the vertex placement but also on the vertex connection. Traditonal two step processes for TIN construction, which separate point selection from the triangulation, generate far worse results than the methods which iteratively select points during the triangulation process. A pure data-dependent triangulation contains a large amount of slivers and steep triangles, which greatly affect the quality of TINs constructed. Among the triangulation methods tested, the classical Delaunay triangulation is still the most successful technique for constructing TINs for approximating natural terrain surfaces.     

多尺度TIN管理及表达算法探讨

为实现大规模地形的多分辨率显示与实时绘制,基于LOD技术给出了多尺度TIN的管理和表达算法。探讨该算法相关的数据组织、LOD层次表达、实时刷新等关键问题。该算法使用分级策略,在不影响视觉效果前提下对TIN进行分级表达;使用分区策略,在可视化过程中对TIN进行局部更新。采取不同分辨率TIN模型间逐步过渡策略,基本上消除了视图变换时的跳跃感。实验结果表明,这种紧凑有效的TIN表示方法实现简单,内存开销较少,CPU耗费小,大大缩短了视图刷新切换时间,能够在普通机器上实现大规模地形的实时漫游。     

DEM格网与畸变遥感影像的一体化显示研究

遥感影像可以极大地增强DEM的表达效果,然而由于各种因素的影响,通常需对其进行预处理,传统方法是通过同名控制点进行校正。该文提出一种新的自动匹配算法,即提取DEM和遥感影像对应的特征线,利用Douglas-Peucker算法提取对应的特征点,以DEM特征点为离散点进行Delaunay三角剖分,并基于TIN完成纹理映射。实验结果表明,该算法显示效果较好,可有效改善畸变图像引起的错误显示。