李世寶，陳 通，劉建航，陳海華

(中國石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院，山東 青島 266580)

基于交叉點(diǎn)的道路曲線化簡算法研究

李世寶，陳 通，劉建航，陳海華

(中國石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院，山東 青島 266580)

現(xiàn)有的曲線化簡算法不能很好地化簡具有交叉路口的道路曲線，針對(duì)這一問題提出一種基于交叉點(diǎn)的道路曲線化簡算法。算法分為預(yù)化簡和修正化簡兩個(gè)階段：首先識(shí)別并得到曲線上的分段點(diǎn)，利用相鄰的分段點(diǎn)作為道格拉斯-普克算法的首尾點(diǎn)對(duì)曲線進(jìn)行化簡，得到預(yù)化簡的結(jié)果；然后對(duì)于交叉點(diǎn)引入偏差閾值ε，通過判斷道路曲線交叉點(diǎn)與化簡后交叉點(diǎn)的距離與偏差精度ε的大小關(guān)系來確定該交叉點(diǎn)的化簡與保留，如果保留或者化簡后的道路曲線沒有交叉點(diǎn)那么將原交叉點(diǎn)作為分段點(diǎn)對(duì)此段曲線進(jìn)行重新化簡。理論分析與實(shí)驗(yàn)結(jié)果表明，文中算法能夠有針對(duì)性地保留或化簡道路交叉點(diǎn)以及保持曲線化簡后的形態(tài)特征。

交叉口；分段點(diǎn)；偏差閾值ε；道格拉斯-普克算法

近年來,隨著智慧城市、地理信息系統(tǒng)在各個(gè)領(lǐng)域的不斷深入，制圖綜合成為眾多學(xué)者研究的熱點(diǎn)[1]。曲線是地圖數(shù)據(jù)最基本的組成要素之一，在地圖數(shù)據(jù)中占據(jù)了很大的比例。因此，對(duì)于曲線的化簡一直是地圖自動(dòng)綜合最重要的問題。在對(duì)線狀要素進(jìn)行化簡時(shí)，首先要識(shí)別和提取曲線上重要的特征點(diǎn)，然后對(duì)曲線進(jìn)行化簡。因?yàn)閷?duì)于曲線化簡不僅僅只是關(guān)注曲線的壓縮率，曲線化簡后的形態(tài)也是衡量曲線化簡算法的一個(gè)重要指標(biāo)。對(duì)于道路曲線，不僅僅曲線上重要的點(diǎn)為特征點(diǎn)，交叉點(diǎn)也是重要的特征點(diǎn)。因?yàn)榻徊纥c(diǎn)是維持道路曲線交錯(cuò)關(guān)系的點(diǎn)。

目前還沒有針對(duì)具有交叉點(diǎn)的道路曲線的成熟的化簡算法，傳統(tǒng)的曲線化簡算法主要有光柵法、垂距法[2]、角度限值法[3]、道格拉斯-普克算法[4]等，其中道格拉斯-普克算法是一種全局的化簡算法而廣泛用于曲線化簡中。該算法的主要思想是：設(shè)曲線是有P1,P2,P3,…,Pn等n個(gè)點(diǎn)組成，P1,Pn是曲線的首尾點(diǎn)。依次計(jì)算曲線上所有的點(diǎn)Pi(i=2,3,…,n-1)到首尾點(diǎn)P1,Pn構(gòu)成的直線距離，記為Di(i=2,3,…,n-1),取其中最大的距離Dmax,如果Dmax小于設(shè)定的距離閾值D，則刪除P1，Pn內(nèi)的所有的點(diǎn)，反之，則把最大距離對(duì)應(yīng)的點(diǎn)作為分段點(diǎn)，把曲線分為兩段，然后在每一段上用同樣的方法進(jìn)行處理，最后保留的點(diǎn)就是壓縮后的結(jié)果。該算法實(shí)現(xiàn)比較簡單，作為一種全局的曲線化簡算法能在化簡后一定程度上保持化簡后曲線整體形態(tài)，但是還存在很多缺陷：一些曲線上的點(diǎn)直接被化簡掉，其位置信息、重要程度并沒有考慮[5];化簡后曲線上一些重要的特征點(diǎn)丟失，不利于化簡后曲線整體的保持，道格拉斯-普克算法采用的是單一閾值，不能適應(yīng)各種復(fù)雜的情況[6]；化簡后的曲線有可能相交[7]。因此，對(duì)于道格拉斯-普克算法，很多學(xué)者對(duì)其進(jìn)行了改進(jìn)：于靖等[8]提出了面向自然岸線抽稀的改進(jìn)道格拉斯-普克算法，把曲線上重要的凸點(diǎn)作為曲線化簡的分段點(diǎn)，使用道格拉斯-普克算法進(jìn)行化簡；張振鑫[9]等提出了多種數(shù)據(jù)化簡算法之間的對(duì)比，通過對(duì)比指出了數(shù)據(jù)化簡研究發(fā)展的趨勢；李朝奎等[10]以優(yōu)化線狀要素的化簡綜合為目標(biāo)，對(duì)道格拉斯-普克算法進(jìn)行了改進(jìn)，改進(jìn)后的算法在保留了曲線的特征點(diǎn)后再對(duì)其進(jìn)行化簡；巨正平等[11]提出了附有限制條件的逐點(diǎn)壓縮法，在滿足給定限差下能夠很好地考慮了化簡曲線之間的相互關(guān)系；張志偉等[12]通過建立距離閾值與化簡后的點(diǎn)數(shù)的最優(yōu)擬合函數(shù)，分析擬合函數(shù)的性質(zhì)確定距離閾值，從而更好地保留化簡后曲線形態(tài)，取得了比較好的化簡結(jié)果。

對(duì)具有交叉點(diǎn)的道路曲線進(jìn)行化簡時(shí)，道路曲線的交叉點(diǎn)和化簡后保持曲線形態(tài)的點(diǎn)為重要的特征點(diǎn)，這兩類點(diǎn)在化簡時(shí)都要進(jìn)行處理，上述對(duì)于曲線化簡算法的改進(jìn)主要針對(duì)曲線上起伏比較大的特征點(diǎn)在化簡中的保留，并沒有考慮到除了這類特征點(diǎn)以外的點(diǎn)如道路交叉點(diǎn)的保留與化簡。雖然何海威[13]提出了一種采用彎曲避免化簡后道路的沖突，但僅僅是把所有的道路交叉點(diǎn)都保留下來，并沒有針對(duì)道路交叉點(diǎn)作進(jìn)一步的分析與處理。本文針對(duì)目前具有交叉路口的道路曲線化簡的不足，提出了一種基于交叉點(diǎn)的道路曲線化簡算法。把道路曲線上特征點(diǎn)分為兩類，然后針對(duì)這兩類特征點(diǎn)分別進(jìn)行處理，在保證化簡后道路曲線形態(tài)特征的同時(shí)保留符合實(shí)際需求的道路曲線交叉點(diǎn)。

1 改進(jìn)的曲線化簡算法

1.1 算法的思想

對(duì)于包含多條道路曲線的復(fù)雜道路網(wǎng)，每一條道路曲線在空間數(shù)據(jù)庫中一般都是獨(dú)立存取。道路曲線之間存在著交錯(cuò)關(guān)系，而交叉點(diǎn)是維持不同道路曲線拓?fù)潢P(guān)系的關(guān)鍵點(diǎn)，傳統(tǒng)的算法是化簡或者保留所有的道路交叉點(diǎn)。本文認(rèn)為對(duì)于化簡后交叉點(diǎn)的偏移量小于偏差閾值的可以化簡。因此，對(duì)于一部分道路交叉點(diǎn)在不影響實(shí)際使用的情況下可以被化簡。若使用傳統(tǒng)的道格拉斯-普克算法對(duì)整段道路曲線進(jìn)行化簡，單一的閾值不能保證曲線的各個(gè)部分都能得到最優(yōu)化簡，而且也不能夠針對(duì)交叉點(diǎn)進(jìn)行化簡。為了在化簡后能更好地保持道路曲線的形態(tài)特征和交叉點(diǎn)的位置，在化簡時(shí)應(yīng)對(duì)這兩類點(diǎn)單獨(dú)進(jìn)行處理，本文提出了基于交叉點(diǎn)的道路曲線化簡算法。算法主要包括：①選取曲線上重要的特征點(diǎn)；②選取和處理道路曲線交叉點(diǎn)。

1.2 曲線上重要特征點(diǎn)的選取與處理

對(duì)于曲線上重要的特征點(diǎn)，要選取對(duì)曲線整體形態(tài)影響比較大的點(diǎn)，采用基于m階鄰居坐標(biāo)點(diǎn)的方法[14]來確定影響曲線形態(tài)的重要的特征點(diǎn)，以此為分段點(diǎn)，把道路曲線分成許多子曲線，在每段子曲線中把分段點(diǎn)作為道格拉斯-普克算法的首尾點(diǎn)進(jìn)行化簡，利用基于最小二乘法的曲線擬合方法[15]得到每段子曲線中閾值與化簡后點(diǎn)數(shù)的關(guān)系，通過分析閾值與點(diǎn)數(shù)的擬合曲線，找到擬合曲線上曲率最大的點(diǎn)對(duì)應(yīng)的閾值作為每段子曲線中最優(yōu)閾值，分別對(duì)每段子曲線進(jìn)行化簡。

1.3 交叉路口特征點(diǎn)的選取與處理

首先分析道路網(wǎng)中所有道路曲線的拓?fù)潢P(guān)系，獲取所有道路曲線的交叉點(diǎn)。然后設(shè)置滿足實(shí)際需求的偏差閾值ε，對(duì)于化簡后的道路曲線的交叉點(diǎn)分為兩種類型，第一種是化簡后的道路曲線有交叉點(diǎn)，另一種是化簡后的道路曲線沒有交叉點(diǎn)。

對(duì)于第一種化簡后的道路曲線有交叉點(diǎn)的類型，如果交叉點(diǎn)化簡前后的位移差D<ε,則化簡后交叉點(diǎn)不用處理，化簡掉該交叉點(diǎn)并不會(huì)對(duì)實(shí)際的使用造成較大的影響，而如果D>ε，交叉點(diǎn)被化簡會(huì)影響實(shí)際的使用需求，要對(duì)此交叉點(diǎn)進(jìn)行處理。具體處理方法如圖1所示,P1(X1,Y1)、P2(X2,Y2)、P3(X3,Y3)、P4(X4,Y4)為預(yù)化簡過程的分段點(diǎn)，其坐標(biāo)是已知的，P5(X5,Y5)為原始交叉路口，P6為化簡后道路曲線新的交叉路口，其坐標(biāo)的計(jì)算方法為

通過求解方程組得到化簡后交叉點(diǎn)P6的坐標(biāo)(X6,Y6)，進(jìn)而得到化簡前后交叉點(diǎn)的偏移距離D,計(jì)算方法如下：

若D<ε,認(rèn)為化簡后的交叉口滿足精度的要求，不需要對(duì)化簡后的交叉點(diǎn)做處理。若D>ε,則把原交叉點(diǎn)P5作為分段點(diǎn)，然后對(duì)由點(diǎn)P1，P2，P3，P4組成的曲線段P1P5，P2P5，P3P5，P4P5進(jìn)行修正化簡，這樣就保證了道路曲線交叉點(diǎn)P5不被化簡。

圖1 化簡后曲線相交的交叉路口特征點(diǎn)的處理過程

對(duì)于第二種化簡后的道路曲線沒有交叉點(diǎn)的類型，則該交叉點(diǎn)不能被化簡，因?yàn)檫@種類型的交叉點(diǎn)是維持兩條道路曲線拓?fù)潢P(guān)系的關(guān)鍵點(diǎn)，如果被化簡兩條道路曲線就由相交變成了相離，導(dǎo)致原始到道路曲線之間的空間關(guān)系發(fā)生較大變化。如圖2所示,兩條道路曲線化簡后形成的線段P1P2,P3P4沒有相交，則以P5為分段點(diǎn)對(duì)此段曲線重新進(jìn)行修正化簡，這樣交叉點(diǎn)P5就得了保留，道路曲線的拓?fù)潢P(guān)系也得到保持。

圖2 化簡后曲線不相交的交叉路口特征點(diǎn)的處理過程

2 算法實(shí)現(xiàn)

算法具體步驟如下：

1)針對(duì)道路網(wǎng)中的道路曲線進(jìn)行相交和自交的拓?fù)浞治?，獲取到道路網(wǎng)中所有的交叉點(diǎn)。

2)在道路網(wǎng)中選取其中的一條道路曲線。然后從曲線的點(diǎn)Pi(i=2,3,…,N-1)中選取出特征點(diǎn)作為曲線的分段點(diǎn)。

3)以相鄰的分段點(diǎn)作為道格拉斯-普克算法的首尾點(diǎn)，利用基于最小二乘法的曲線擬合方法得到每一段曲線的最佳閾值，對(duì)分段后的曲線進(jìn)行化簡。

4)重復(fù)步驟2)～4)把道路網(wǎng)中所有的道路曲線都化簡完畢，至此得到預(yù)化簡后的曲線。

5)分析交叉點(diǎn)所在線段化簡后是否相交，如果不相交執(zhí)行步驟6)，如果相交則判斷道路曲線交叉點(diǎn)與化簡后交叉點(diǎn)的距離D與偏差閾值ε的關(guān)系，如果D<ε則此交叉點(diǎn)可以化簡掉，如果D>ε則此交叉點(diǎn)不能化簡，以此原交叉點(diǎn)為分段點(diǎn)，對(duì)相鄰的線段重新進(jìn)行化簡。

6)化簡后的曲線不相交則交叉點(diǎn)不能被化簡，以原交叉點(diǎn)為分段點(diǎn)對(duì)相鄰的線段重新進(jìn)行修正化簡。

7)重復(fù)執(zhí)行步驟5)，直到所有道路交叉點(diǎn)處理完畢。

3 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文算法的有效性，在實(shí)驗(yàn)中隨機(jī)選取一組道路曲線，利用本文所提算法與傳統(tǒng)的道格拉斯-算法進(jìn)行化簡。通過化簡后的圖形來說明該算法的有效性。

圖3、圖4展示了傳統(tǒng)的道格拉斯-普克算法與本文算法對(duì)具有交叉路口的道路曲線的效果對(duì)比。圖3所示是傳統(tǒng)道格拉斯-普克算法對(duì)道路曲線的化簡結(jié)果，由實(shí)驗(yàn)結(jié)果可知，傳統(tǒng)的道格拉斯-普克算法在對(duì)道路曲線進(jìn)行化簡時(shí)，只是針對(duì)每一條道路曲線進(jìn)行化簡，并沒有考慮道路曲線之間的拓?fù)潢P(guān)系，P1，P2，P3，P44個(gè)交叉點(diǎn)都被化簡，而且曲線上一些重要的特征點(diǎn)也沒有保留。同時(shí)由于交叉點(diǎn)P2被化簡，交叉點(diǎn)P2連接的兩條道路曲線由相交變?yōu)橄嚯x，道路曲線的拓?fù)潢P(guān)系發(fā)生了較大的改變。由此可見在對(duì)道路曲線進(jìn)行化簡時(shí)，傳統(tǒng)的道格拉斯-普克算法不能滿足實(shí)際的應(yīng)用需求。

圖3 傳統(tǒng)道格拉斯-普克算法化簡結(jié)果

圖4 本文算法化簡結(jié)果

圖4所示的是本文算法對(duì)道路曲線化簡的結(jié)果，由圖4(a)可知，當(dāng)偏差閾值ε=1 mm時(shí)，交叉點(diǎn)P1，P3化簡之后的位置偏移小于ε，滿足偏差閾值的要求，因此，交叉點(diǎn)P1，P3被化簡。交叉點(diǎn)P2由于化簡后的道路曲線不相交而不能被化簡。交叉點(diǎn)P4由于化簡前后的距離大于偏差閾值ε而沒有被化簡。使用本文算法在ε=1 mm對(duì)道路曲線進(jìn)行化簡后，交叉點(diǎn)P2，P4沒有被化簡，P1，P3被化簡掉，同時(shí)由于交叉點(diǎn)P2沒有被化簡兩條道路曲線化簡后的拓?fù)潢P(guān)系得到了保留。由圖4(b)可知，偏差閾值ε=2 mm，交叉點(diǎn)P1，P3，P4由于位置偏移都滿足精度要求而被化簡，交叉口P2由于化簡后道路曲線不相交而保留，維持了道路曲線之間的拓?fù)潢P(guān)系，同時(shí)曲線上一些重要的局部特征點(diǎn)也得

到了保留。因此，在使用本文算法對(duì)道路曲線進(jìn)行化簡時(shí)，并不是保留所有的道路交叉點(diǎn)，而是引入偏差閾值ε概念，確定交叉點(diǎn)是否保留，在實(shí)際需求中可以通過設(shè)置偏差閾值ε的大小，以滿足不同的化簡精度需求。

4 結(jié)束語

對(duì)于道路曲線而言，道路曲線的交叉點(diǎn)作為維持道路拓?fù)潢P(guān)系的關(guān)鍵點(diǎn)，在對(duì)其進(jìn)行化簡時(shí)，不能簡單地保留或化簡，應(yīng)該單獨(dú)進(jìn)行分析、處理。傳統(tǒng)的道格拉斯-普克算法在對(duì)道路曲線進(jìn)行化簡時(shí)并沒有考慮到道路曲線交叉點(diǎn)的特殊性，不能滿足道路曲線實(shí)際的化簡需求。本文通過尋找曲線上的特征點(diǎn)作為分段點(diǎn)及引入偏差閾值ε，設(shè)計(jì)并實(shí)現(xiàn)了一種基于交叉點(diǎn)的道路曲線化簡算法，通過引入偏差閾值概念使得本文算法不同于傳統(tǒng)的算法對(duì)交叉點(diǎn)全部保留或者刪除，而是通過分析交叉點(diǎn)化簡后的特征選擇性的保留與化簡，使用本文算法對(duì)于密集道路網(wǎng)進(jìn)行化簡時(shí)，能夠在保證道路曲線局部形態(tài)的前提下，科學(xué)有效地化簡或者保留交叉點(diǎn)，提升化簡的壓縮率。

[1] 蘇宏瑞,崔先國,彭玉艷.制圖綜合中基于中心地思想的線狀要素自動(dòng)取舍算法研究[J].測繪科學(xué),2007,32(1):40-42.

[2] 彭認(rèn)燦,董箭,鄭義東,等.垂距法與道格拉斯-普克法刪除冗余頂點(diǎn)效率的比較[J].測繪通報(bào),2010(3):66-67.

[3] 徐新.增強(qiáng)型矢量數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究,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] 張青年,廖克.基于結(jié)構(gòu)分析的曲線概括方法[J].中山大學(xué)學(xué)報(bào)(自然科學(xué)版),2001,40(5):118-121.

[8] 于靖,陳剛,張笑,等.面向自然岸線抽稀的改進(jìn)道格拉斯—普克算法[J].測繪科學(xué),2015,40(4):23-27.

[9] 張振鑫,張維,劉嬪,等.矢量地圖數(shù)據(jù)簡化研究進(jìn)展[J].測繪工程,2016,25(6)：10-14.

[10] 李朝奎,駱文芳,陳果,等.漸進(jìn)式改進(jìn)的線要素簡化算法探討[J].測繪科學(xué)，2015,40(11):123-126.

[11] 巨正平,王勇,郭廣禮,等.附有限制條件的逐點(diǎn)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)[J].測繪通報(bào),2009(4):25-28.

[12] 張志偉,暴景陽,肖付民,等.基于Ping的Douglas-Peucker法抽稀閾值優(yōu)化選取[J].海洋測繪,2015,35(2):9-12.

[13] 何海威,錢海忠,王驍,等.采用彎曲進(jìn)行道路化簡沖突避免的方法[J].測繪學(xué)報(bào),2016,45(3):354-361.

[14] 楊志堅(jiān).顧及局部特征的線狀要素制圖綜合[J].測繪科學(xué),2016,41(4)：118-123.

[15] 王曉理,陳雙軍,魏斌,等.曲線擬合的Douglas-Peucker算法閾值優(yōu)化選擇[J].測繪科學(xué)技術(shù)學(xué)報(bào),2010,27(6):459-462.

[責(zé)任編輯：劉文霞]

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

著錄：李世寶，陳通，劉建航，等.基于交叉點(diǎn)的道路曲線化簡算法研究[J].測繪工程，2017，26(7)：1-4，11.

10.19349/j.cnki.issn1006-7949.2017.07.001

2016-07-18

山東省自然科學(xué)基金面向項(xiàng)目(ZR2014FM017);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(15CX05025A);青島市科技創(chuàng)新計(jì)劃(15-9-80-jch);青島市黃島區(qū)科技發(fā)展計(jì)劃項(xiàng)目(2014-1-45)

李世寶(1978-)，男，副教授，碩士.

P208

A

1006-7949(2017)07-0001-04