再论三维Douglas-Peucker算法及其在DEM综合中的应用

相对于笔者在已发表论文中所提出的一般性方法,本文在算法上有了进一步的改善或扩展。结果表明,这些措施在保证综合效果的前提下,可以大大提高DEM的综合速度,从而为海量DEM数据的全局动态式综合提供了现实的可能性。

3维Douglas-Peucker算法及其在DEM自动综合中的应用研究

在分析2维Douglas-Peucker算法原理实质的基础上,提出3维Douglas-Peucker算法,并将此法应用到对DEM的基础———3维离散点的自动综合上。采用计算机程序对新算法进行的验证,初步结果表明该算法能较好地筛选出DEM整体及局部范围的地貌特征点,其计算效率也较令人满意。

曲线拟合的Douglas-Peucker算法阈值优化选择

通过迭代法得到Douglas-Peucker算法阈值与线要素化简质量相关特定属性的样本数据;利用曲线拟合法得到阈值与线要素长度和点数之间的函数关系;分析给定区间上阈值-点数关系函数的曲率,寻求最大曲率点对应的阈值作为化简算法最优阈值。从定性和定量两方面揭示了化简算法阈值选择对化简结果的影响规律,提出化简阈值的优化确定方法。适用于利用Douglas-Peucker算法化简海量线要素数据时分析化简阈值的影响及确定化简算法最优阈值。

Douglas-Peucker算法在无拓扑矢量数据压缩中的改进

分析了常规Douglas-Peucker算法压缩无拓扑矢量数据时产生公共边"裂缝"现象的原因,即公共边被两次或可能更多次压缩,而每次运用Douglas-Peucker算法压缩时所选择的初始点和终点不同造成的。为此,提出了公共边对象化Douglas-Peucker改进算法。为实现此算法,首先设计了新的公共边提取算法来提取公共边,然后使用OOP技术,把公共边的相关信息封装成类,最后根据公共边对象提供的信息对多边形的公共边和非公共边分别进行Douglas-Peucker压缩。以广东省行政界线的SVG矢量图为实验对象验证了该算法的有效性,分析了该算法相对于其他Douglas-Peucker改进算法在所需辅助空间和时间效率上的优势。

基于面积保持的Douglas-Peucker改进算法的多边形化简

面状数据的化简是空间数据多尺度表达和制图综合必须处理的关键问题,有些面状的地理要素要求简化前后面积保持一致,并且不破坏原来的拓扑关系。因此必须对原有的线化简算法做适当的改进。提出对要化简的多边形根据其与相邻多边形的邻接关系,对邻接线段分别化简,以保持原来的拓扑关系;并在采用Douglas-Peucker算法化简时,加入面积平衡的约束条件,构造"平衡线",使化简前后保持面积一致。通过对实验数据化简结果的分析,改进的算法能很好保持化简前后面积及拓扑的一致性,但较Douglas-Peucker算法化简结果,其化简率较小一些。

采用3维Douglas-Peucker算法的等高线综合

在数字环境下进行等高线综合是制图综合领域中的热点问题。将3维Douglas-Peucker算法应用于等高线综合,是从真3维的角度提取等高线上的特征点。首先根据等高线上高程点的空间分布特征,提出采用空间线规则排序方法组织空间点;引入了全局孤独指数解决综合过程中等高线之间的空间跳跃问题;然后通过空间内插引绘综合后DEM的等高线,从而实现等高线的自动综合。初步实验表明,采用3维Douglas-Peucker算法的等高线综合,从全局上保持了主要地貌形态并抑制了破碎的微地貌特征,具有良好的综合质量和制图效果。

Douglas—Peucker和LZW算法在矢量数据压缩中的应用

在分析矢量数据结构特点、Douglas—Peucker和LZW算法原理及其优点的基础上，提出先用Douglas—Peucker对矢量数据进行有损压缩再用LZW进行无损压缩的压缩流程，取得了很高的压缩比。

基于径向约束与点位优化的Douglas-Peucker改良算法

目前众多的矢量数据压缩算法存在提高压缩曲线精度的同时牺牲压缩效率的问题。为此,文章提出一种以带有径向约束的Douglas-Peucker算法为基础来调整曲线局部形态特征点位置的矢量数据压缩算法。首先,通过带有径向约束的Douglas-Peucker算法提取曲线的特征点;其次,筛选出各个局部曲线段的重要形态特征点;最终,通过重要形态特征点对曲线进行局部调整,以提高曲线整体精度。实验表明,该方法一方面保证了压缩效率不变,另一方面能够有效降低局部位移偏差和面积偏差,从而提高曲线的压缩精度。

基于动态规划算法的矢量数据压缩改进算法

为了使移动设备存储大容量的矢量数据和提高矢量数据的网络传输效率,矢量数据压缩是一项很重要的工作。提出了基于动态规划算法的矢量数据压缩的模型和改进方法,通过一条参考路径构造一条带形成最小误差搜索范围,同时条带宽度可自适应调整。实验结果表明,该方法具有较高的效率,能够得到较小的压缩误差。

附有限制条件的逐点压缩算法的设计与实现

讨论矢量数据压缩问题,着重介绍Douglas-Peucker算法,并分析该算法在矢量数据压缩过程中的局限性,提出附有限制条件的逐点压缩法。新的算法在满足给定限差的前提下,能够对曲线进行实时分析,并很好地考虑了目标曲线之间的相互关系。试验表明,该算法与Douglas-Peucker算法相比,不仅克服了后者在数据压缩过程中的局限性,且在数据压缩率和算法效率方面都得到了改进。

基于GA的矢量数据压缩优化算法

矢量数据压缩在地形环境仿真、制图综合、GIS等研究中具有重要作用,对增加移动设备的存储能力和提高矢量数据的网络传输效率来说是一项很重要的工作。根据遗传算法理论、Douglas-Peucker算法和矢量数据的特点,提出了基于GA的矢量数据压缩的模型和方法。通过对构成曲线的结点进行二进制编码,以压缩后结点数较少和误差较小为优化目标,并利用Douglas-Peucker算法控制选择、变异和交叉的有效性,所得最优解中值为1的基因对应压缩后的曲线结点。实验结果表明,该方法能够得到较大的压缩率。

基于约束点的无拓扑多边形数据压缩算法

分析了常规压缩算法(如Douglas-Peucker算法)压缩无拓扑多边形数据会产生公共边界不一致现象,认为出现此现象的原因是多边形公共边界的压缩起始点选择不一致,进而提出了一种新的基于约束点的无拓扑多边形数据压缩算法。算法原理包括:首先将多边形公共边界的两个端点作为约束点处理,使得多边形从约束点处逻辑上分成几段;然后利用常规压缩算法进行分段压缩,使每一多边形公共边界的压缩初始点一致,从而保证了无拓扑多边形数据的一致性压缩;最后大量试验验证了此算法的有效性。

坐标转换中地貌重构算法研究

由于历史和地理的原因,我国不同地区平面坐标系统和高程基准不尽相同。因此在不同高程基准面地形图数据的坐标转换中,往往需要重新勾绘等高线,重现该地区的地形地貌。利用二次开发语言,详细介绍地形图中高程数据配对、等高线赋值、抽稀以及生成相关算法。

DP⁃B样条移动机器人路径光滑算法

针对快速扩展随机树算法(RRT)产生的路径冗余点过多与路径转折点较多的问题,提出了一种基于Douglas⁃Peucker算法及B样条函数的路径光滑算法。首先,利用Douglas⁃Peucker(DP)算法从RRT算法产生的路径节点中提取出若干节点作为关键路标;然后,采用B样条函数拟合关键路标,得到一条曲率连续的光滑路径,实现规划路径的光滑化。通过在不同环境中进行实验和与其他路径光滑算法实验进行对比,结果表明,该算法能够明显缩短优化路径的路径长度,明显减少优化路径转折次数,大幅度提升优化路径的光滑度,有利于减少机器人在单次航程中的能量消耗,完成更多任务,有效提升机器人的工作效率。

基于样条的矢量数据多尺度表达与压缩算法

传统矢量曲线压缩算法不能解决曲线压缩后的平滑问题,并可能产生拓扑异化。为此,提出基于样条的矢量数据多尺度表达与压缩算法。选择样条的光滑因子作为阈值对曲线进行多尺度表达与压缩,保持压缩前后曲线的光滑特性,利用少量的控制点描述整条曲线,从而提高矢量曲线处理的速度和质量。实验结果表明,该算法仅需9个控制点就能逼近给定的一条原始曲线,验证了其高效性。

一种基于最小四叉树划分的矢量数据水印算法

数字水印在实际应用时可能受到数据裁剪、数据压缩、随机增点和地物加密等攻击。针对该问题,基于特征点图层和最小四叉树划分,提出一种适用于线数据和面数据的矢量图层水印算法。利用Douglas-Peucker压缩算法提取矢量数据的特征点图层,通过最小四叉树划分将水印信息分区域嵌入到地物的特征点中。实验结果表明,该算法具有很好的不可感知性,相比MQUAD算法能更好地抵抗地图裁剪攻击。

基于节点特征的矢量地图零水印算法

为实现高保真矢量地图的版权保护,提出一种基于节点特征的矢量地图零水印算法。该方案以矢量地图线图元节点为基础,先采用道格拉斯一普克压缩算法提取特征节点,然后采用K-means聚类算法对特征点进行分块,最后根据各个分块内的特征点到聚类中心点距离的关系提取特征信息。处理水印图像时,先采用基于完全互补码的扩频技术扩大水印容量,然后采用混沌置乱保障水印的安全,再对水印图像进行分块处理,最后将水印信息与提取到的地图特征进行异或运算,由此构造出能够抗几何变化、简化、数据扰动等攻击的零水印参数。结果表明,该方案能够解决传统水印算法中地图精度与水印鲁棒性间的矛盾,并通过添加多重秘钥的方式保障了算法的安全性。

WebGIS系统中矢量数据的压缩与化简方法综述

空间数据的压缩对于空间数据网络传输以及提高整个WebGIS系统的效率来说是一项很重要的工作。该文针对WebGIS系统中矢量数据压缩问题进行了总结与综述。首先分析了矢量数据压缩的重要性,并对矢量数据压缩技术进行了详细的分类,然后重点分析与比较了Douglas-Peucker压缩方法与小波技术压缩方法,最后简单讨论了WebGIS系统中矢量数据的网络传输策略。

采用3D D-P算法的等高线三维综合实验研究

将等高线看作是由高程点以特定形式组织得到的空间三维线段,采用3维Douglas-Peucker算法从三维空间提取等高线上的主要特征点。根据等高线数据特点,对该算法进行等高线综合的几种方案进行实验讨论。实验结果和运算速度表明,采用3维Douglas-Peucker算法综合等高线具有广阔的研究前景。

一种声图直航段数据自动提取及镶嵌的方法

声图镶嵌是利用成像声纳获得声图进行测深、水下地形地貌测绘的重要应用方向。常见的成像声纳多要求声纳载体做直线运动,而实际应用中载体有大量转弯的情况。为此提出了一种声图直航段数据自动提取方法,该方法首先利用Douglas-Peucker算法对声纳航迹进行抽稀处理,之后利用相邻抽稀点之间的距离判断数据是否为直航段,最后将直航段图像提取出来。获得直航段数据后,利用地理信息对声图进行镶嵌处理。对千岛湖湖底地貌图像进行了处理,获得了较好的镶嵌结果。