一種顧及空間關(guān)系約束的線化簡算法

李成名，郭沛沛，殷 勇，武鵬達，顧 騰

1. 山東科技大學(xué)測繪科學(xué)與工程學(xué)院，山東 青島 266590； 2. 中國測繪科學(xué)研究院，北京 100830； 3. 東華理工大學(xué)測繪工程學(xué)院，江西 南昌 330013

?

一種顧及空間關(guān)系約束的線化簡算法

李成名1,2，郭沛沛1,2，殷 勇1,2，武鵬達2，顧 騰3

1. 山東科技大學(xué)測繪科學(xué)與工程學(xué)院，山東 青島 266590； 2. 中國測繪科學(xué)研究院，北京 100830； 3. 東華理工大學(xué)測繪工程學(xué)院，江西 南昌 330013

線要素化簡在制圖表達與綜合領(lǐng)域一直是研究的熱點和難點之一。然而，經(jīng)典化簡算法多針對單獨線要素進行處理，缺乏對該線要素與周邊線要素之間整體空間關(guān)系的考慮，并且，存在計算結(jié)果生硬(D-P算法)、局部極值點缺失，特別是在曲度較大之處出現(xiàn)相交異常(L-O算法)等問題。為此，本文提出一種顧及空間關(guān)系約束的線化簡算法，建立線要素全局化簡方法(LGSM)和矢量位移、面積位移等5類評價指標(biāo)。采用等高線、河流和道路3類線要素實際數(shù)據(jù)進行了試驗，充分檢驗了本文算法的優(yōu)越性，其處理結(jié)果符合開方根模型規(guī)律，降低了曲線復(fù)雜度，在保證全局空間關(guān)系不變條件下，不僅更好地保持了曲線整體形狀特征，而且光滑美觀、精度高。

線化簡；空間關(guān)系約束；全局化簡方法；開方根模型

線要素在地圖要素中占比較大，用于道路、河流、等高線等重要線狀地理要素的表達，因此，有關(guān)線要素的化簡在制圖綜合領(lǐng)域中，一直是研究的熱點，也取得了較好的結(jié)果。線要素化簡算法的基本思想是在盡可能保持曲線形狀特征的前提下，減其節(jié)點數(shù)量，如常用的Douglas-Peucker算法[1]、Li-Openshaw算法[2]以及改進的Li-Openshaw算法[3]和弧比弦算法[4]等。Douglas-Pecuker算法最為經(jīng)典，能夠?qū)φ麠l曲線進行壓縮的同時，很好地保留曲線的特征彎曲點，但化簡結(jié)果過于生硬且在特征點處容易產(chǎn)生尖角；Li-Openshaw算法則可以很好地光滑線要素特征彎曲點(尖角)，一定程度上克服了化簡結(jié)果生硬的不足，但對所有特征彎曲點統(tǒng)一光滑卻容易造成化簡結(jié)果發(fā)生變形；改進后的Li-Openshaw算法很好地保留了曲線的局部極大值點，但由于未考慮該線要素與周邊的整體空間關(guān)系，當(dāng)遇到復(fù)雜密集線要素時，其處理結(jié)果會出現(xiàn)線相交或相接的缺陷[5]。

整體而言，現(xiàn)有線化簡算法大多僅考慮單獨線要素自身節(jié)點及其弧段特征，鮮有顧及線要素與周邊鄰近線要素的整體空間關(guān)系，當(dāng)化簡復(fù)雜線要素(如密集等高線)時，由于線間距離過小，難以避免化簡結(jié)果出現(xiàn)線相交或相接的拓撲錯誤。有鑒于此，本文提出一種顧及空間關(guān)系約束的線化簡算法，首先建立線要素全局化簡方法(LGSM)，標(biāo)識化簡區(qū)域線要素的全局空間關(guān)系，然后，組合使用經(jīng)典D-P、L-O算法對曲線進行自適應(yīng)化簡。

1 現(xiàn)有研究基礎(chǔ)

1.1 Douglas-Peucker(D-P)算法

D -P算法出現(xiàn)較早，在線要素化簡中影響較大。該算法的核心思想是對曲線上的點進行采樣簡化，即在曲線上取有限個點，將其變?yōu)檎劬€，化簡后的曲線可以在一定程度上保持原有的形狀，化簡效率高且不會產(chǎn)生多余的點。其原理如圖1(a)所示，thresholdv為設(shè)定的距離綜合閾值，ABCDEFG為原折線，ACEG為化簡后折線[5]。可以發(fā)現(xiàn)，該算法生成的化簡結(jié)果保留了曲線上重要的點，對原線段進行了概括，然而該算法無法在特征點處做到光滑處理，這限制了該算法在線要素化簡中的實際應(yīng)用。

圖1 兩中經(jīng)典線化簡算法示意圖Fig.1 Two classic line simplification algorithms

1.2 Li-Openshaw(L-O)算法

Li-Openshaw算法是一種基于自然法則的自適應(yīng)線狀要素綜合算法。該算法的核心思想是：首先，依據(jù)源比例尺和目標(biāo)比例尺估算出圓形最小可視目標(biāo)SVO(smallest visual object)的尺寸R，見式(1)

(1)

式中，St為需要化簡后的目標(biāo)比例尺分母；Sf為原比例尺分母；D為化簡后地圖上的SVO的一個參數(shù)。Muller[8]根據(jù)繪圖筆的粗度和人眼分辨率推算在地圖上D取0.4mm為能保證視覺分辨的最小值。

然后，確定圓形SVO的起始位置，一般以待綜合曲線的首節(jié)點作為首個圓心，如圖1(b)所示，以A點為圓心、圓形SVO的尺寸R為直徑作圓，交曲線于點Q，選擇AQ的中點P作為綜合后的選取點，從Q點開始，重復(fù)迭代，直到曲線末端點D。

在圖1(b)中，折線ABCD為原折線，AEFGHID為化簡后折線[5]，可以發(fā)現(xiàn)，經(jīng)L-O算法化簡的線要素比較光滑，局部特征處理美觀，但因為算法會對局部特征點進行統(tǒng)一光滑概括，也導(dǎo)致了在對于整體形狀具有支撐作用的局部特征點處會發(fā)生變形。

2 空間關(guān)系約束下的線化簡算法原理與方法

2.1 空間關(guān)系約束下的線化簡算法原理

針對以上兩種算法的不足，本文首先考慮化簡區(qū)域線要素與周邊鄰近線要素的距離關(guān)系、整體拓撲關(guān)系，當(dāng)線要素形狀復(fù)雜、彎曲多而密集、數(shù)據(jù)量較大時，不僅要盡可能維持線要素形狀，更要保證線要素空間關(guān)系不變，避免化簡結(jié)果出現(xiàn)相交或相接。為此，本文設(shè)計空間關(guān)系約束條件下的線要素全局化簡方法(line global simplification method，LGSM)，該方法細分為全局化簡判斷模型(global simplification estimation model，GSEM)和全局化簡光滑模型(global simplification smooth model，GSSM)。

GSEM用作標(biāo)識化簡區(qū)域線要素的全局空間關(guān)系

GSEM=Fs(SpacingL-Others, SpatialRelationshipL-Others)

(2)

式中，F(xiàn)s指化簡函數(shù)(function simplification)，SpacingL-Others指某一條線L與其他鄰近線要素(Others)之間的間距值，SpatialRelationshipL-Others指某一條線L與其他鄰近線要素之間的拓撲空間關(guān)系。

對于使用現(xiàn)有算法化簡后，發(fā)生相交的部分多集中曲線曲度較大之處，如曲線“瓶頸”“凹槽”等部位，通常這些部分兩條線間寬度間距較小。因此，為避免比例尺縮小時線化簡出現(xiàn)拓撲變化，首先使用特征點計算這些部位的寬度間距SpacingL-Others[6-7]，如果SpacingL-Others≤thresholdH(間距閾值)，則標(biāo)記這些部分，在化簡處理時根據(jù)要素幾何特征、語義優(yōu)先級特征作出選取處理或跳過這些部分不作處理(表1)；如果SpacingL-Others>thresholdH，且線要素之間符合空間拓撲約束(圖2相接、相離)，則可對這些部分進行線要素化簡并記錄化簡前的空間關(guān)系。thresholdH是一種經(jīng)驗閾值，參考文獻[8]，考慮到屏幕分辨率或繪圖筆的粗度，實際閾值的基礎(chǔ)參考值可設(shè)為保證視覺分辨的最小值0.4 mm。

表1 線要素SpacingL-Others≤thresholdH時的處理方法

對于符合化簡條件的線要素，設(shè)計全局化簡光滑模型進行光滑化簡處理

GSSM=Fs(DValueLD,LValueLR,SpacingL-Others, SpatialRelationshipL-Others)

(3)

式中，F(xiàn)s、SpacingL-Others、SpatialRelationshipL-Others要素指代含義與上述GSEM模型中各要素含義一致；DValueLD指應(yīng)用D-P算法要事先設(shè)定的距離綜合閾值(line distance，LD)，該值用來篩選過濾線要素的局部極值點，LValueLR指應(yīng)用L-O算法估算出的圓形最小可視目標(biāo)SVO的尺寸R。

由第2部分可知，單獨應(yīng)用D-P算法會使線要素化簡結(jié)果不夠光滑，單獨應(yīng)用L-O算法則會出現(xiàn)局部極值點缺失等情況，因此，本文嘗試將Douglas-Peucker算法與Li-Openshaw算法結(jié)合應(yīng)用，保留各自的算法優(yōu)勢并進行優(yōu)化以實現(xiàn)曲線化簡。GSSM用于對化簡區(qū)域內(nèi)的線要素進行光滑化簡處理，每條曲線為一個處理單元，處理結(jié)束后計算線要素與其鄰近要素之間的拓撲空間關(guān)系。如該線要素周圍環(huán)境簡單，則計算化簡后的線要素與鄰近線要素之間的間距是否符合后續(xù)制圖表達時的間距要求，如小于間距要求，則對兩線要素進行遠離移位處理，如表2所示；如線要素周圍環(huán)境復(fù)雜，移位處理涉及多條線要素，則保留曲線化簡前形狀特征，對該部分不作處理(如表1序號3所示)。

在線要素化簡過程中，兩條曲線之間的空間拓撲關(guān)系LL(代表任意的兩條曲線)可總結(jié)為6種[9-11]，如圖2所示，具體的組合方式如下：①共線，曲線L1與曲線L2部分重疊，圖2(a)；②覆蓋，曲線L2被曲線L1覆蓋，圖2(b)；③重合，直線段L1全部位于直線段L2中，與L2完全重合圖2(c)；④相接，L1一端點在曲線L2上，兩曲線相交于此點，L1的另一端點在曲線L2的一側(cè)，圖2(d)；⑤相交，兩曲線相交于非端點，L1的兩個端點分別位于L2的兩側(cè)，圖2(e)；⑥相離，端點都不重合，兩曲線不共線，兩曲線相離，圖2(f)。

圖2 兩條曲線之間的空間拓撲關(guān)系Fig.2 Spatial topological relations between two curves

以上定義的6種曲線之間的空間拓撲關(guān)系構(gòu)成了整個線空間對象拓撲關(guān)系空間的一個覆蓋，其他更加復(fù)雜的拓撲關(guān)系都可以用這6種拓撲關(guān)系的變形或復(fù)合來實現(xiàn)[12-14]。本文通過模型參數(shù)SpatialRelationshipL-Others來實現(xiàn)這些拓撲關(guān)系的運算、驗證與表達。在線要素化簡過程中，當(dāng)兩條曲線之間的空間拓撲關(guān)系為共線、覆蓋、重合、相交時，不能進行化簡，需進行拓撲糾正，以保證同一要素類中，線與線不能相互重疊、相交；同時，化簡過程中，若相離關(guān)系因為線群密集或LValueLR值過大導(dǎo)致化簡后線要素相接或相交，則需進行如表2所示拓撲移位處理。

表2 空間關(guān)系變化后處理方法(粗線為化簡后)

模型中，某一條線L與其他鄰近線要素(Others)之間的間距值SpacingL-Others為L上的特征彎曲點到各個鄰近線要素體之間的最短距離；D-P算法的距離綜合閾值DValueLD為事先給定的經(jīng)驗值；L-O算法的圓形最小可視目標(biāo)SVO的尺寸LValueLR值由公式(1)計算得到。

2.2 線要素全局化簡方法(LGSM)計算流程

線要素全局化簡方法(LGSM)計算流程如下：

(1) 根據(jù)經(jīng)驗及綜合前后的比例尺跨度，應(yīng)用GSEM模型設(shè)立空間間距閾值并判斷線要素之間的空間關(guān)系，若滿足模型空間約束條件，執(zhí)行步驟(2)；若不滿足模型約束條件，則對不滿足條件的曲線進行拓撲處理，拓撲處理屬于本領(lǐng)域常用知識[15-16]，這里不再贅述，對處理后滿足條件的曲線執(zhí)行步驟(2)。

(2) 設(shè)定GSSM模型中的距離綜合閾值DValueLD，采用D-P算法得到距離大于DValueLD的局部極值點集合，如圖3所示，B、E、F、G為滿足條件的極值點。

(3) 應(yīng)用公式(1)，按照目標(biāo)比例尺和原比例尺來估算出GSSM模型中最小可視目標(biāo)SVO的尺寸R。

(4) 以局部極值點為圓點，以2～3倍的R值為探測閾值，畫SVO交原曲線于點B1、B2，記錄B1、B2、E1、E2為處理分界點。

圖3 線要素全局化簡方法(LGSM)Fig.3 Line global simplification method

(5) 從首節(jié)點A開始至相鄰分界點B1、分界點B2至分界點E1、分界點E2至末節(jié)點H應(yīng)用L-O算法對該折線進行化簡。

(6) 對于極值點稀疏處(如圖3中極值點B處)，分界點B1、B2之間不作處理，保留極值點B。

(7) 對于不包括極值點的曲線平滑部分(如B2至C)，為提高化簡效率，減少節(jié)點數(shù)量，化簡時不需逐點探測化簡，采用如下優(yōu)化算法找到該部分的“有效部分”：判斷B2至C區(qū)間的距離(L)所包含的探測結(jié)構(gòu)SVO(R為SVO的半徑)的個數(shù)n(n=1,2,3…)，從點B2開始，對n×R距離內(nèi)覆蓋的平整曲線不作處理，而將(L-n×R，L)的部分記為該段曲線的“有效部分”，對“有效部分”使用L-O算法進行化簡。

(8) 對于極值點聚集處(如圖3中極值點E處，極值點F、G在其探測范圍內(nèi))，以E點為圓心，更改SVO半徑(如1/2R)畫圓對F、G極值點進行化簡概括。

(9) 順序處理，保存末節(jié)點H，單獨曲線化簡結(jié)束。圖3中，ABCDEFGH為原曲線，ABIJKLMN

OPH為化簡后曲線。

(10) 逐個線要素處理完成后，應(yīng)用GSSM模型檢驗化簡后的曲線周圍的空間關(guān)系，對不滿足化簡間距要求的曲線進行遠離移位，保證線要素之間空間關(guān)系不變，化簡結(jié)束。

3 試驗分析及評價

3.1 對比分析試驗

本文依托中國測繪科學(xué)研究院研制的NewMap軟件平臺WJ-III地圖工作站，嵌入本文提出的線化簡改進方法，以南方某城市0.007km2范圍等高線、7.43km2范圍道路與55.37km2范圍水系數(shù)據(jù)綜合化簡為例對本方法進行化簡效果驗證，同時，選取該算法與Douglas-Peucker、文獻[3]中改進的Li-OpenShaw算法進行對比分析。其中，等高線數(shù)據(jù)由原始的1∶5萬比例尺地圖綜合至1∶10萬比例尺，對應(yīng)的GSEM、GSSM模型分別為

道路和水系數(shù)據(jù)由原始1∶1萬地圖綜合取舍至1∶10萬比例尺，對應(yīng)的GSEM、GSSM模型分別為

式中，GSEM模型中0.4 mm為1∶1萬比例尺道路和水系數(shù)據(jù)圖上間距閾值，R1d or f表示對符合圖2(d)、2(f)中的相接、相離空間拓撲關(guān)系的線要素進行化簡；同樣為突出3種算法的化簡效果，GSSM模型中設(shè)置0.8 mm(0.2 mm×4)為D-P算法圖上距離綜合閾值，由式(1)計算得到L-O算法的R值為36 m(實際距離)，0.4 mm為1∶10萬比例尺道路和水系數(shù)據(jù)圖上間距閾值，R2d or f為與R1d or f完全對應(yīng)的空間關(guān)系。

在相同的參數(shù)條件下用3種算法對等高線、道路和河流數(shù)據(jù)進行化簡，圖4、圖5和圖6分別截取了部分化簡結(jié)果，圖中短線為D-P算法的距離綜合閾值圖解標(biāo)識線。

在處理等高線等線群密集的要素時，D-P算法化簡效率最高，但是化簡結(jié)果顯得粗糙，線群密集時相交較多(圖4(a))，且在處理小面積閉合等高線時，由于取長軸作為閉合等高線的首末節(jié)點連線，而短軸小于距離閾值，導(dǎo)致個別閉合等高線在化簡時被刪除，沒有產(chǎn)生化簡后的圖形；改進的L-O算法在綜合化簡中對等高線線做到了光滑過濾，很好地保證了彎曲特征點，線線相交或相接次數(shù)減少，但局部特征點仍有缺失(圖4(b))，化簡后曲線密集處(A-B)仍有相交趨勢，無法解決當(dāng)綜合前后的比例尺跨度較大時曲線的相交(接)問題；本文算法化簡結(jié)果與原始數(shù)據(jù)貼合緊密，不僅在等高線要素化簡中做到了光滑，而且精確地保留了局部極大值點，保證了曲線原有的形狀特征不發(fā)生明顯變化(圖4(c))，且在曲線密集、兩條線間寬度間距小于GSEM模型中的化簡間距閾值時(A-B部分)，本文算法通過“標(biāo)記”處理(表1序號3)，保證了該部分曲線化簡前后線線間間距、拓撲關(guān)系不變。

圖4 等高線試驗結(jié)果圖(粗線為化簡后)Fig.4 Contour simplification results(broad lines show the result after simplification)

試驗數(shù)據(jù)中，道路、水系線狀要素結(jié)構(gòu)平緩而稀疏，空間關(guān)系發(fā)生變化區(qū)域較少，數(shù)據(jù)化簡特征與等高線效果相似，圖5(c)、圖6(c)中，改進的算法更多地保留了曲線特征拐點，與原始道路、水系形狀貼合地更加一致，化簡結(jié)果優(yōu)于其他兩種算法。

縱向?qū)Ρ?幅圖的化簡結(jié)果，當(dāng)線要素平滑而稀疏時，改進的效果并不明顯，而對于彎曲多且密集的線要素區(qū)域，本文提出的改進算法化簡效果明顯優(yōu)于其他兩種算法，化簡后的線要素與原始數(shù)據(jù)貼合效果好，在保證了曲線壓縮的基礎(chǔ)上，最大程度地保留了曲線形狀特征，且不會發(fā)生空間關(guān)系變化，因此本算法更加適用于制圖綜合及表達。

圖5 道路試驗結(jié)果圖(粗線為化簡后)Fig.5 Road simplification results(broad lines show the result after simplification)

圖6 水系試驗結(jié)果圖(粗線為化簡后)Fig.6 River simplification results(broad lines show the result after simplification)

3.2 精度評價

線要素制圖綜合中，算法化簡對線要素幾何精度的影響主要體現(xiàn)在曲線化簡前后整體和局部的位移，因此，本文給出矢量位移、面積位移[17-19]、位移標(biāo)準(zhǔn)差和位置誤差等評價指標(biāo)[20-21]，對本文提出的算法與Douglas-Peucker、改進的Li-OpenShaw兩種算法進行位置精度比較評估。本文在矢量位移上采用線要素化簡區(qū)域的平均偏移值，在面積位移上采用面積位移總和進行評價[5,22]。

如表3所示，本文提出的改進算法不僅在視覺感官上的效果優(yōu)于其他兩種算法，而且矢量平均偏移值和面積位移總和也遠遠小于優(yōu)于其他兩種算法，表明本文算法對于維持線狀要素的形狀特征更有優(yōu)勢。

表3 3種算法對不同線要素化簡后矢量、面積位移評價結(jié)果

位移標(biāo)準(zhǔn)差(standardized measure of displac-ement，SMD)[20]計算方法如下

SMD(%)=100(1-(S-D)/S)

(4)

式中，S為算法化簡后原始曲線上位移最大的點到曲線首末端點連線的距離；D為該點化簡前后的位移值。SMD主要針對局部最大值進行評價，本文進一步采用位置誤差來評價化簡前后的整體位移，計算方法如下[20-21]

δ=Δs/L

(5)

式中，Δs表示曲線化簡前后相交圍成的面積；L表示原始曲線的長度。

由表4可以看出，本文算法展現(xiàn)出了良好的性能，在位移標(biāo)準(zhǔn)差與位置誤差兩方面都處于3種方法中的最優(yōu)位置，尤其在位置誤差指標(biāo)上表現(xiàn)得最為優(yōu)異，其值很小，表明該方法有效地維持了道路、水系數(shù)據(jù)的整體形狀特征。

表4 3種算法對不同線要素化簡后位移標(biāo)準(zhǔn)差與位置誤差評價結(jié)果

在線要素化簡評估過程中，線要素的復(fù)雜度是評價的另一個重要指標(biāo)，而節(jié)點數(shù)量是反映復(fù)雜度的一個主要指標(biāo)，因此，本文統(tǒng)計線要素的節(jié)點數(shù)量并使用開方根模型規(guī)律[23-25]進行驗證，見式(6)

(6)

式中，nF為新編地物數(shù)量；nA為原始地物數(shù)量；MA為原始地圖比例尺分母；MF為新編地圖比例尺分母。

如表5所示，在等高線、道路、水系3種地物要素中，對于節(jié)點數(shù)量化簡程度最大的是D-P算法，因為其在化簡過程中刪除了數(shù)量最多的極值點；改進的L-O算法及本文算法因為保持線要素化簡的形狀特征，故化簡后的節(jié)點數(shù)量相對較多，但仍符合方根模型規(guī)律，對于道路、水系等簡單地物要素，化簡后節(jié)點數(shù)量貼近方根模型約束節(jié)點數(shù)量，對于等高線等復(fù)雜地物，化簡后節(jié)點數(shù)量遠遠小于模型約束數(shù)量，去復(fù)雜化程度明顯。

表5 等高線、道路、水系化簡節(jié)點數(shù)量變化情況

4 結(jié)束語

本文提出一種顧及空間關(guān)系約束及制圖表達要求的線化簡算法，在化簡過程中以鄰近空間關(guān)系符合制圖要求為約束條件，以相鄰線要素作為化簡參考，構(gòu)造線要素全局化簡判斷模型、線要素全局化簡光滑模型實現(xiàn)曲線化簡，并依托中國測繪科學(xué)研究院研制的WJ-III地圖工作站，嵌入上述綜合取舍算法。以南方某城市等高線、道路與水系數(shù)據(jù)為試驗案例，進行了曲線化簡，并將化簡結(jié)果與D-P、改進的L-O算法進行了對比分析。試驗結(jié)果表明：同已有兩種經(jīng)典算法相比，本文算法在線化簡中顧及了線要素整體的空間關(guān)系，更好地保持了曲線的整體形狀，保留了局部特征點的同時對曲線進行了光滑處理，化簡結(jié)果具有更高的位置精度，更加適用于制圖綜合及表達。

本文目前所提線化簡算法主要針對線要素空間特征、位置精度進行設(shè)計，并未考慮線要素的語義特征且并未顧及與其他點、面要素間的關(guān)系，這些都有待進一步探討。

[1] DOUGLAS D H, PEUCKER T K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J]. Cartographer, 1973, 10(2): 112-122.

[2] 李志林, OPENSHAW S. 基于客觀綜合自然規(guī)律的線狀要素自動綜合的算法[J]. 武測譯文, 1994(1): 49-58. LI Zhilin, OPENSHAW S. Linear Feature’s Self-adapted Generalization Algorithm Based on Impersonality Generalized Natural Law[J]. Translation of Wuhan Technical University of Surveying and Mapping, 1994(1): 49-58.

[3] 朱鯤鵬, 武芳, 王輝連, 等. Li-Openshaw算法的改進與評價[J]. 測繪學(xué)報, 2007, 36(4): 450-456. ZHU Kunpeng, WU Fang, WANG Huilian, et al. Improvement and Assessment of Li-Openshaw Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4): 450-456.

[4] 劉慧敏, 樊子德, 徐震, 等. 曲線化簡的弧比弦算法改進及其評價[J]. 地理與地理信息科學(xué), 2011, 27(1): 45-48. LIU Huimin, FAN Zide, XU Zhen, et al. An Improved Local Length Ratio Method for Curve Simplification and Its Evaluation[J]. Geography and Geo-Information Science, 2011, 27(1): 45-48.

[5] 顧騰, 陳曉勇, 劉成強. 一種Douglas-Peucker與Li-Openshaw結(jié)合改進的曲線化簡方法[J]. 東華理工大學(xué)學(xué)報(自然科學(xué)版), 2016, 39(4): 396-400. GU Teng, CHEN Xiaoyong, LIU Chengqiang. A modified Line Simplification Method Combined Douglas-Peucker with Li-Openshaw[J]. Journal of East China University of Technology, 2016, 39(4): 396-400.

[6] NAKOS B, MITROPOULOS V. Local Length Ratio as a Measure of Critical Points Detection for Line Simplification[C]∥The Symposium of the 5th ICA Workshop on Progress in Automated Map Generalization. Paris, France: ICA, 2003: 28-30.

[7] 艾廷華, 劉耀林. 保持空間分布特征的群點化簡方法[J]. 測繪學(xué)報, 2002, 31(2): 175-181. AI Tinghua, LIU Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 175-181.

[8] MULLER J C. Fractal and Automated Line Generalization[J]. The Cartographic Journal, 1987, 24(1): 27-34.

[9] 郭慶勝, 劉小利, 陳宇箭. 線與線之間的空間拓撲關(guān)系組合推理[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2006, 31(1): 39-42. GUO Qingsheng,LIU Xiaoli,CHEN Yujian.Combinational Reasoning of Topological Spatial Relations between Two Lines[J]. Geomatics and Information Science of Wuhan University, 2006, 31(1): 39-42.

[10] 何建華, 劉耀林. GIS中拓撲和方向關(guān)系推理模型[J]. 測繪學(xué)報, 2004, 33(2): 156-162. DOI: 10.3321/j.issn:1001-1595.2004.02.012. HE Jianhua, LIU Yaolin. An Integrated Model for Topology & Direction Relation Reasoning[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(2): 156-162. DOI: 10.3321/j.issn:1001-1595.2004.02.012.

[11] 王家耀, 崔鐵軍, 王光霞. 圖論在道路網(wǎng)自動選取中的應(yīng)用[J]. 解放軍測繪學(xué)院學(xué)報, 1985(1): 79-86. WANG Jiayao,CUI Tiejun,WANG Guangxia.Applications of Graph Theory in Automatic Selection of Road Network[J]. Journal of Geomatics Science and Technology, 1985(1): 79-86.

[12] CHEN Jun, LI Chengming, LI Zhilin, et al. A Voronoi-based 9-intersection Model for Spatial Relations[J]. International Journal of Geographical Information Science, 2001, 15(3): 201-220.

[13] WINTER S, FRANK A U. Topology in Raster and Vector Representation[J]. GeoInformatica, 2000, 4(1): 35-65.

[14] 鄧敏, 李成名, 劉文寶. 利用拓撲和度量相結(jié)合的方法描述面目標(biāo)間的空間關(guān)系[J]. 測繪學(xué)報, 2002, 31(2): 164-169. DENG Min, LI Chengming, LIU Wenbao. Describing Spatial Relations between Area Objects via Combining Topology with Metrization[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 164-169.

[15] 陳述彭, 魯學(xué)軍, 周成虎. 地理信息系統(tǒng)導(dǎo)論[M]. 北京: 科學(xué)出版社, 1999. CHEN Shupeng, LU Xuejun, ZHOU Chenghu. Introduction to Geographic Information System[M]. Beijing: Science Press, 1999.

[16] 王鵬波, 武芳, 翟仁健. 一種用于道路網(wǎng)綜合的拓撲處理方法[J]. 測繪科學(xué)技術(shù)學(xué)報, 2009, 26(1): 64-68. WANG Pengbo, WU Fang, ZHAI Renjian. A Topologic Operation Method for Automated Generalization of Road Networks[J]. Journal of Geomatics Science and Technology, 2009, 26(1): 64-68.

[17] WHITE E R.Assessment of Line-Generalization Algorithms Using Characteristic Points[J].The American Cartographer, 1985, 12(1): 17-28.

[18] MCMASTER R B. A Statistical Analysis of Mathematical Measures for Linear Simplification[J]. The American Cartographer, 1986, 13(2): 103-116.

[19] MCMASTER R B. Automated Line Generalization[J]. Cartographica, 1987, 24(2): 74-111.

[20] 武芳, 朱鯤鵬. 線要素化簡算法幾何精度評估[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2008, 33(6): 600-603. WU Fang,ZHU Kunpeng.Geometric Accuracy Assessment of Linear Features′ Simplification Algorithms[J]. Geomatics and Information Science of Wuhan University, 2008, 33(6): 600-603.

[21] 陳競男, 錢海忠, 王驍, 等. 提高線要素匹配率的動態(tài)化簡方法[J]. 測繪學(xué)報, 2016, 45(4): 486-493. DOI: 10.11947/j.AGCS.2016.20150074. CHEN Jingnan, QIAN Haizhong, WANG Xiao, et al. Improving the Matching Rate of Line Feature by Using Dynamic Simplification[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4): 486-493. DOI: 10.11947/j.AGCS.2016.20150074.

[22] 鄧敏, 陳杰, 李志林, 等. 曲線簡化中節(jié)點重要性度量方法比較及垂比弦法的改進[J]. 地理與地理信息科學(xué), 2009, 25(1): 40-43. DENG Min, CHEN Jie, LI Zhilin, et al. An Improved Local Measure Method for the Importance of Vertices in Curve Simplification[J]. Geography and Geo-Information Science, 2009, 25(1): 40-43.

[23] 何宗宜. 地圖數(shù)據(jù)處理模型的原理與方法[M]. 武漢: 武漢大學(xué)出版社, 2004. HE Zongyi. Elements and Methods of Model for Cartographical Data Processing[M]. Wuhan: Wuhan University Press, 2004.

[24] 張青年. 逐層分解選取指標(biāo)的河系簡化方法[J]. 地理研究, 2007, 26(2): 222-228. ZHANG Qingnian. Drainage Generalization by Layered Division of The Number of Retained Rivers in River Trees[J]. Geographical Research, 2007, 26(2): 222-228.

[25] 邵黎霞, 何宗宜, 艾自興, 等. 基于BP神經(jīng)網(wǎng)絡(luò)的河系自動綜合研究[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2004, 29(6): 555-557. SHAO Lixia, HE Zongyi, AI Zixing, et al. Automatic Generalization of River Network Based on BP Neural Network Techniques[J]. Geomatics and Information Science of Wuhan University, 2004, 29(6): 555-557.

(責(zé)任編輯：宋啟凡)

歡迎訂閱《測繪學(xué)報》

《測繪學(xué)報》創(chuàng)刊于1957年，是由中國科協(xié)主管、中國測繪地理信息學(xué)會主辦、《測繪學(xué)報》編輯部編輯、測繪出版社出版的反映我國測繪地理信息科學(xué)技術(shù)發(fā)展水平的綜合性學(xué)術(shù)刊物，影響因子和被引頻次居中文核心期刊測繪地理信息類前列，是美國《工程索引》 (Ei)核心期刊，曾榮獲百種中國杰出學(xué)術(shù)期刊、中國精品科技期刊、中國國際影響力優(yōu)秀學(xué)術(shù)期刊、全國優(yōu)秀測繪期刊等稱號，連續(xù)多年入選中國科協(xié)精品科技期刊工程項目，并被國內(nèi)外多個重要數(shù)據(jù)庫收錄，是我國測繪地理信息科學(xué)領(lǐng)域具有重要影響力的學(xué)術(shù)期刊。

《測繪學(xué)報》著重報道我國測繪地理信息科技最新的重要研究成果及其應(yīng)用，內(nèi)容涉及大地測量與導(dǎo)航、工程測量、攝影測量與遙感、地圖學(xué)與地理信息、礦山測量、海洋測繪、地籍測繪、地圖印刷、測繪儀器、信息傳輸?shù)葴y繪地理信息學(xué)科及其相關(guān)相鄰學(xué)科。

《測繪學(xué)報》設(shè)有快報論文、學(xué)術(shù)論文、博士論文摘要等欄目。

《測繪學(xué)報》(月刊)2017年定價：40.00元/期,郵發(fā)代號：2-224。

編輯部地址：北京市西城區(qū)三里河路50號，郵編：100045，訂閱電話：010-68531192(金老師)，010-68531317(傳真)。

網(wǎng)址：http:∥xb.sinomaps.com

A Line Simplification Algorithm Considering Spatial Relations between Two Lines

LI Chengming1,2，GUO Peipei1,2，YIN Yong1,2，WU Pengda2，GU Teng3

1. College of Geomatics, Shandong University of Science and Technology, Qingdao 266590, China; 2. Chinese Academy of Surveying and Mapping, Beijing 100830, China; 3.School of Geomatics, East China University of Tecnology, Nanchang 330013, China

Line element simplification has always been a hot research topic in the field of cartography generalization and expression. However, more existing line simplification algorithms aimed at single line rather than spatial relationship between linear elements. At the same time, there are some problems with classical algorithm, such as blunt performance(D-P algorithm), missing local extreme point and curve intersection(L-O algorithm). So, this paper puts forward a line simplification algorithm taking account of spatial relations between two lines. Line global simplification method(LGSM), vector displacement, area displacement and so on are proposed. Experiments are carried out on three kinds of line elements,such as contour lines, rivers and roads. The experiments' results show that the proposed algorithm can maintain the overall shape of the curve better and reduce the complexity of the curve effectively, the shape is more smooth and has a high position accuracy.

line simplification; spatial relations constraints; line global simplification method(LGSM); square-root model

The National Key Technology Research and Development Program of the Ministry of Science and Technology of China (No.2015BAJ06B01)； Special Scientific Research Fund of Public Welfare Profession on Surveying, Mapping and Geo-Information (No. 201512027)；National Basic Surveying and Mapping Project (No. A1615)

GUO Peipei

P208

A

1001-1595(2017)04-0498-09

國家科技支撐計劃(2015BAJ06B01)；測繪地理信息公益性行業(yè)科研專項(201512027)；國家基礎(chǔ)測繪項目(A1615)

2016-10-31

李成名(1968—)，男，博士，研究員，主要從事數(shù)字城市、智慧城市、地圖制圖與綜合自動化研究。First author： LI Chengming(1968—), male, PhD, research fellow, majors in digital city, smart city，cartography and map automatic generalization.

E-mail： cmli@casm.ac.cn

郭沛沛

E-mail： guopeipei925@163.com

修回日期： 2017-03-27