李世宝，陈 通，刘建航，陈海华

(中国石油大学(华东) 计算机与通信工程学院，山东 青岛 266580)

基于交叉点的道路曲线化简算法研究

李世宝，陈 通，刘建航，陈海华

(中国石油大学(华东) 计算机与通信工程学院，山东 青岛 266580)

现有的曲线化简算法不能很好地化简具有交叉路口的道路曲线，针对这一问题提出一种基于交叉点的道路曲线化简算法。算法分为预化简和修正化简两个阶段：首先识别并得到曲线上的分段点，利用相邻的分段点作为道格拉斯-普克算法的首尾点对曲线进行化简，得到预化简的结果；然后对于交叉点引入偏差阈值ε，通过判断道路曲线交叉点与化简后交叉点的距离与偏差精度ε的大小关系来确定该交叉点的化简与保留，如果保留或者化简后的道路曲线没有交叉点那么将原交叉点作为分段点对此段曲线进行重新化简。理论分析与实验结果表明，文中算法能够有针对性地保留或化简道路交叉点以及保持曲线化简后的形态特征。

交叉口；分段点；偏差阈值ε；道格拉斯-普克算法

近年来,随着智慧城市、地理信息系统在各个领域的不断深入，制图综合成为众多学者研究的热点[1]。曲线是地图数据最基本的组成要素之一，在地图数据中占据了很大的比例。因此，对于曲线的化简一直是地图自动综合最重要的问题。在对线状要素进行化简时，首先要识别和提取曲线上重要的特征点，然后对曲线进行化简。因为对于曲线化简不仅仅只是关注曲线的压缩率，曲线化简后的形态也是衡量曲线化简算法的一个重要指标。对于道路曲线，不仅仅曲线上重要的点为特征点，交叉点也是重要的特征点。因为交叉点是维持道路曲线交错关系的点。

目前还没有针对具有交叉点的道路曲线的成熟的化简算法，传统的曲线化简算法主要有光栅法、垂距法[2]、角度限值法[3]、道格拉斯-普克算法[4]等，其中道格拉斯-普克算法是一种全局的化简算法而广泛用于曲线化简中。该算法的主要思想是：设曲线是有P1,P2,P3,…,Pn等n个点组成，P1,Pn是曲线的首尾点。依次计算曲线上所有的点Pi(i=2,3,…,n-1)到首尾点P1,Pn构成的直线距离，记为Di(i=2,3,…,n-1),取其中最大的距离Dmax,如果Dmax小于设定的距离阈值D，则删除P1，Pn内的所有的点，反之，则把最大距离对应的点作为分段点，把曲线分为两段，然后在每一段上用同样的方法进行处理，最后保留的点就是压缩后的结果。该算法实现比较简单，作为一种全局的曲线化简算法能在化简后一定程度上保持化简后曲线整体形态，但是还存在很多缺陷：一些曲线上的点直接被化简掉，其位置信息、重要程度并没有考虑[5];化简后曲线上一些重要的特征点丢失，不利于化简后曲线整体的保持，道格拉斯-普克算法采用的是单一阈值，不能适应各种复杂的情况[6]；化简后的曲线有可能相交[7]。因此，对于道格拉斯-普克算法，很多学者对其进行了改进：于靖等[8]提出了面向自然岸线抽稀的改进道格拉斯-普克算法，把曲线上重要的凸点作为曲线化简的分段点，使用道格拉斯-普克算法进行化简；张振鑫[9]等提出了多种数据化简算法之间的对比，通过对比指出了数据化简研究发展的趋势；李朝奎等[10]以优化线状要素的化简综合为目标，对道格拉斯-普克算法进行了改进，改进后的算法在保留了曲线的特征点后再对其进行化简；巨正平等[11]提出了附有限制条件的逐点压缩法，在满足给定限差下能够很好地考虑了化简曲线之间的相互关系；张志伟等[12]通过建立距离阈值与化简后的点数的最优拟合函数，分析拟合函数的性质确定距离阈值，从而更好地保留化简后曲线形态，取得了比较好的化简结果。

对具有交叉点的道路曲线进行化简时，道路曲线的交叉点和化简后保持曲线形态的点为重要的特征点，这两类点在化简时都要进行处理，上述对于曲线化简算法的改进主要针对曲线上起伏比较大的特征点在化简中的保留，并没有考虑到除了这类特征点以外的点如道路交叉点的保留与化简。虽然何海威[13]提出了一种采用弯曲避免化简后道路的冲突，但仅仅是把所有的道路交叉点都保留下来，并没有针对道路交叉点作进一步的分析与处理。本文针对目前具有交叉路口的道路曲线化简的不足，提出了一种基于交叉点的道路曲线化简算法。把道路曲线上特征点分为两类，然后针对这两类特征点分别进行处理，在保证化简后道路曲线形态特征的同时保留符合实际需求的道路曲线交叉点。

1 改进的曲线化简算法

1.1 算法的思想

对于包含多条道路曲线的复杂道路网，每一条道路曲线在空间数据库中一般都是独立存取。道路曲线之间存在着交错关系，而交叉点是维持不同道路曲线拓扑关系的关键点，传统的算法是化简或者保留所有的道路交叉点。本文认为对于化简后交叉点的偏移量小于偏差阈值的可以化简。因此，对于一部分道路交叉点在不影响实际使用的情况下可以被化简。若使用传统的道格拉斯-普克算法对整段道路曲线进行化简，单一的阈值不能保证曲线的各个部分都能得到最优化简，而且也不能够针对交叉点进行化简。为了在化简后能更好地保持道路曲线的形态特征和交叉点的位置，在化简时应对这两类点单独进行处理，本文提出了基于交叉点的道路曲线化简算法。算法主要包括：①选取曲线上重要的特征点；②选取和处理道路曲线交叉点。

1.2 曲线上重要特征点的选取与处理

对于曲线上重要的特征点，要选取对曲线整体形态影响比较大的点，采用基于m阶邻居坐标点的方法[14]来确定影响曲线形态的重要的特征点，以此为分段点，把道路曲线分成许多子曲线，在每段子曲线中把分段点作为道格拉斯-普克算法的首尾点进行化简，利用基于最小二乘法的曲线拟合方法[15]得到每段子曲线中阈值与化简后点数的关系，通过分析阈值与点数的拟合曲线，找到拟合曲线上曲率最大的点对应的阈值作为每段子曲线中最优阈值，分别对每段子曲线进行化简。

1.3 交叉路口特征点的选取与处理

首先分析道路网中所有道路曲线的拓扑关系，获取所有道路曲线的交叉点。然后设置满足实际需求的偏差阈值ε，对于化简后的道路曲线的交叉点分为两种类型，第一种是化简后的道路曲线有交叉点，另一种是化简后的道路曲线没有交叉点。

对于第一种化简后的道路曲线有交叉点的类型，如果交叉点化简前后的位移差D<ε,则化简后交叉点不用处理，化简掉该交叉点并不会对实际的使用造成较大的影响，而如果D>ε，交叉点被化简会影响实际的使用需求，要对此交叉点进行处理。具体处理方法如图1所示,P1(X1,Y1)、P2(X2,Y2)、P3(X3,Y3)、P4(X4,Y4)为预化简过程的分段点，其坐标是已知的，P5(X5,Y5)为原始交叉路口，P6为化简后道路曲线新的交叉路口，其坐标的计算方法为

通过求解方程组得到化简后交叉点P6的坐标(X6,Y6)，进而得到化简前后交叉点的偏移距离D,计算方法如下：

若D<ε,认为化简后的交叉口满足精度的要求，不需要对化简后的交叉点做处理。若D>ε,则把原交叉点P5作为分段点，然后对由点P1，P2，P3，P4组成的曲线段P1P5，P2P5，P3P5，P4P5进行修正化简，这样就保证了道路曲线交叉点P5不被化简。

图1 化简后曲线相交的交叉路口特征点的处理过程

对于第二种化简后的道路曲线没有交叉点的类型，则该交叉点不能被化简，因为这种类型的交叉点是维持两条道路曲线拓扑关系的关键点，如果被化简两条道路曲线就由相交变成了相离，导致原始到道路曲线之间的空间关系发生较大变化。如图2所示,两条道路曲线化简后形成的线段P1P2,P3P4没有相交，则以P5为分段点对此段曲线重新进行修正化简，这样交叉点P5就得了保留，道路曲线的拓扑关系也得到保持。

图2 化简后曲线不相交的交叉路口特征点的处理过程

2 算法实现

算法具体步骤如下：

1)针对道路网中的道路曲线进行相交和自交的拓扑分析，获取到道路网中所有的交叉点。

2)在道路网中选取其中的一条道路曲线。然后从曲线的点Pi(i=2,3,…,N-1)中选取出特征点作为曲线的分段点。

3)以相邻的分段点作为道格拉斯-普克算法的首尾点，利用基于最小二乘法的曲线拟合方法得到每一段曲线的最佳阈值，对分段后的曲线进行化简。

4)重复步骤2)～4)把道路网中所有的道路曲线都化简完毕，至此得到预化简后的曲线。

5)分析交叉点所在线段化简后是否相交，如果不相交执行步骤6)，如果相交则判断道路曲线交叉点与化简后交叉点的距离D与偏差阈值ε的关系，如果D<ε则此交叉点可以化简掉，如果D>ε则此交叉点不能化简，以此原交叉点为分段点，对相邻的线段重新进行化简。

6)化简后的曲线不相交则交叉点不能被化简，以原交叉点为分段点对相邻的线段重新进行修正化简。

7)重复执行步骤5)，直到所有道路交叉点处理完毕。

3 实验与结果分析

为了验证本文算法的有效性，在实验中随机选取一组道路曲线，利用本文所提算法与传统的道格拉斯-算法进行化简。通过化简后的图形来说明该算法的有效性。

图3、图4展示了传统的道格拉斯-普克算法与本文算法对具有交叉路口的道路曲线的效果对比。图3所示是传统道格拉斯-普克算法对道路曲线的化简结果，由实验结果可知，传统的道格拉斯-普克算法在对道路曲线进行化简时，只是针对每一条道路曲线进行化简，并没有考虑道路曲线之间的拓扑关系，P1，P2，P3，P44个交叉点都被化简，而且曲线上一些重要的特征点也没有保留。同时由于交叉点P2被化简，交叉点P2连接的两条道路曲线由相交变为相离，道路曲线的拓扑关系发生了较大的改变。由此可见在对道路曲线进行化简时，传统的道格拉斯-普克算法不能满足实际的应用需求。

图3 传统道格拉斯-普克算法化简结果

图4 本文算法化简结果

图4所示的是本文算法对道路曲线化简的结果，由图4(a)可知，当偏差阈值ε=1 mm时，交叉点P1，P3化简之后的位置偏移小于ε，满足偏差阈值的要求，因此，交叉点P1，P3被化简。交叉点P2由于化简后的道路曲线不相交而不能被化简。交叉点P4由于化简前后的距离大于偏差阈值ε而没有被化简。使用本文算法在ε=1 mm对道路曲线进行化简后，交叉点P2，P4没有被化简，P1，P3被化简掉，同时由于交叉点P2没有被化简两条道路曲线化简后的拓扑关系得到了保留。由图4(b)可知，偏差阈值ε=2 mm，交叉点P1，P3，P4由于位置偏移都满足精度要求而被化简，交叉口P2由于化简后道路曲线不相交而保留，维持了道路曲线之间的拓扑关系，同时曲线上一些重要的局部特征点也得

到了保留。因此，在使用本文算法对道路曲线进行化简时，并不是保留所有的道路交叉点，而是引入偏差阈值ε概念，确定交叉点是否保留，在实际需求中可以通过设置偏差阈值ε的大小，以满足不同的化简精度需求。

4 结束语

对于道路曲线而言，道路曲线的交叉点作为维持道路拓扑关系的关键点，在对其进行化简时，不能简单地保留或化简，应该单独进行分析、处理。传统的道格拉斯-普克算法在对道路曲线进行化简时并没有考虑到道路曲线交叉点的特殊性，不能满足道路曲线实际的化简需求。本文通过寻找曲线上的特征点作为分段点及引入偏差阈值ε，设计并实现了一种基于交叉点的道路曲线化简算法，通过引入偏差阈值概念使得本文算法不同于传统的算法对交叉点全部保留或者删除，而是通过分析交叉点化简后的特征选择性的保留与化简，使用本文算法对于密集道路网进行化简时，能够在保证道路曲线局部形态的前提下，科学有效地化简或者保留交叉点，提升化简的压缩率。

[1] 苏宏瑞,崔先国,彭玉艳.制图综合中基于中心地思想的线状要素自动取舍算法研究[J].测绘科学,2007,32(1):40-42.

[2] 彭认灿,董箭,郑义东,等.垂距法与道格拉斯-普克法删除冗余顶点效率的比较[J].测绘通报,2010(3):66-67.

[3] 徐新.增强型矢量数据压缩算法的设计与实现[J].计算机应用研究,2007,24(12):393-395.

[4] POIKER T,DOUGLAS D H.Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature[J].Cartographica the International Journal for Geographic Information & Geovisualization,1973,10(2):112-122.

[5] TONG X,XU G.A new least squares method based line generalization in GIS[C]// Geoscience and Remote Sensing Symposium,2004.IGARSS’04.Proceedings.2004 IEEE International.IEEE,2004:2912-2915 vol.5.

[6] CARMONA-POYATO A,MADRID-CUEVAS F J,MEDINA-CARNICER R,et al.Polygonal approximation of digital planar curves through break point suppression[J].Pattern Recognition,2010,43(1):14-25.

[7] 张青年,廖克.基于结构分析的曲线概括方法[J].中山大学学报(自然科学版),2001,40(5):118-121.

[8] 于靖,陈刚,张笑,等.面向自然岸线抽稀的改进道格拉斯—普克算法[J].测绘科学,2015,40(4):23-27.

[9] 张振鑫,张维,刘嫔,等.矢量地图数据简化研究进展[J].测绘工程,2016,25(6)：10-14.

[10] 李朝奎,骆文芳,陈果,等.渐进式改进的线要素简化算法探讨[J].测绘科学，2015,40(11):123-126.

[11] 巨正平,王勇,郭广礼,等.附有限制条件的逐点压缩算法的设计与实现[J].测绘通报,2009(4):25-28.

[12] 张志伟,暴景阳,肖付民,等.基于Ping的Douglas-Peucker法抽稀阈值优化选取[J].海洋测绘,2015,35(2):9-12.

[13] 何海威,钱海忠,王骁,等.采用弯曲进行道路化简冲突避免的方法[J].测绘学报,2016,45(3):354-361.

[14] 杨志坚.顾及局部特征的线状要素制图综合[J].测绘科学,2016,41(4)：118-123.

[15] 王晓理,陈双军,魏斌,等.曲线拟合的Douglas-Peucker算法阈值优化选择[J].测绘科学技术学报,2010,27(6):459-462.

[责任编辑：刘文霞]

A road curve simplification algorithm based on intersection point

LI Shibao，CHEN Tong，LIU Jianhang，CHEN Haihua

(College of Computer and Communication Engineering，China University of Petroleum，Qingdao 266580，China)

The existing algorithms on curve simplification can’t simplify the road curve with intersections.To solve this problem,this paper proposes a road curve simplification algorithm based on intersections.The first stage is called pretreatment stage,which identifies the segmentation points of a curve,and treats the adjacent segmentation points as beginning and end points of Douglas Peucker algorithm to get the simplified pretreatment results.The second stage is called correction simplification stage,which determines the simplification or deviation of intersections,by introducing a deviation threshold ε,and comparing it with the distance between before-simplification and after.If the intersections are retained or there are no intersections after simplification,redo the simplification by using the previous intersections as segmentation points. Theoretical analysis and experimental results show that the proposed algorithm can retain or simplify the adjacent points purposefully,meanwhile keeping the morphological characters of curves after simplification.

intersection feature point;segmentation point;deviation threshold;Douglas-Peucker algorithm

著录：李世宝，陈通，刘建航，等.基于交叉点的道路曲线化简算法研究[J].测绘工程，2017，26(7)：1-4，11.

10.19349/j.cnki.issn1006-7949.2017.07.001

2016-07-18

山东省自然科学基金面向项目(ZR2014FM017);中央高校基本科研业务费专项资金资助项目(15CX05025A);青岛市科技创新计划(15-9-80-jch);青岛市黄岛区科技发展计划项目(2014-1-45)

李世宝(1978-)，男，副教授，硕士.

P208

A

1006-7949(2017)07-0001-04