曲线简化的各种计算方法及比较分析

杨红雷1，陈 杰2

（1．长安大学地测学院，陕西西安 710000；2．山西大同大学地测与安全工程系，山西大同 037003）

作者简介：杨红雷（1991－），男，长安大学地测学院硕士研究生，测绘工程专业。

陈 杰（1982－），男，山西临汾人，讲师，硕士，毕业于中南大学地图学与地理信息系统专业。

摘 要：地图综合是当前国际GIS和制图学领域的一个重要研究问题，化简是地图综合的一类基本算子，线要素是地图综合操作的主要对象，又是基础的并且至关重要的要素。论文首先归纳和总结常用的曲线简化的算法；然后，以一境界线为实验对象，结合常用的几种简化算法对其进行不同程度的简化；最后，分别从几个指标来评价各方法的优劣。

关键词：曲线化简；算法比较；分析评价

Abstract：Map generalization is an international field of GIS and Cartography important research issue currently．Simplification is a map of a class of integrated basic operator．Line feature is not only the main object map integrated operation，but also the basic and essential elements．Firstly，induction and summarized common curve simplification algorithm；Then，as experimental subjects to a boundary line，combined with several commonly used simplified algorithm to simplify the different degrees；Final－ly，from several indicators to evaluate the pros and cons of each method respectively．

Key words：curve simplification；algorithm comparison；analysis and evaluation

1 引 言

随着地理空间信息应用领域不断扩展，地图综合服务需求也变得的多样化。线要素是地图综合操作的主要对象，一般地图内容中线要素可占80％以上。现今简化算法的主要共同特征是对节点或特征点的数据进行压缩，剔除和删减不必要的点。

一般来讲，考虑的曲线要素都在二维平面内进行操作。在实际操作中，对于信息量很大的要素，简化是必要的。简化时，目的是为了避开反映特征的点要素的丢失，以保持线性图形特征的形态。典型的且应用广泛的方法有道格拉斯－普克（Douglas－Peucker）算法［1］、垂距法［2］、光栏法（偏角法或扇形法）［3］、角度法［4］、垂比弦法［5］、弧比弦算法［6］以及针对不同方法的相应改进等。每种方法都有其本身的优点，对于不同的曲线要素有不同的算法进行，这由它们本身所存在的局限性和曲线本身特征所决定。无论是什么方法，其本质上都是为了压缩数据量，优化曲线的化简过程，更合理保持图形基本形态特征。在图形制作过程中，面临的边界线、道路线、河流以及海岸线等都需要涉及曲线简化，简化在地理信息系统、地图学以及计算机方面具有广阔的应用前景，它的研究具有十分重要的理论意义和应用价值。

论文首先介绍了典型的四种曲线简化的算法，然后，分别从不同的评价指标来对给定的曲线简化的效果进行评价，最后，分析了各简化方法优劣及适用条件。

2 化简算法

2．1 道格拉斯－普克法（Douglas－Peucker）

该方法简化过程：连接首末节点形成一条直线，求得所有节点的垂直距离，找到最大值M，再与容差D比较：如果M小于D，剔除中间所有的点；如果M大于等于D，保留M处的节点，以该点为边界点，将曲线一分为二，重复操作，直至结束。

该算法是一种整体算法，这样可以更好地保证图形的整体效果，将重要节点保留，使图形变形稳定，保持图形形态特征。道格拉斯－普克算法能准确剔除不重要的节点，保证图形整体精度。由于该算法为递归算法，压缩数据时比较复杂，也是其不足之处。

2．2 垂距法

垂距法的简要思路：依次连接由相邻三节点组成的三元组，求得中间点的垂距，跟设定参数最大距离D相比：如果M小于D，删除中间点；如果M大于等于D，保留并将其作为下一个三元组的第一个点，依次继续处理，最终计算到末点结束。

垂距法算法简单，易于操作。但由于其为局部算法，每次只是从一个三元组考虑，不能整体把握图形特征，于是化简中可能出现图形特征的较大改变。就算是设定的最大距离比较小，但由于相邻点间变化不大，也可能造成中间的最大值点被删掉，图形特征完全反映不出来。综合考虑，对于线要素的化简，垂距法要根据实际条件来使用，以达到化简效果。

2．3 光栏法

光栏法的理解从偏角或扇形的概念入手。在处理曲线时，先在曲线上做一个扇形，也可看成是偏角，得到一个区域，通过判断节点是否在划定的区域内选择节点去留。下面通过图形解释，如图1所示：

图1 光栏法示意图

（1）首先在P1处确定扇形区域。设定d为参数，过P2做P1P2的垂线，在d／2处交于两点，跟P1相连，确定扇形或偏角区域。（2）接着跟踪第三点，确定第三点的位置。如果该点在锁定范围内，删除第二点，然后以第三点为原第二点，重复1操作中的步骤。（3）如果新的点又跑出该区域，则由新的边界交点替代原交点。（4）重新进行以上操作，若节点在范围内，重复2步骤，直至有节点在所划定区域外为止。（5）若节点在所划定范围外，则以该节点的前一节点为初始，开始重复以上操作，直至结束。

2．4 角度法

该方法的基本思想是：每次顺序取曲线上的三个点，计算有三个点组成的夹角X，并与给定的最大角度Y进行比较：如果X大于等于Y，则将中间的点删除；如果X小于Y，保留该点。之后依次顺序进行处理，直至结束。如图2所示：

（1）首先，将节点P1剔除掉，那么，现在我们看到的是节点线要素P0P1P2变成P0P2，曲线方向改变大小为∠1＋∠2＝∠①；（2）现在，假若去掉的是节点P2，曲线方向改变大小为∠3＋∠4＝∠②；（3）同样的，节点P3被删除，曲线方向改变大小为∠5＋∠6＝∠③。从节点线要素方向控制的角度，节点是否重要主要的判断标准为节点与前后相邻节点夹角的补角大小。补角越大，节点对曲线的转折作用越大，节点越重要，选择保留。

图2 基于角度的节点重要性程度

3 评价指标

线要素简化算法评价指标有从局部的位置精度描述，也有侧重线要素的整体形态结构。本文主要是比较简化前后线要素的形状逼近程度，重点趋于几何精度的评价标准［7］。评价算法的好与不好，主要比较在简化程度相同时，能保持较高的几何位置精度，即能够更好地保持图形形态特征［8］。对于线状要素化简算法的评价化简算法一般从面积差、弯曲度、最大拐角比率、化简变化趋势、化简结果一致性和自相交性等方面来评价［9］。此间，关于面积差、弯曲度和最大拐角比率3个标准，无论用什么方法化简，都必须选取合适的参数，使得曲线化简前后的节点个数大致相等，若节点数相差很多，就没法比较，无可比性。

这里最后加几个评价指标图来说明一下。

4 实例分析

本实验选用内蒙古1∶1000万边界线（初始节点为2025个），如图3所示。针对该边界线，分别用道格拉斯－普克法、光栏法、垂距法、角度法对其进行简化，采用相同的压缩比率以确保保留相同数量的节点，来进行比较分析。化简采用压缩比率为32∶1。

由于初始节点的数据量足够大，因此各种方法化简过程中节点个数相差的极个别个数可忽略不计，对比较分析几乎无影响。

对应的面积如表1：

表1 不同方法在相同压缩比率下的化简面积对比

图3 不同方法在相同压缩比率下的简化对比

明显看出化简保留线性特征最好的是道格拉斯－普克算法，然后依次是光栏法、垂距法、角度法；道格拉斯－普克法和光栏法能较好的保持图形特征，面积形变较小，面积保持较稳定，而垂距法和角度法较差。

随着压缩比率不断增大，各种方法出现的面积对应的曲线变化趋势如图4：

图4 4种方法的化简变化趋势对应的曲线对比

由图4的曲线变化趋势可知：（1）随着压缩比的增大，道格拉斯－普克算法和光栏算法面积变形较稳定；（2）角度法在一定的范围内较稳定，当超过一定的压缩比率，面积变形逐渐变大；（3）垂距法的面积变化波动相对比较随机，不稳定。同时，可知垂距法受初始图形的形状因素的影响较大。

化简变化趋势能明显检验化简适用性。判断标准是曲线化简后的点数是否呈单调变化。根据如图5，能够比较出：（1）道格拉斯－普克算法和光栏算法的在面积变形稳定的前提下，化简变化趋势的稳定性也高；垂距法的线性程度相对较弱；（2）角度法面积稳定时，压缩比率小，而当化简变化趋势线性化程度高时，面积变形较大。

图5 4种方法的化简变化趋势

图5是对应图4面积变形下4种方法的图表节点变化统计的综合比较，该趋势比较反映的是一个线性化程度。化简趋势的比较主要看的是各自化简方法本身节点的单调程度。因此，我们在进行化简趋势的分析时，在一定意义上，直观明了。

在化简过程中，对于角度法的化简中，出现了交叉的现象。如图6所示：

图6 化简过程中所出现的自相交现象

经过查阅文献资料等，发现对于很多种方法均存在自相交现象，如道格拉斯－普克法和光栏法。因此，本实验对于角度法的自相交现象并非偶然，对于特定的曲线节点，化简出现自相交现象可通过一定的方法解决。

就道格拉斯－普克法和光栏法之间的比较不很明显。因此，对这两种方法进行进一步对比，通过面积差和弯曲度进行对比分析。

令初始面积S0，化简后面积Si，面积差为ΔSi。则计算公式为

ΔSi＝Si－S0 　（1）

又：令始曲线的长度L，化简后的长度Li，弯曲度（反映曲线迂回特征）的计算公式：

ΔLi＝Li／L0 　（2）

由表2明显看出，在相同压缩比率的情况下，道格拉斯－普克法比光栏法的面积差小一个数量级，化简后的整体偏移量要比光栏法小。在相同的压缩比率的情况下，道格拉斯－普克法的弯曲度比光栏法的弯曲度大，化简线状要素更接近原 始曲线的线划特征。

表2 相同压缩比率下面积差和弯曲度的比较

5 结论及不足

道格拉斯－普克法在曲线化简中能够整体的保持图形的特征形态，因此一直以来作为跟其他化简算法及改进算法比较的经典算法有其合理性。光栏法的化简效果也不错。对比各种分析方法，关于面积差、弯曲度等几何精度方向的评估以及位置精度评估，虽操作手段不同，但基本思想如出一辙。在实际运用过程中，根据不同需求有所侧重地选择合适的化简及评价方法。

该实验整体上能客观反映分析与评价，但还是存在一定的局限性。几何精度并不是判断化简效果优劣的唯一指标。化简效果时常要兼顾曲线形状特征、空间关系等。对于不同的图形，有不同的图形特征，进行比较评价时，评价标准必定不完善，在处理过程中可能会出现偏差。此外，对于不同的化简算法，都存在优劣性，面对不同的地理特征、地形要素等，对于化简算法的选择要综合考虑，考虑算法自身对不同线要素、比例尺和设定参数以及算法的适合用性等，并采取相应的手段进行比较分析。

参考文献

［1］ Douglas D，Peueker T．Algorithms for the reduction of the number of points required to represent a digitized line of its caricature［J］．1973，10（2）：112－123．

［2］ 彭认灿，董箭．垂距法与道格拉斯－普克法删除冗余顶点效率的比较［J］．测绘通报，2010，3（1）：66－67．

［3］ 于晓艳．等高线简化法评价体系研究［硕士学位论文］［D］．南京：南京大学，2011．

［4］ 刘慧敏．地图空间信息量的度量方法研究［博士学位论文］［D］．长沙：中南大学，2012．

［5］ 邓敏，陈杰，李志林，等．线目标化简中节点重要性度量方法比较及垂比弦法的改进［J］．地理与地理信息科学， 2009，25（1）：40－43．

［6］ 刘慧敏，樊子德，徐震，等．曲线化简的弧比弦算法改进及其评价［J］．地理与地理信息科学，2011，27（1）：45－48．

［7］ 朱鲲鹏，武芳，陈波，等．基于约束条件的线要素化简算法质量评估［J］．测绘科学，2007，32（3）：28－29．

［8］ 武芳，朱鲲鹏．线要素化简算法几何精度评估［J］．武汉大学学报信息科学，2008，33（6），600－603．

［9］ 陈波，朱鲲鹏，薛本新．现状要素化简算法的分析评估［J］．测绘科学技术学报，2007，24（2）：121－124．