简化线状要素算法实现及比较研究
2017-09-09陈炫岩刘福江
陈炫岩+刘福江
摘 要：在GIS研究中，地图矢量数据通常用线状图形表达，研究主要集中在线状要素自动简化模型建立上。为对比不同线状要素简化算法的特点，分别对面积和道格拉斯匹克两种线要素简化算法进行了简化，并通过横向和纵向对算法进行比较。实验结果发现，道格拉斯匹克算法随简化率升高，保留点下降速率相对柔和，在相同简化率的情况下，道格拉斯匹克算法单位长度偏移更小。因此，從整体上考虑，道格拉斯匹克算法性能更优。
关键词：制图综合；线状要素简化；基于面积的算法；道格拉斯匹克算法
DOIDOI：10.11907/rjdk.172089
中图分类号：TP312
文献标识码：A 文章编号文章编号：1672-7800（2017）008-0029-03
0 引言
空间数据多尺度表达问题是GIS研究的重点，也是地图自动综合的瓶颈。地图矢量数据都可用线状图形来表达，这就使多尺度研究的焦点主要集中在线要素自动简化模型的建立上。许多学者已经对此问题作了大量研究，Douglas DH和Peucker TK[1]提出DP算法，其采用首尾相连进行迭代化简；Li Zhi-lin和Openshaw[2]提出基于客观综合的自然规律的线划要素化简的方法；VisvaLingam 和Whyatt[3]提出基于最小面积的重复式点删除方法；Salfeld[4]提出基于逻辑一致的Douglas算法；郭庆胜[5]提出渐进式化简算法；武芳[6]提出面向地图基于遗传算法的线要素化简算法等。线简化算法种类繁多[7-8]，本文以道格拉斯匹克（DP）算法和最小面积算法为例，纵向研究每种算法的简化特点，并横向比较两种算法的优劣。
1 算法概述
1.1 基于面积的线要素简化
迭代计算相邻3点围成面积，如果大于先前设定的面积，则保留这3个点，并向下遍历；若小于先前设定的面积，则删除中间的点，继续向下遍历选点，直至遍历整条线段。
1.2 道格拉斯匹克线要素简化
先选择首尾两点连接，遍历两点之间的所有点，找到距离首尾连线垂距最大的点，若最大垂距小于设定阈值，则删除中间的所有点；若最大垂距大于设定阈值，则保留此点，并将其与首尾相连，得到两根新的线段。分别对新线段进行如上操作，直至判断完整个曲线上的点。
2 研究方法及技术路线
首先明确线状要素简化的原因，是为了满足不同比例尺下的地图信息表达[9-10]。首先明确一个概念——简化率，因为线状要素简化的方法是先将其降维，转化为一系列离散的点状要素，再合理选取这些描述线要素的点要素，重新形成简化后的线要素。所以，简化率定义为：
α=Ndelete/Nsum（1）
其中，α为简化率，Ndelete为删除的点数，Nsum为简化前的总点数。
另外，在不同比例尺下，尽管是同一条线段，也要用不同数量的点对其进行描述，即地图综合。所以，假设曲线原图比例尺为1：n，简化前的总点数为Nsum，若要转换到1：N比例尺下，应该保留的点数Nreserve为：
Nreserve=nN×Nsum（2）
又有：
Ndelete=Nsum-Nreserve（3）
所以：
Ndelete=Nsum×1-nN（4）
又有：
α=Ndelete/Nsum（5）
所以：
α=1-nN（6）
基于以上公式，首先纵向评估每种算法在不同简化率下的化简效果，得到对应的阈值和保留点数Nreserve的对应关系，在Excel中拟合曲线，得到两者之间的函数关系，进而得到阈值与比例尺之间的函数关系，定量描述出两种简化算法的简化特点。至此，可以实现在比例尺无级缩放条件下的阈值选择。
另一方面，横向对比两种方法，在同样的简化率下，用两种方法分别对同一条曲线进行简化，得到简化后的曲线。将简化后的曲线和原曲线在ArcGIS中打开，计算出相交面积，通过控制简化率一致，从面积差异来对比评估两种方法的简化效果。
3 简化结果纵向分析
3.1 基于面积的线要素简化
3.1.1 实验数据及流程
选取一条初始点数为164的曲线作为实验数据，将其坐标值导入.txt文件，使用C++程序读入文件，经过简化算法后输出到.txt文件，再导入Excel中画出曲线。
3.1.2 简化结果
选取不同阈值，得到不同保留结果，计算出简化率，进而求出相应的比例尺分母放大倍数，即找到此方法阈值对应的缩放尺度。另外，得到设定阈值和保留点数的对应关系后，根据对应关系产生的散点，在Excel中使用幂函数进行拟合，显示拟合方程，即可得到由离散点到连续化的映射，从而得到比例尺无级缩放条件下对应的简化阈值。
基于以上对应关系，得到设定阈值与保留点数之间的散点关系，在Excel中将散点进行拟合，得到初步的连续函数。在此函数中，即可得到比例尺无级变化下对应的阈值。此函数关系为：
y=2 125.1x-0.396（7）
相关系数为：
R2=0.993 7
可以发现，在基于面积的线要素简化方法中，保留函数与幂函数相近，在初期保留点数下降较快，但是随着阈值不断增大，保留点数缓慢收敛于2，即首尾两点，相应函数表达式如上文所示。
3.2 基于道格拉斯匹克的线要素简化
3.2.1 实验数据及流程
数据及流程同3.1.1，采用同一根线控制变量，研究简化特点。
3.1.2 简化结果
基于以上对应关系，同样可以得到在道格拉斯匹克算法下设定阈值与保留点数之间的散点关系。在Excel中将散点拟合，得到初步的连续函数，此函数关系为：endprint
y=317.31x-0.57（8）
相关系数为：
R2=0.993 1
对比基于面积的线简化算法，道格拉斯匹克算法的保留函数柔和很多，下面分析两种保留函数保留点数下降的速率。
分别对两个保留函数求导，得到其导函数，可知导函数为其简化速率。两者相除，则可知简化速率的相对倍数。
基于面积的简化方式的简化速率为：
v1=-841.539 6x-1.396（9）
基于道格拉斯匹克算法的简化方式的简化速率为：
v2=180.900 9x-1.57（10）
所以，面积简化算法的简化速率为DP算法的v1/v2倍：
v1v2=4.651 9x0.174（11）
4 简化结果横向分析
选择简化率为80%的两种算法进行简化结果的横向比较分析。基于面积的简化线阈值为40，简化率为80%，保留点数为32；基于道格拉斯匹克的简化线阈值为50，简化率为80%，保留点数为32。
将简化结果与源数据相交，求得相交的面积区域总和。统计结果为40个相交区域，面积最大值为49 918.111 021，面积最小值为49.419 953，面积总和为479 090.813 592，单位长度面积偏移量为20.020 091 4。
同理，将基于道格拉斯匹克算法的简化结果与源数据相交，求得相交的面积区域总和。统计结果为56个相交区域，面积最大值为62 933.889 761，面积最小值为15.621 068，面积总和为330 143.467 505，单位长度面积偏移量为13.795 928 05。
以下定量比较两种方法的简化效果，统计结果如表3所示。
经过分析对比可以得到，当线简化的简化率相同时，基于面积简化的效果不如基于道格拉斯匹克算法简化的结果。可以从单位长度面积偏移量对比，也可以从相交区域的面积总和值进行对比。但是从最大值和最小值的角度来看，基于面积的算法是从局部进行简化的，而道格拉斯匹克算法是从空间分布整体进行简化的。因此，基于道格拉斯匹克算法的Max值大于基于面积算法的Max值。
5 结语
由分析结果可以得到，基于面积简化的偏移面积总和与基于道格拉斯匹克算法的简化线的偏移面积总和之差为：
△Sum=Sum（Area）-Sum（DP）
当两个算法简化率相同时，可通过计算面积之差来比较简化效果。这里选择简化率为80%时的面积数据，得到△Sum=6.224 163 4。当简化率相同且达到一定值时，基于面积和基于道格拉斯匹克算法的简化面积偏移量相差并不大，但是可以定量反映出两种简化效果的差别。
本文通过建立每一种简化算法对应的阈值T和保留点数Nreserve的函数关系，近似拟合曲线得到一般规律。利用一般规律来确定简化线的阈值大小，进而确定对应的简化率以及缩放的比例尺等。下一步可以继续研究当简化率大小不同时，两种算法简化面积偏移的变化，也可以继续模拟拟合曲线，以进一步定量研究两种算法的优劣。
参考文献：
[1] DOUGLAS DH，PEUCKER TK.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].The CanadianCartographer，1973，10（2）：112-122.
[2] ZHILIN LI，STAN OPENSHAW.Algorithms for automated line generalization based on a natural principle of objective generalization[J].Geographical Information Systems，1992，6（5）：373-389.
[3] MVISVALINGAM，JD WHYATT.Line generalization by repeated elimination of the smallest area[J].The Cartographic Journal，1993，30（1）：46-51.
[4] SAALFELD A.Topologically consistent line simplification with the douglas-peuckeralgorithm[J].Cartography and Geographic Information Science，1999，26（1）：7-18.
[5] 郭慶胜.线状要素图形综合的渐进方法研究[J].武汉测绘科技大学学报，1998，23（1）：52-56.
[6] 武芳，钱海忠，邓红艳，等.面向地图自动综合的空间信息智能处理[M].北京：科学出版社，2008：164-170.
[7] 刘鹏程，罗静，艾廷华，等.基于线要素综合的形状相似性评价模型[J].武汉大学学报信息科学版，2012，37（1）：114-117.
[8] 雷伟刚，童小华，刘大杰.基于曲线拟合的线要素综合数据整体处理方法[J].武汉大学学报：信息科学版，2006（10）：896-899.
[9] 李霖，于忠海，朱海红，等.地图要素图形冲突处理方法——以线状要素（道路、水系和境界）为例[J].测绘学报，2015，44（5）：563-569.
[10] 邓敏，彭东亮，徐震，等.一种基于弯曲结构的线状要素Morphing方法[J].中南大学学报：自然科学版，2012（7）：2674-2682.endprint
