矢量数据压缩的角度分段道格拉斯算法研究
[摘要]本文提出了一种矢量数据压缩方法角度分段道格拉斯算法，该方法以道格拉斯普克法为基础通过对角度和距离的判断，取出代表曲率变化的特征点，对曲线进行分段，然后使用道格拉斯普克法进行化简，在所需要化简的曲线弯曲程度变化较大的情况下，该方法可以规避其它压缩方法产生的压缩程度不够丢失曲率变化特征点的问题。
[关键词]道格拉斯普克法; 角度分段; 角度分段道格拉斯算法
1 引言
近年来在计算机技术发展的推动下，地图制图学结合计算机技术形成的计算机地图制图学也得到了迅速发展。已在地理信息系统等领域中得到了广泛应用，并且显示出了强大的生命力。计算机地图制图的一项重要任务就是自动制图综合，而矢量数据压缩既是制图综合的关键技术，又为制图综合提供技术方法。矢量数据压缩的主要对象是线状要素中心轴线和面状要素的边界数据、几何数据。
[1] 笔者在工作实践中发现，在使用道格拉斯-普克法对弯曲程度变化较大的曲线进行化简时，存在着压缩程度与保留曲率变化特征点之间的矛盾。为此作者进行了专门研究与实验。在道格拉斯普克法的基础上提出了角度分段道格拉斯算法
2 道格拉斯普克算法
道格拉斯普克法试图保持曲线走向和允许制图人员规定合理的限差。其执行过程如图2 所示，首先将一条曲线首末点虚连一条直线，求出其余各点到该直线的距离，选出其中的最大距离值max d用max d 与限差D比较。若max d < D ，则这条曲线上的中间点全部舍去；若max d D， 则保留max d 所对应的坐标点，并以该点为界，把曲线分为两部分，对这两部分重复使用该方法
[2] 尽管多数情况下，道格拉斯-普克法压缩算法较好，但是当需要化简的曲线的弯曲程度变化很大而且曲率变化特征点的d 小于与限差D时，这些特征点就会被舍去。如图3， 我们知道地图上曲线的特征点是反映地貌的重要因素。如果一些显著的特征点被省略，那势必会造成地形失真。虽然也可以采用减小限差的方法令道格拉斯普克法保留曲率变化特征点，但势必会降低对曲线的压缩程度。针对这种特殊情况，本文提出了角度分段道格拉斯算法
3 角度分段道格拉斯算法
3.1 角度分段 道格拉斯算法的基本原理角度分段。道格拉斯算法的计算思路主要分为两大步：、
1： 测定角度和距离，取出特征点，每次顺序取曲线上的三个点，计算2、1 点的连线与3、2 点的连线之间的夹角a， 并与限差A比较。若a< A 则，若a A， 则将2 点记录到新建的点集s 中进行2、3、4 点的判断，直至整条曲线结束。此次操作的目的是取出曲率变化特征较为明显的点，依次测量点集s 中相邻两点的距离d ，并与限差1 D 比较。如果某点与其前后两点的距离有一者小于1 D， 则从点集中删除该点，直至点集中的点依次判断完毕。此次操作的目的是防止取出深度较小的弯曲，至此角度测定法执行完毕。点集s 中的点即为特征点
2 ：利用所得到特征点，将曲线分段，对每段曲线单独使用道格拉斯-普克法化简。其具体计算步骤为：
1） 根据需要规定一个角度限差A和一个距离限差1 D 角度测定法的距离限差2 D 道格拉斯-普克法中的距离限差
2） 每次顺序取曲线上的三个点i-1 p i p i+1 p计算i+1 p i p 点的连线与i p i-1 p 点连线之间的夹角i a ，并与限差A比较。若i a A 则将i p 点记录到新建的点集s 中
3） 令i = i +1 重复步骤2 至整条直线结束得到点集{ , ,... } 1 2 k s = p p p k 为点集中点的个数
4） 依次计算点集s 相邻两点的距离并与限差1 D 比较
5） 若i i d -1, < 1 D 或i,i +1 d < 1 D 则删除i p 点令i = i +1 重复步骤2， 按照上述步骤进行判断到整条直线结束为止
6） 利用取出的特征点将原曲线分段，分别利用道格拉斯算法进行化简。化简过程中应注意的问题：1 首末点不参加判断;2 夹角判断必须严格按照曲线方向进行
3.2 角度分段道格拉斯算法的实验分析:为验证该方法的可靠性,作者选取多组数据进行了测试并与道格拉斯-普克法进行了对比.图4为两种方法的压缩效果对比图.由图可见角度分段道格拉斯算法可以最大程度的保留曲率变化特征点
4 结论
本文针对制图综合中曲线化简中的道格拉斯普克法有可能舍掉曲率变化很大的点的问题，提出了角度分段道格拉斯算法。并将两种方法进行了对比实验，表明角度分段道格拉斯算法可以有效地保留住曲率变化特征点。但是由于该方法是在道格拉斯-普克法基础上又增加了角度与距离的计算，所以计算量进一步加大，故该法适用于对曲率变化频繁的曲线进行化简。因此为处理好减少计算量与保留地形特征点的矛盾，对地形平缓地区的曲线可采用一般的道格拉斯-普克法压缩算法，而对于地形复杂地区的各种曲线可采用角度分段道格拉斯算法。当然尽管角度分段道格拉斯压缩算法比道格拉斯-普克法压缩算法的时间复杂度有所增大，但是随着计算机计算速度的迅速增长，角度分段道格拉斯压缩算法应用是完全可行的。
参考文献 [1] 郑海鹰.计算机地图制图原理[M].郑州:原解放军测绘学院,1997.58-59.
[2] 胡鹏,黄杏元,华一新. 地理信息系统教程[M].武汉:武汉大学出版社,2002.105-106
声明①：文章部分内容来源互联网，如有侵权请联系删除，邮箱 cehui8@qq.com
声明②：中测网登载此文出于传递更多信息之目的，并不意味着赞同其观点或证实其描述，文章内容仅供参考。
加群提示：我们创建了全国32个省份的地方测绘群，旨在打造本地测绘同行交流圈，有需要请联系管理员测小量（微信 cexiaoliang）进群，一人最多只能进入一个省份群，中介人员勿扰
