斷裂點位置對GIS中無拓撲閉曲線簡化的影響

高培超，劉 釗，謝美慧，田 琨

(清華大學(xué)土木工程系地球空間信息研究所，北京100084)

斷裂點位置對GIS中無拓撲閉曲線簡化的影響

高培超，劉 釗，謝美慧，田 琨

(清華大學(xué)土木工程系地球空間信息研究所，北京100084)

在回顧并總結(jié)無拓撲閉曲線簡化工作的基礎(chǔ)上，分別研究了斷裂點位置對地圖中人工地物和自然地物簡化的影響.采用經(jīng)典、常用的Douglas-Peucker方法作為簡化算法，研究結(jié)果表明斷裂點位置對人工地物和自然地物的簡化結(jié)果影響均較大，且在人工地物簡化過程中呈現(xiàn)一定的規(guī)律性.文章最后給出了斷裂點位置選擇的具體建議.

斷裂點;簡化;無拓撲;閉曲線;地理信息系統(tǒng)

數(shù)字地球的建設(shè)目前已初具成果，并在人類的生活中發(fā)揮越來越重要的作用［1-3］.矢量數(shù)據(jù)是地理信息系統(tǒng)［4］(Geographical Information System，GIS)中的主要數(shù)據(jù)類型，其數(shù)據(jù)量目前正隨著數(shù)字化工作的推進日益增多并趨向海量.無論從優(yōu)化存儲的角度還是多尺度顯示的角度來看，都有必要對矢量數(shù)據(jù)進行簡化.

矢量數(shù)據(jù)簡化主要包括散點抽稀、曲線(包括直線)簡化、面簡化(主要針對邊界線)3種類型，在曲線簡化和面簡化中，常用的算法有Douglas-Peucker(DP)［5，6］、Opheim［7］、SimpliPoly［8］等，但這些算法均是針對開曲線(Open curve)設(shè)計的，而在實際工作中，部分曲線和所有面邊界都是首尾相連的閉曲線(Closed curve，又稱為多邊形).

選擇斷裂點(Break point)位置，將閉曲線“拆剪”為開曲線，是閉曲線簡化工作中的首要任務(wù).對于該問題的處理方法，相關(guān)工作可分為3類.

(1)不涉及斷裂點問題.

文獻［9，10］在簡化閉曲線網(wǎng)的過程中，根據(jù)閉曲線間的相鄰關(guān)系提取公共邊(已是開曲線)，對公共邊進行簡化，然后再組合為新的閉曲線網(wǎng).在這種情況下，斷裂點位置已被客觀確定，無需主動選擇.

(2)涉及斷裂點問題但未闡明處理細節(jié).

文獻［11］在進行形狀匹配前簡化復(fù)雜面狀要素，文獻［12］對等高線進行簡化，文獻［13］的簡化對象是獨立的林權(quán)地塊邊界，文獻［14］對二值圖像的輪廓進行簡化，這些簡化對象均為無拓撲閉曲線，采用開曲線算法簡化時必須主動選擇斷裂點位置，但文中均未對斷裂方法進行細節(jié)闡述.文獻［15］提出了一種基于數(shù)學(xué)特征值對開曲線進行簡化的算法，并說明算法可擴展至閉曲線，但未對細節(jié)進行深入討論.

(3)涉及斷裂點問題并闡明處理細節(jié).

文獻［16］在簡化過程中根據(jù)等高線與其最大外接矩形的交點，將閉合的等高線劃分為左上、上右、右下、下左4段開曲線處理.文獻［17］在第二次全國土地調(diào)查成果縮編工作中，利用基本農(nóng)田數(shù)據(jù)將地類圖斑邊界分為若干片段，然后采用開曲線簡化算法處理.此2項工作通過不同的方法，在無拓撲閉曲線簡化過程中均主動選擇了斷裂點的位置.此外，也有文獻采用被動選擇(或隨機選取)的做法，例如，文獻［18］的主要工作是平滑柵格數(shù)據(jù)的矢量化結(jié)果，其在平滑閉合矢量曲線時認為，可以從任一節(jié)點處將閉合曲線斷裂成開曲線.文獻［19］在應(yīng)對閉曲線簡化并選擇斷裂點時，提出了一種近乎遍歷的方法，從而得到產(chǎn)生誤差最小的斷裂位置.

綜上所述，在無拓撲曲線簡化過程中，閉曲線的情況存在且不容忽略.閉曲線往往需要斷裂成開曲線處理，但對于斷裂點位置選擇問題的研究相對較少.因此，補充相關(guān)研究，了解斷裂點位置對簡化工作的影響，發(fā)現(xiàn)可能存在的規(guī)律，并提供合理的位置選擇方法具有一定的意義.

1 無拓撲閉曲線的特點

從拓撲學(xué)的角度來看，矢量數(shù)據(jù)結(jié)構(gòu)分為無拓撲矢量數(shù)據(jù)結(jié)構(gòu)(又稱為簡單數(shù)據(jù)結(jié)構(gòu))和拓撲矢量結(jié)構(gòu)(又稱為復(fù)雜數(shù)據(jù)結(jié)構(gòu)).無拓撲矢量數(shù)據(jù)結(jié)構(gòu)只存儲地理實體的位置信息(二維或三維)和屬性信息，將地理實體抽象為點、線、面3種基本類型，并不記錄地理實體間的拓撲關(guān)系.由于部分圖形應(yīng)用中無需基于拓撲關(guān)系的空間分析功能［20］，且無拓撲矢量數(shù)據(jù)結(jié)構(gòu)能夠更快速地在計算機中顯示［21］，因此無拓撲矢量數(shù)據(jù)經(jīng)常成為空間數(shù)據(jù)結(jié)構(gòu)的首選.

無拓撲閉曲線作為無拓撲矢量數(shù)據(jù)的一種，主要特點可總結(jié)如下.

(1)以坐標(biāo)對的形式記錄空間對象的位置信息.

(2)由于曲線閉合，因此曲線起點和終點的坐標(biāo)對相同.

(3)不包含拓撲關(guān)系，在表達多邊形網(wǎng)狀結(jié)構(gòu)時公共邊會被相鄰的多邊形獨立存儲.

2 簡化算法與評價指標(biāo)

2.1 DP算法

DP算法［5-6］是目前最經(jīng)典、使用最廣泛的一種矢量數(shù)據(jù)簡化算法，由Douglas和Peucker于1973年聯(lián)合發(fā)表，后人在DP算法基礎(chǔ)上做了很多優(yōu)化和改進，使之成為很多簡化算法的基礎(chǔ).DP算法的簡化流程如下.

(1)確定DP算法中的距離閾值ε.

(2)連接曲線首點和尾點，形成基準(zhǔn)線(若首尾點重合，則形成基準(zhǔn)點)，計算其余各點(即中間點)到基準(zhǔn)線的距離.如果所有中間點到基準(zhǔn)線的距離都小于ε，則刪除所有中間點，否則不刪除任何點，但將距離基準(zhǔn)線最遠的中間點標(biāo)記為分界點.

(3)分界點將曲線分割成2段，對每段重復(fù)執(zhí)行步驟2，直到每段曲線上的所有中間點到各自基準(zhǔn)線的距離均小于閾值ε.

(4)最終仍被保留的點即為簡化結(jié)果.

2.2 簡化質(zhì)量評價指標(biāo)

使用定量評價的方法計算由簡化操作引起的誤差，具體采用的評價指標(biāo)為長度變形(Length deformation，LD)、矢量偏差(Vector displacement，VD)［22］、面積畸變(Shape distortion，SD)［23］，其具體的計算方法分別是:

3 實驗

無拓撲閉曲線簡化是一項復(fù)雜的工作，實際應(yīng)用中常常需要聯(lián)合使用多種算法才能的獲得令人滿意的簡化效果［23］，但多種算法的存在將使得斷裂點位置影響的研究變得參數(shù)復(fù)雜.考慮到DP算法是目前最經(jīng)典、使用最廣泛的一種矢量數(shù)據(jù)簡化算法，也是當(dāng)今多種主流算法和最新算法的基礎(chǔ)［24-26］，本文將采用最基礎(chǔ)的DP算法簡化GIS無拓撲閉曲線，從而在基礎(chǔ)層次探究斷裂點位置對簡化工作的影響.

由于GIS的處理對象往往是地理空間以及空間中的地物，因此GIS無拓撲閉曲線主要是地物本身或輪廓線.在現(xiàn)實生活中，地物可分為人工地物和自然地物2類.人工地物如居民地、工程建筑物與構(gòu)筑物、道路等，其特點是比較規(guī)則，轉(zhuǎn)彎“急促”，且轉(zhuǎn)角以直角為主;自然地物如湖泊、河流等，廣義上的自然地物甚至包括等高線，其特點是線形自然，轉(zhuǎn)彎較為“緩和”，且轉(zhuǎn)角以鈍角為主.2類地物的特點不同，因此分2類進行實驗.

在實驗過程中，分別對仿真數(shù)據(jù)和真實數(shù)據(jù)進行測試.仿真數(shù)據(jù)是理想化、典型化、特殊化地物的代表，使用這樣的仿真數(shù)據(jù)進行實驗可以簡化冗余參數(shù)，方便分析實驗結(jié)果;真實數(shù)據(jù)是切實存在于地圖中的數(shù)據(jù)，真實數(shù)據(jù)比仿真數(shù)據(jù)復(fù)雜，數(shù)據(jù)特征更為一般化，對真實數(shù)據(jù)進行實驗可以驗證仿真實驗的結(jié)論.

3.1 人工地物

建筑物是人工地物中的典型代表，在一幅地圖中，大部分的建筑物輪廓線均較為規(guī)則，近似矩形.為方便探究斷裂點位置對簡化工作的影響，使用矩形仿真數(shù)據(jù)(如圖1).仿真數(shù)據(jù)中共有12個頂點，其中首頂點和尾頂點重合，坐標(biāo)值均為(1 000 cm，2 000 cm).所有相鄰頂點間隔相同，均為500 cm.5號點和11號點的坐標(biāo)分別為(3 000 cm，2 000 cm)和(1 000 cm，1 000 cm).為表示曲線的閉合性，在存儲矩形仿真數(shù)據(jù)時，重復(fù)儲存2次斷裂點，使斷裂點既成為曲線的起點，又成為曲線的終點.例如，以3號頂點為斷裂點的閉曲線中，共存儲13個頂點，點號順序依次是3～12、1～3;又如，以7號頂點為斷裂點的閉曲線中，共存儲13個頂點，點號順序依次是7～12、1～7.

圖1 矩形仿真數(shù)據(jù)Fig.1 Simulation data(a rectangle)

考慮到對稱性，若以7～12號點為斷裂點簡化曲線，簡化結(jié)果將和1～6號點相同.因此僅分別以1～6號點為斷裂點，使用DP算法(閾值為500 cm)簡化曲線，探究斷裂點位置對曲線簡化的影響.簡化結(jié)果如表1所示.

表1 簡化效果評價Tab.1 Assessments of the simplified results

分析表1中的數(shù)據(jù)，可得知當(dāng)矩形角點(1號點和5號點)作為斷裂點時，產(chǎn)生的長度變形、矢量偏差、面積畸變均為零;當(dāng)斷裂點處于2個角點的中點位置時(3號點)，產(chǎn)生的誤差也為零，但并不絕對(反例為6號點);位置對稱的斷裂點(2號點和4號點)產(chǎn)生的誤差大小相同.但斷裂點位置更靠近角點時，誤差是否更小，不同斷裂點位置產(chǎn)生的誤差是否呈線性變化等細節(jié)無從得知.

為進一步探究細節(jié)，仍使用圖1中的矩形，沿邊界將其等分為60份，由此獲得60個間距相等的頂點，其中相鄰頂點間距為100 cm.此時1號點位置不變，其余3個角點的序號依次變更為21、31、51.同樣考慮到對稱性，只研究1～30號點，將1～30號分別作為斷裂點，生成30條閉合曲線，分別使用DP算法(閾值為500 cm)進行簡化.在理想情況下，如果同時展示30條閉曲線的化簡結(jié)果，這些簡化后的閉曲線應(yīng)重合在一起，并與原矩形吻合，但實際效果卻如圖2所示.

圖2 同時展示30條簡化結(jié)果Fig.2 Displaying all the simplified results at the same time

計算壓縮率(剩余頂點數(shù)/原始頂點數(shù))、長度變形、矢量偏差、面積畸變，結(jié)果如圖3所示.

從圖3中可以確認上文結(jié)果，并綜合得出以下結(jié)論.

(1)斷裂點位置對壓縮率的影響較小，在大多數(shù)情況下，斷裂點位置的改變并不影響閉曲線的壓縮率.

(2)斷裂點位置對長度變形、矢量偏差、面積畸變的影響很大，并且值得注意的是此3項誤差指標(biāo)的變化曲線相似，峰值點幾乎相同.

圖3 斷裂點位置與簡化誤差的關(guān)系(人工地物)Fig.3 Relationships between the positions of breakpoints and the simplification errors(artificial features)

(3)當(dāng)以矩形角點作為斷裂點時，產(chǎn)生的長度變形、矢量偏差、面積畸變最小(此處為零).

(4)大多數(shù)情況下，斷裂點位置越靠近角點，產(chǎn)生的簡化誤差越小，但并不絕對.

(5)將斷裂點位置設(shè)在兩角點連線中點處并不一定能夠控制簡化誤差，例如同樣處于中點位置，11號點產(chǎn)生的誤差很小，但26號點產(chǎn)生的誤差卻很大.

(6)隨著斷裂點位置的順次改變，簡化誤差并不呈現(xiàn)線性變化趨勢，而是無規(guī)律地波動變化.

為進一步驗證實驗結(jié)果，將遙感圖像上的2塊農(nóng)作物植被輪廓線作為對象分別進行簡化(見圖4).與仿真數(shù)據(jù)不同，這些輪廓線并非標(biāo)準(zhǔn)矩形.每條輪廓線上的頂點個數(shù)均大于100，因此數(shù)據(jù)高度冗余.實驗結(jié)果表明，當(dāng)以角點作為斷裂點時，產(chǎn)生的長度變形、矢量偏差、面積畸變明顯變小(但并非一定最小).實驗結(jié)果完善了上述第3條結(jié)論，并確認了其余結(jié)論.

3.2 自然地物

地圖上的自然地物包括湖泊邊界、河流線、等高線等，自然地物與人工地物最大的區(qū)別在于線形較為自然，轉(zhuǎn)彎“緩和”并以鈍角(而非直角)為主.本文以我國喀納斯冰川地區(qū)等高線數(shù)據(jù)①數(shù)據(jù)來源:中國西部環(huán)境與生態(tài)科學(xué)數(shù)據(jù)中心(http://westdc.westgis.ac.cn)為例，簡化其中的閉合等高線，如圖5所示.

圖4 農(nóng)作物植被輪廓線Fig.4 Contours of the land used for crop production

圖5 閉合的等高線Fig.5 Closed contours

這里給出圖5中最外圍等高線的簡化評價結(jié)果，該條等高線共有91個頂點，全長為6 926.232 8個單位，平均點間距約為770個單位.分別以1～91號點為斷裂點，以數(shù)值77為閾值，使用DP算法簡化等高線.然后依次計算每項簡化結(jié)果的壓縮率、長度變形、矢量偏差和面積畸變.最終計算結(jié)果如圖6所示.

圖6 斷裂點位置與簡化誤差的關(guān)系(自然地物)Fig.6 Relationships between the positions of breakpoints and the simplification errors(natural features)

從圖6中可以看到，當(dāng)簡化對象為自然地物時，簡化誤差并未變現(xiàn)出一定的規(guī)律性.

(1)隨著斷裂點位置的改變，閉曲線的壓縮率呈上下波動狀變化，但浮動范圍較小(上下浮動值約為4%).

(2)斷裂點位置對長度變形、矢量偏差、面積畸變的影響很大，且影響不同.

(3)當(dāng)角點(轉(zhuǎn)角較大的點，如18號點)作為斷裂點時，產(chǎn)生的長度變形、矢量偏差、面積畸變并未達到最值.

(4)壓縮率、長度變形、矢量偏差、面積畸變的變化均不具有規(guī)律性，且兩兩之間并無明顯相關(guān)性.

為進一步驗證實驗結(jié)果，將我國青海湖的輪廓線作為對象進行簡化(圖7).該輪廓線上共有560個頂點，具有一定的數(shù)據(jù)冗余.循環(huán)執(zhí)行簡化操作560次，逐次將每個頂點作為斷裂點，并計算每次簡化后的各項誤差指標(biāo).實驗結(jié)果確認了上述結(jié)論，當(dāng)簡化對象為自然地物時，簡化誤差并未變現(xiàn)出一定的規(guī)律性.

圖7 青海湖輪廓線Fig.7 The contour of the Qinghai Lake

4 結(jié)論

本文研究表明，在無拓撲閉曲線簡化過程中，需要考慮斷裂點位置的設(shè)置問題.盡管斷裂點位置不影響無拓撲閉曲線的形狀信息表達，卻對簡化質(zhì)量和效果有著不容忽視的影響.本文研究根據(jù)屬性和幾何特征的不同，將待簡化對象分為人工地物和自然地物兩大類，并以仿真矩形和等高線為典型代表，探究了斷裂點位置對2類地物的影響.結(jié)論如下.

(1)斷裂點位置對簡化人工地物和自然地物均有較大影響.

(2)斷裂點位置對人工地物的影響具有規(guī)律性，當(dāng)斷裂點位置位于角點處時，簡化誤差較小.

(3)斷裂點位置對自然地物的影響具有波動性，但簡化誤差并沒有表現(xiàn)出明顯的規(guī)律性.

(4)在簡化人工地物時，長度變形、矢量誤差、面積畸變的變化趨勢相關(guān)性高，在簡化自然地物時變化趨勢的相關(guān)性低.

(5)在簡化工作中，如果待簡化對象為城鎮(zhèn)地圖(含有大量的人工地物)，應(yīng)特別注意斷裂點位置的選取規(guī)則，建議在編寫代碼時首選角點.

［1］Goodchild M F，Guo Huadong，Annoni A，et al.Nextgeneration digital earth［J］.Proceedings of the National Academy of Sciences，2012，109(28):11088-11094.

［2］Gao Peichao，Liu Zhao，Xie Meihui，et al.The Development of and Prospects for Private Cloud GIS in China［J］.Asian Journal of Geoinformatics，2014，14(4):30-38.

［3］郭華東.數(shù)字地球:10年發(fā)展與前瞻［J］.地球科學(xué)進展，2009(09):955-962.

［4］劉釗，高培超，閔世平，等.一種大曲率線狀實體的三維可視化方法［J］.國土資源遙感，2014，26(3):43-47.

［5］費立凡，何津，馬晨燕，等.三維Douglas-Peucker算法及其在DEM自動綜合中的應(yīng)用研究［J］.測繪學(xué)報，2006，35(3):278-284.

［6］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］.The Canadian Cartographer，1973，10(2): 112-122.

［7］Mcmaster R B.Automated line generalization［J］.Cartographica:The International Journal for Geographic Information and Geovisualization，1987，24(2):74-111.

［8］Chuon C，Guha S，Janecek P，et al.Simplipoly:Curvature-based polygonal curve simplification［J］.International Journal of Computational Geometry＆Applications，2011，21(4): 417-429.

［9］黃萬里，戴文遠，余珊.基于面積保持的Douglas-Peucker改進算法的多邊形化簡［J］.科學(xué)技術(shù)與工程，2009 (24):7325-7328.

［10］禹銘月，王衛(wèi)安.多邊形形狀簡化及其質(zhì)量評價［J］.測繪與空間地理信息，2011(06):152-155.

［11］付仲良，邵世維.復(fù)雜面狀矢量要素快速形狀匹配方法［J］.測繪通報，2011，3(03):26-28.

［12］紀(jì)洋，武文波，楊曉偉.等高線自動矢量化的后處理［J］.遼寧工程技術(shù)大學(xué)學(xué)報:自然科學(xué)版，2008(S1):37-39.

［13］胡蕓，方陸明.一種利用拓撲轉(zhuǎn)換消除多邊形數(shù)據(jù)壓縮裂縫的方法［J］.浙江農(nóng)林大學(xué)學(xué)報，2011(04):597-600.

［14］谷柱，武衛(wèi)，高翌飛，等.X射線安檢設(shè)備測試圖像分割方法［J］.無損檢測，2009(03):169-172.

［15］Salotti M.Optimal polygonal approximation of digitized curves using the sum of square deviations criterion［J］.Pattern Recognition，2002，35(2):435-443.

［16］朱強，武芳，翟仁健.基于通視性原理的等高線化簡算法研究［J］.中國圖象圖形學(xué)報，2009(02):359-364.

［17］張俊峰，費立凡，黃麗娜，等.第二次全國土地調(diào)查成果的多比例尺縮編方法研究［J］.測繪科學(xué)，2011(02):121 -123.

［18］Yue Jianwei，Wang Jun，Wang Bin.A fast method of smoothing vector graph converted from raster image［J］.The International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences，2008，XXXVII(B7):943-945.

［19］Perez J，Vidal E.Optimum polygonal approximation of digitized curves［J］.Pattern Recognition Letters，1994，15(8): 743-750.

［20］羅芳，艾廷華，王洪.閉合坐標(biāo)鏈多邊形數(shù)據(jù)的拓撲關(guān)系快速構(gòu)建［J］.武漢大學(xué)學(xué)報:信息科學(xué)版，2004，29 (6):558-561.

［21］郭嘉亮.基于VxWorks的ECDIS基礎(chǔ)顯示平臺研究［D］.哈爾濱:哈爾濱工程大學(xué)，2011.

［22］鄭春燕，郭慶勝，胡華科.基于蟻群優(yōu)化算法的線狀目標(biāo)簡化模型［J］.測繪學(xué)報，2011，40(05):635-638.

［23］Park W，Yu K.Hybrid line simplification for cartographic generalization［J］.Pattern Recognition Letters，2011，32 (9):1267-1273.

［24］Pallero J.Robust line simplification on the plane［J］. Computers＆Geosciences，2013，61:152-159.

［25］Song Xiaomei，Cheng Changxiu，Zhou Chenghu，et al. Gestalt-based douglas-peucker algorithm to keep shape similarity and area consistency of polygons［J］.Sensor Letters，2013，11 (6-7):1015-1021.

［26］Gorman G J，Piggott M D，Pain C C.Shoreline approximation for unstructured mesh generation［J］.Computers＆Geosciences，2007，33(5):666-677.

Effect of Breakpoints Position on Simplification of Closed Curves without Topology

GAO Pei-chao，LIU Zhao，XIE Mei-hui，TIAN Kun
(Institute of Geomatics，Department of Civil Engineering，Tsinghua University，Beijing 100084，China)

This paper reviews the simplification of closed curves without topology，and studies the effects of the position of breakpoints on simplification both in terms of artificial and natural features.The classical Douglas-Peucker algorithm is adopted，and the research result shows that the position of breakpoints can influence both artificial and natural features in the simplification process.Furthermore，there are some influencing rules in the process for artificial features.Specific tips on breakpoints selection are given at the end of the article.

breakpoint;simplification;without topology;closed curve;Geographical Information System(GIS)

P208

A

(責(zé)任編輯 蘇曉東)

1004-8820(2015)02-0090-06

10.13951/j.cnki.37-1213/n.2015.02.003

2014-08-22

高培超(1991-)，男，河南長葛人，碩士研究生.

劉釗(liuz@mail.tsinghua.edu.cn)，副教授，主要研究方向為地理信息系統(tǒng)與遙感.