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

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

斷裂點(diǎn)位置對(duì)GIS中無(wú)拓?fù)溟]曲線簡(jiǎn)化的影響

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

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

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

斷裂點(diǎn);簡(jiǎn)化;無(wú)拓?fù)?閉曲線;地理信息系統(tǒng)

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

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

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

(1)不涉及斷裂點(diǎn)問(wèn)題.

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

(2)涉及斷裂點(diǎn)問(wèn)題但未闡明處理細(xì)節(jié).

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

(3)涉及斷裂點(diǎn)問(wèn)題并闡明處理細(xì)節(jié).

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

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

1 無(wú)拓?fù)溟]曲線的特點(diǎn)

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

無(wú)拓?fù)溟]曲線作為無(wú)拓?fù)涫噶繑?shù)據(jù)的一種，主要特點(diǎn)可總結(jié)如下.

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

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

(3)不包含拓?fù)潢P(guān)系，在表達(dá)多邊形網(wǎng)狀結(jié)構(gòu)時(shí)公共邊會(huì)被相鄰的多邊形獨(dú)立存儲(chǔ).

2 簡(jiǎn)化算法與評(píng)價(jià)指標(biāo)

2.1 DP算法

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

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

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

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

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

2.2 簡(jiǎn)化質(zhì)量評(píng)價(jià)指標(biāo)

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

3 實(shí)驗(yàn)

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

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

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

3.1 人工地物

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

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

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

表1 簡(jiǎn)化效果評(píng)價(jià)Tab.1 Assessments of the simplified results

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 自然地物

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

(3)斷裂點(diǎn)位置對(duì)自然地物的影響具有波動(dòng)性，但簡(jiǎn)化誤差并沒(méi)有表現(xiàn)出明顯的規(guī)律性.

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

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

［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é)進(jìn)展，2009(09):955-962.

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

［5］費(fèi)立凡，何津，馬晨燕，等.三維Douglas-Peucker算法及其在DEM自動(dòng)綜合中的應(yīng)用研究［J］.測(cè)繪學(xué)報(bào)，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］黃萬(wàn)里，戴文遠(yuǎn)，余珊.基于面積保持的Douglas-Peucker改進(jìn)算法的多邊形化簡(jiǎn)［J］.科學(xué)技術(shù)與工程，2009 (24):7325-7328.

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

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

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

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

［14］谷柱，武衛(wèi)，高翌飛，等.X射線安檢設(shè)備測(cè)試圖像分割方法［J］.無(wú)損檢測(cè)，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］朱強(qiáng)，武芳，翟仁健.基于通視性原理的等高線化簡(jiǎn)算法研究［J］.中國(guó)圖象圖形學(xué)報(bào)，2009(02):359-364.

［17］張俊峰，費(fèi)立凡，黃麗娜，等.第二次全國(guó)土地調(diào)查成果的多比例尺縮編方法研究［J］.測(cè)繪科學(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ù)的拓?fù)潢P(guān)系快速構(gòu)建［J］.武漢大學(xué)學(xué)報(bào):信息科學(xué)版，2004，29 (6):558-561.

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

［22］鄭春燕，郭慶勝，胡華科.基于蟻群優(yōu)化算法的線狀目標(biāo)簡(jiǎn)化模型［J］.測(cè)繪學(xué)報(bào)，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-)，男，河南長(zhǎng)葛人，碩士研究生.

劉釗(liuz@mail.tsinghua.edu.cn)，副教授，主要研究方向?yàn)榈乩硇畔⑾到y(tǒng)與遙感.