三角网的生成与简化算法

在三维地理信息系统的开发与研究中，要求三角网模型的支持，而高效的三角网生成算法是三角网模型的基础。该文综述各类三角网的生成算法，对以往被人忽视但简明高效的算法－径向扫描算法进行阐释，并对它的实现进行改进；对地形数据的简化及建立地形层次对象模型是实现高效的三维地理信息系统的关键，而三角网的简化是地形数据简化的基石之一，文中提供三种简化三角网的的算法供同行讨论；并在微机上实现上述算法。     

顾及等高线和凹边界特征的不规则三角网生成方法

传统的不规则三角网生成算法会导致等高线凹边界处生成大量的狭长三角形,影响地形表达模型的准确性和合理性.该文提出了渐进式的三角网扩展生成方法,设计了三角网渐进式的扩展原则和具体的实现方案,发展了闭合扩展边链的提取和三角化的方法,构建了顾及等高线特征的Delaunary三角网模型,并应用某煤矿煤顶板数据进行了相关实验.结果表明:该方法既保留等高线的基本特征,又能有效地消除等高线凹边界处的狭长三角形.     

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

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

一种基于TIN的地形剖面线生成算法

在目前已有基于规则格网(Grid)生成地形剖面线的基础上，提出了一种适用于不规则三角网(TIN)的剖面线生成算法。该算法充分利用TIN中各三角形间存在的拓扑关系，实现了与剖面线相交三角形的快速搜索，大大提高了算法的执行效率。由于地形简化后的TIN仍保留三角形间的拓扑关系，该剖面线生成算法还适用于多分辨率的海量TIN数据。     

基于地形坝体一体化三维场景的水库洪水淹没模拟

提出一种无缝融合地形三角网与坝体虚拟现实模型、构建一体化水库库区三维场景的方法。基于真实连续的下垫面环境进行确定水位的淹没模拟,其中地形部分以迭代实现邻接扩展的淹没算法,坝体部分通过高程比较与体元轴对齐包围盒相交判断确定迎水面受淹形态。通过计算广义三棱柱及其变体的离散水体体积,求得水位对应库容,并构建二分查找判定树,以快速获取接受净入库洪量后的库区洪水淹没结果,并在三维场景中渲染表达。实验结果表明,基于地形坝体一体化三维场景的计算模拟方法,相比传统库容曲线与洪水风险图能够在展现库区洪灾影响范围的同时,兼顾坝体局部的淹没细节。     

基于SRTM DEM数据的全国地表面积计算研究

对山区表面积的估算方法为准确估算复杂地形条件下的陆地生态系统固碳特征提供了基础条件。投影面积与实际表面积在山区有相当大的差异,这些差异对于估算陆表覆被面积、碳水循环有较大的影响。该文通过地形特征点提取算法和不规则三角网构建算法,以省域为单位提取地形特征点,并在此基础上构建了不规则三角网,求算区域表面积。根据表面积与投影面积的比较,得出以下结论:1)不同分辨率的DEM数据对计算结果是有影响的,分辨率越大,表面积越大;2)在SRTM DEM尺度(90m)下,我国陆地范围的表面积为1 003.36万km2,比投影面积多出约43万km2。     

海量三维地形数据集的流式处理

该文提出基于网络实时交互的海量三维地形数据的流式处理方案。通过一个输出恒定的动态多分辨率简化算法,对三维地形数据进行裁剪简化,实现与总数据量和视点位置无关的恒定数据量输出;在算法输出的非均匀高程矩阵上,进一步采用三维地形数据流式编码解码算法,将高程矩阵进行离散余弦变换到频率域,并根据频谱分析结果引入累进式传输编码解码,结合服务质量控制,根据客户端和网络的性能状况进行自适应调节。实验表明,流式处理方案可以根据运行平台性能提供不同质量的场景复原,达到基于网络的实时交互性能。     

多边形主骨架线提取算法的设计与实现

在Delaunay三角网的基础上对骨架线节点进行了分类,通过确定主骨架线的两个端点,运用回溯法提取了多边形的主骨架线,同时给出了详细的算法步骤,并在Visual C++2003环境下实现了该算法。较之其他算法,该算法思路简捷,易于编程,生成的主骨架线形态优良,较好地反映了多边形的主体形状特征和主延伸方向。     

组件式三维GIS技术及应用研究

组件化是地理信息系统软件开发的发展方向，而三维可视化是地理信息系统的核心技术之一。文章就三维地理信息系统开发中的关键技术进行了研究，如：三维场景综合建模平台、地形模型的建模和处理、地物模型的建模和处理、地物模型与地形模型融合、基于矢量地图数据生成地表纹理、视景数据动态管理等。并运用开发的系统对河南省新密市古城寨遗址进行了模拟。     

基于拓扑追踪的不规则三角网裁剪算法

针对地质建模中常见的空间曲线(如断层线、断层多边形、等值线等)提出一种较为通用的空间曲线裁剪三角网算法,并给出合理的空间裁剪曲线定义。利用依附于三角网上的空间曲线,沿着三角网进行拓扑追踪,并沿追踪轨迹进行分离,最终实现三角网的裁剪。该算法对开曲面、闭曲面、复杂地质曲面裁剪效果都很好,算法复杂度低,易于编程,适用于绝大多数的地质曲线对不规则三角网的裁剪。     

摄影测量三维重建中多源信息融合方法探讨

分析摄影测量三维重建中不同数据源的特点,针对现有多源数据融合存在的有限数据源低层次融合问题,提出一种基于影像特征、GIS信息和3D TIN模型融合的层次结构与算法流程 .该算法主要包括多边形区域增长、几何推理和建筑物几何模型平差等处理,为基于摄影测 量的三维城市模型自动重建提供了一种新的思路与方法.     

An integrated TIN and Grid method for constructing multi‐resolution digital terrain models

Multi‐resolution terrain models are an efficient approach to improve the speed of three‐dimensional (3D) visualizations, especially for terrain visualization in Geographical Information Systems (GIS). As a further development to existing algorithms and models, a new model is proposed for the construction of multi‐resolution terrain models in a 3D GIS. The new model represents multi‐resolution terrains using two major methods for terrain representation: Triangulated Irregular Network (TIN) and regular grid (Grid). In this paper, first, the concepts and formal definitions of the new model are presented. Second, the methodology for constructing multi‐resolution terrain models based on the new model is proposed. Third, the error of multi‐resolution terrain models is analysed, and a set of rules is proposed to retain the important features (e.g. boundaries of man‐made objects) within the multi‐resolution terrain models. Finally, several experiments are undertaken to test the performance of the new model. The experimental results demonstrate that the new model can be applied to construct multi‐resolution terrain models with good performance in terms of time cost and maintenance of the important features. Furthermore, a comparison with previous algorithms/models shows that the speed of rendering for 3D walking/flying through has been greatly improved by applying the new model.     

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.     

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

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

基于表面模型的三维数据重建方法的研究与实现

该文分析了三维数据重建的研究现状 ,提出了基于表面模型的三维数据重建方法 ,给出了具体的算法和应用实例。实例证明算法是收敛的 ,具有较高的精度。该方法对于三维数据重建、三维GIS以及数字城市的建设具有一定的应用价值     

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

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

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

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

Robustness in GIS algorithm implementation with application to line simplification

The sensitivity of computed results to implementations of algorithms in GIS is considered in this paper on the example of a precisely defined recursive variant of the Ramer-Douglas-Peucker line simplification algorithm (called the R-D-P algorithm). We establish a robust version of the R-D-P algorithm where the determination of the simplification is rounding error free if the data are already machine numbers. Under these assumptions, the results are reproducible which is not the case with other versions of the algorithm.     

基于GIS的边坡有限元网格自动生成研究

GIS已广泛运用于滑坡灾害研究,但GIS和数值方法相结合研究边坡问题的文献很少。原因在于边坡失稳和滑坡形成是复杂的三维空间物理力学过程,而三维空间数据模型理论还不成熟。因此,在现有GIS软件平台上实现大区域滑坡灾害数值模拟的关键在于三维有限元网格的自动生成。该文研究边坡岩土数值分析相关数据的GIS数据存储格式,提出基于栅格的六面体有限元网格生成和基于TIN的三棱柱有限元网格生成,并利用ArcGIS9．0、Amys7．0实现有限元网格自动生成。