三角网的生成与简化算法

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

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

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

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

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

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

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

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

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

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

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

一种基于DEM的河网快速提取算法

目前从DEM中提取河网应用最普遍的是径向水流算法,但DEM中存在平地会形成平行水流,存在洼地会造成平行水流形成断流。该文提出一种快速提取算法:首先在DEM中标注山顶、平地、洼地和盆地,以山顶区域周围的低洼点为起点,按照最陡坡降追踪谷地,当追踪到盆地区域或其他谷地区域则结束;连接谷地和盆地,建立初步的河流网络。然后计算出网络中连接点的汇水量,舍弃汇水量小的节点的上游谷地,得到需要提取的网络。该算法避免了平行水流和断流的产生,其仅追踪从山顶区域(而非所有格网点)发育的水流,汇水量计算中仅计算连接点(而非所有格网点)的汇水量,实现了河网的快速提取。     

二维Delaunay三角网局部更新:点插入与点删除

二维Delaunay三角网的局部更新在地学分析、道路CAD、城市规划等领域有着广泛的用途,点插入和点删除则是其中最重要、最基本的操作。该文针对原有逐点插入法和凸耳权值点删除算法存在的不足,利用动态包围三角形和特征三角形分别对其进行改进,在设计的具有拓扑关系Delaunay的三角网数据结构基础上,实现Delaunay三角网的快速局部更新,且使之满足Delaunay特性。最后通过模拟实验验证了算法的正确性和高效性。     

规则格网DEM坡度坡向算法的比较分析

DEM的主要用途之一就是提取坡度和坡向。目前基于格网DEM的坡度坡向算法比较多,正确分析和评价现有算法是当前较为关心的问题。通过对格网DEM的算法进行了简要的归纳,然后对坡度坡向算法进行了理论分析。并通过实验对相关的结论进行了验证。本研究澄清了目前有关DEM坡度坡向算法中存在的一些问题,对实际应用有一定的指导意义。     

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

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

一种基于面积平衡约束的图斑化简算法

保持综合前后各地类土地面积平衡是土地利用数据综合的基本原则.地类图斑是面积统计的最小单元,用常规的线化简算法不但难以保证图斑的地理特性,而且会给面积统计带来不确定性.该文提出一种能够使图斑化简前后面积保持绝对平衡的化简算法,该算法给出了求取图斑群和岛图斑的地理特征点、几何特征点的相关方法,对被特征点分割的综合子弧段运用直线面积平衡和参数曲线面积平衡两种求取平衡线的方式进行化简,基本原理是综合前后弧段切割它们自身的包络矩形面积比相等,且综合后的弧段须落入综合前子弧段的误差缓冲区内.实验表明,该算法不但能保持图斑的形态特征,而且能保持图斑化简前后面积绝对相等.     

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

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

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

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

一种基于TIN的DEM表面插值模型

针对目前基于TIN的DEM存在的表面模型单一、表面不光滑、达不到更高的精度等问题,该文利用二元泰勒公式、顶点法向量、插值函数等,提出一种基于TIN的DEM表面插值模型,并利用数学曲面评估模型精度。结果表明,该模型具有较好的光滑效果和精度,扩展了基于TIN的DEM表达方式,为DEM的应用提供了更多的选择。     

曲线化简的弧比弦算法改进及其评价

地图综合是当前国际GIS和制图学领域的一个难题。化简是地图综合的一个基本操作算子,线要素是地图综合操作的主要对象,该文主要研究地图线要素的化简问题。首先,从算法的适用范围、阈值设置等方面分析了现有算法的优点,重点阐述了一种常用的弧比弦算法,并指出了其在化简过程中存在的不足。然后,基于地图曲线的空间认知特征,提出了一种改进弧比弦算法。该算法能够更好地保持曲线的特征点和曲线的几何形态,避免阈值的设置问题。在算法评价上,采用3种定量评价指标,即:偏移平均值、偏移量中值和面积变形值,对改进的弧比弦算法与现有经典算法进行了比较分析。最后,通过算例分析验证了该算法的可行性、有效性和健壮性。     

DEM地形简化指标的分析研究

该文对基于局部误差、曲率和法向量的5个地形简化指标进行分析评价,用离散的高斯合成曲面来模拟真实DEM,以解析得到的高斯曲率作为地形简化指标“真值”,通过对各个指标“保特征性”可信度的分析,获得对这5个指标的整体评价：1)基于法向量的地形简化指标更能反映地形特征;2)各指标的“保特征性”随简化比的减小呈线性上升;3)各指标的优劣排序对地表形状和分辨率不敏感;4)各指标“保特征性”可信度在同一分辨率下较为稳定。并用实例验证结论的正确性。     

多分辨率小波分析在线状要素简化中的应用

空间数据的多尺度表达问题已成为GIS研究的重点,也是地图自动综合的瓶颈。智能化的多尺度表达是亟须解决的问题。利用小波分析中的多分辨率分析原理,建立微分角度的线状要素简化模型,结合空间要素多尺度表达的特征,研究空间线状要素的简化方法,并对简化后的图形拓扑一致性做简单分析,实现线状要素的简化。     

基于空间索引的规则格网DTM内插算法研究

从离散点内插规则格网数字地形模型(DTM)方法的关键是如何提高待插点周围数据的搜索效率。该文针对离散点的空间分布特性,给出了基于网格分块和KD-Tree两种空间索引技术的规则格网内插方法。实验表明,这两种索引方法能显著提高搜索速度,算法内插效率较高。最后,在算法效率分析的基础上,对两种索引方法所适应的条件进行了讨论。