空間數(shù)據(jù)組織算法課件

1空間數(shù)據(jù)組織算法《地理信息系統(tǒng)算法基礎(chǔ)》第六章1空間數(shù)據(jù)組織算法《地理信息系統(tǒng)算法基礎(chǔ)》第六章2本講內(nèi)容1矢量數(shù)據(jù)的壓縮2柵格數(shù)據(jù)的壓縮3拓?fù)潢P(guān)系的生成

2本講內(nèi)容1矢量數(shù)據(jù)的壓縮31矢量數(shù)據(jù)的壓縮矢量數(shù)據(jù)的壓縮包括兩個(gè)方面的內(nèi)容：一是在不擾亂拓?fù)潢P(guān)系的前提下，對(duì)采樣點(diǎn)數(shù)據(jù)進(jìn)行合理的抽稀；二是對(duì)矢量坐標(biāo)數(shù)據(jù)重新進(jìn)行編碼，以減少所需要的存儲(chǔ)空間。矢量數(shù)據(jù)的壓縮往往是不可逆的，數(shù)據(jù)壓縮后，數(shù)據(jù)量變小了，數(shù)據(jù)的精度降低了。31矢量數(shù)據(jù)的壓縮矢量數(shù)據(jù)的壓縮包括兩個(gè)方面的內(nèi)容：41矢量數(shù)據(jù)的壓縮1.1間隔取點(diǎn)法1.2垂距法和偏角法1.3道格拉斯-普克法1.4光欄法1.5曲線壓縮算法的比較1.6面域的數(shù)據(jù)壓縮算法41矢量數(shù)據(jù)的壓縮1.1間隔取點(diǎn)法51.1間隔取點(diǎn)法原理：每隔K個(gè)點(diǎn)取一點(diǎn)，或舍去那些離已選點(diǎn)比規(guī)定距離更近的點(diǎn)，但首、末點(diǎn)一定要保留，如圖5.1所示。

優(yōu)缺點(diǎn)：可大量壓縮數(shù)字化儀用連續(xù)方法獲取的點(diǎn)列中的點(diǎn)、曲率顯著變化的點(diǎn)，但不一定能恰當(dāng)?shù)乇Ａ舴较蛏锨曙@著變化的點(diǎn)。51.1間隔取點(diǎn)法原理：每隔K個(gè)點(diǎn)取一點(diǎn)，或舍去那些離已選61.2垂距法和偏角法原理：按垂距或偏角的限差，選取符合或超過限差的點(diǎn)。優(yōu)缺點(diǎn)：不能同時(shí)考慮相鄰點(diǎn)間的方向與距離，且有可能舍去不該舍去的點(diǎn)，但較前一種方法有進(jìn)步。61.2垂距法和偏角法原理：按垂距或偏角的限差，選取符合或71.3道格拉斯-普克法

原理：將一條曲線首、末點(diǎn)連一條直線，求出其余各點(diǎn)到該直線的距離，選其最大者與規(guī)定的臨界值相比較，若大于臨界值，則離該直線距離最大的點(diǎn)保留，否則將直線兩端間各點(diǎn)全部舍去。

如圖5.3所示，經(jīng)數(shù)據(jù)采樣得到的曲線MN由點(diǎn)序{P1，P2，P3，…，Pn}組成，n個(gè)點(diǎn)的坐標(biāo)集為(x1,y1),(x2,y2),(x3,y3),…,(xn,yn)。其中P1，Pn代分別對(duì)應(yīng)曲線的起點(diǎn)M和終點(diǎn)N。根據(jù)應(yīng)用需要和數(shù)據(jù)精度要求，給定控制數(shù)據(jù)壓縮的極差為ε，ε表示為被舍棄的點(diǎn)偏離特征點(diǎn)連線之間的垂直距離。71.3道格拉斯-普克法原理：將一條曲線首、末點(diǎn)連一條直81.3道格拉斯-普克法曲線的空間數(shù)據(jù)壓縮過程如下：第一步：確定曲線MN對(duì)應(yīng)弦的直線方程。由起點(diǎn)M、終點(diǎn)N建立直線―方程為將上式化簡為一般形式為：Ax+By+C=0第二步：求曲線MN上各點(diǎn)Pi到弦線MN的距離di。

Pi(xi，yi)到弦線MN的距離為第三步：求距離di的最大值dh第四步：比較dh與ε的大小，并計(jì)算開關(guān)Q：81.3道格拉斯-普克法曲線的空間數(shù)據(jù)壓縮過程如下：91.3道格拉斯-普克法第五步：決定取舍，提取中間特征點(diǎn)。(1)如果Q=0，則直接可以用弦線MN(M、N為特征點(diǎn))代替曲線MN；轉(zhuǎn)第六步。(2)如果Q=1，則將dh所對(duì)應(yīng)的點(diǎn)Pi(Xi，yi)抽出，暫時(shí)作為中間特征點(diǎn)；然后連接新弦線MPj；轉(zhuǎn)第一步(以MPj已代替MN，繼續(xù)計(jì)算和判斷)。若Q=0，則可以用弦線MPj代替曲線MPj；將Pj作為中間特征點(diǎn)取出；順序排在M點(diǎn)之后，成為繼M之后的第一個(gè)中間特征點(diǎn)；并連接PjN，轉(zhuǎn)第一步（以PjN代替MN，繼續(xù)計(jì)算和判斷)……91.3道格拉斯-普克法第五步：決定取舍，提取中間特征點(diǎn)。101.3道格拉斯-普克法

若Q=1，則不可以用弦線MPj代替曲線MPj；找到此時(shí)dh所對(duì)應(yīng)的點(diǎn)Pk，并連接新弦線MPk；轉(zhuǎn)第一步(以MPk代替MN，繼續(xù)計(jì)算和判斷)……

第六步：形成新的數(shù)據(jù)文件。將所有提取出的中間特征點(diǎn)從起點(diǎn)M開始，順序排列至終點(diǎn)N，并寫入新的數(shù)據(jù)文件，即得到化簡后的折線的數(shù)據(jù)文件。101.3道格拉斯-普克法若Q=1，則不可以111.3道格拉斯-普克法如圖5.3所示，曲線MN的特征點(diǎn)提取過程如下：(1)找到曲線MN上dh對(duì)應(yīng)點(diǎn)位為1號(hào)點(diǎn)；經(jīng)判斷可以用弦線M1代替曲線M1，故1號(hào)點(diǎn)是繼似點(diǎn)之后提取出的第一個(gè)特征點(diǎn)；(2)連接弦線1N；經(jīng)判斷，不可以用弦線1N代替曲線1N；找到曲線lN上dh的對(duì)應(yīng)點(diǎn)位為2號(hào)點(diǎn)；故連接1、2號(hào)點(diǎn)之弦線12；經(jīng)判斷，還是不可以用弦線12代替曲線12；找到曲線12上dh的對(duì)應(yīng)點(diǎn)位為3號(hào)點(diǎn)；再連接1、3號(hào)點(diǎn)之弦線13；經(jīng)判斷，可以用弦線13代替曲線13；故3號(hào)點(diǎn)是繼1號(hào)點(diǎn)之后提取出的第二個(gè)特征點(diǎn)；111.3道格拉斯-普克法如圖5.3所示，曲線MN的特征點(diǎn)121.3道格拉斯-普克法(3)連接弦線3N；經(jīng)判斷，不可以用弦線3N代替曲線3N；找到曲線3N上之dh的對(duì)應(yīng)點(diǎn)位仍為2號(hào)點(diǎn)；然后，連接3、2號(hào)點(diǎn)之弦線32；經(jīng)判斷，可以用弦線32代替曲線32；故2號(hào)點(diǎn)是繼1號(hào)點(diǎn)、3號(hào)點(diǎn)之后提取出的第三個(gè)特征點(diǎn)；(4)連接2、N號(hào)點(diǎn)之弦線2N；經(jīng)判斷，可以用弦線2N代替曲線2N；中間特征點(diǎn)提取結(jié)束。至此可知，曲線MN可以用特征點(diǎn)M、1、3、2、N順序連接的折線簡化表示。

121.3道格拉斯-普克法(3)連接弦線3N；經(jīng)判斷，不可131.4光欄法

原理：預(yù)先定義的一個(gè)扇形(“喇叭口”），根據(jù)曲線上各節(jié)點(diǎn)是在扇形外還是在扇形內(nèi)，決定節(jié)點(diǎn)是保留還是舍去。設(shè)有曲線點(diǎn)列{Pi}，i=1，2，…，n，“光欄口徑”為d(由用戶自己定義），則該方法實(shí)施的具體步驟：(1)連接p1和p2，過p2點(diǎn)作一條垂直于p1p2的直線，在該垂線上取兩點(diǎn)a1和a2，使a1p1=a2p2=d/2，此時(shí)a1和a2為“光欄”邊界點(diǎn)，p1與a1、p1與a2的連線為以P1為頂點(diǎn)的扇形的兩條邊，這就定義了一個(gè)扇形(這個(gè)扇形的口朝向曲線的前進(jìn)方向，邊長是任意的）。通過p1并在扇形內(nèi)的所有直線都具有這種性質(zhì)，即p1p2上各點(diǎn)到這些直線的垂距都不大于d/2。131.4光欄法原理：預(yù)先定義的一個(gè)扇形(“喇叭口”），141.4光欄法(2)若p3點(diǎn)在扇形內(nèi)，則舍丟p2點(diǎn)。然后連接p1和p3，過p3作p1p3的垂線，該垂線與前面定義的扇形邊交于c1和c2。在垂線上找到b1和b2點(diǎn)，使p3b1=p3b2=d/2，若b1和b2點(diǎn)落在原扇形外面（圖5.4中為b2點(diǎn)），則用c1或c2取代(圖5.4中由c2取代b2)。此時(shí)用p1b1和p1c2定義一個(gè)新的扇形，這當(dāng)然是口徑(b1c2)縮小了的“光欄”。(3)檢查下一節(jié)點(diǎn)，若該點(diǎn)在新扇形內(nèi)，則重復(fù)第(2)步；直到發(fā)現(xiàn)有一個(gè)節(jié)點(diǎn)在最新定義的扇形外為止。(4)當(dāng)發(fā)現(xiàn)在扇形外的節(jié)點(diǎn)，如圖5.4中的p4，此時(shí)保留點(diǎn)p3，以p3作為新起點(diǎn)，重復(fù)(1)?(2)步。如此繼續(xù)下去，直到整個(gè)點(diǎn)列檢測(cè)完為止。所有被保留的點(diǎn)（含首、末點(diǎn)），順序地構(gòu)成了簡化后的新點(diǎn)列。141.4光欄法(2)若p3點(diǎn)在扇形內(nèi)，則舍丟p2點(diǎn)。然后151.4光欄法151.4光欄法161.5曲線壓縮算法的比較

評(píng)價(jià)依據(jù)：壓縮后的總長度、原曲線及壓縮后曲線的線性位移(矢高和面積)

等。線性位移量評(píng)價(jià)：道格拉斯-普克法具有最小的線性位移；偏角法在所有的壓縮水平上較其他3種方法具有更大的線性位移量，但僅依據(jù)矢高位移量又很難對(duì)間隔取點(diǎn)法的算法作出結(jié)論，而在舍去30%-70%的點(diǎn)時(shí)，無論按矢高位移量還是按面積位移量來評(píng)價(jià)，垂距法顯然較偏角法和間隔取點(diǎn)法好161.5曲線壓縮算法的比較評(píng)價(jià)依據(jù)：壓縮后的總長度、原曲171.5曲線壓縮算法的比較結(jié)論：淘汰的點(diǎn)數(shù)越多，它們的壓縮效果越趨于一致。在一般情況下，道格拉斯-普克方法壓縮效果占優(yōu)，其次是垂距法、間隔取點(diǎn)法和偏角法，但道格拉斯-普克方法需對(duì)整條曲線完成數(shù)字化后方能進(jìn)行壓縮，且計(jì)算工作量較大。光欄法則不僅算法嚴(yán)密，能按給定閾值保留曲線特征點(diǎn)，并能實(shí)時(shí)處理，運(yùn)算量少，占用內(nèi)存少。171.5曲線壓縮算法的比較結(jié)論：淘汰的點(diǎn)數(shù)越多，它們的壓縮181.6面域的數(shù)據(jù)壓縮算法面域空間數(shù)據(jù)的壓縮過程可以看成是組成其邊界的曲線段的分別壓縮，每段邊界曲線的壓縮過程如前所述。

封閉曲線的數(shù)據(jù)壓縮公共節(jié)點(diǎn)的取舍問題181.6面域的數(shù)據(jù)壓縮算法面域空間數(shù)據(jù)的壓縮過程可以看成是191.6面域的數(shù)據(jù)壓縮算法封閉曲線的數(shù)據(jù)壓縮面域由首尾相連的封閉曲線組成。此時(shí)，可以人為地將該封閉線分割為首尾相連的兩段曲線，然后就可以按前述方法進(jìn)行壓縮。曲線分割的原則是：（1）原節(jié)點(diǎn)是分割點(diǎn)之一；（2）離原節(jié)點(diǎn)最遠(yuǎn)的下一節(jié)點(diǎn)是分割點(diǎn)之二。191.6面域的數(shù)據(jù)壓縮算法封閉曲線的數(shù)據(jù)壓縮201.6面域的數(shù)據(jù)壓縮算法如圖5.7所示，多邊形P的邊界曲線由從節(jié)點(diǎn)A出發(fā)的曲線封閉而成；其中曲線上B點(diǎn)離節(jié)點(diǎn)A最遠(yuǎn)。因而，多邊形P的邊界曲線可以分割為AMB和BNA兩段，進(jìn)而對(duì)曲線段AMB和BNA分別進(jìn)行壓縮。201.6面域的數(shù)據(jù)壓縮算法如圖5.7所示，多邊形P的邊界曲211.6面域的數(shù)據(jù)壓縮算法公共節(jié)點(diǎn)的取舍問題在某些特定情況下，面域的邊界曲線由多段首尾相連的曲線連接而成，其壓縮可以分段進(jìn)行。此時(shí)各段曲線的起點(diǎn)和終點(diǎn)必然作為特征點(diǎn)提取出來，因而可能產(chǎn)生數(shù)據(jù)冗余。比如，當(dāng)前后曲線段過渡時(shí)很平緩，曲線段的公共節(jié)點(diǎn)可以不成為特征點(diǎn)，即該點(diǎn)前后的兩段曲線可以直接用該點(diǎn)前后的兩個(gè)特征點(diǎn)的連線來代替。211.6面域的數(shù)據(jù)壓縮算法公共節(jié)點(diǎn)的取舍問題221.6面域的數(shù)據(jù)壓縮算法如圖5.9所示，1、2號(hào)點(diǎn)分別是面域P的邊界曲線AB、BC段的內(nèi)部特征提取點(diǎn)，因而可以用弦1B、B2分別代替曲線1B和B2。而實(shí)際上，整個(gè)曲線1B2仍可以用弦12來代替。221.6面域的數(shù)據(jù)壓縮算法231.6面域的數(shù)據(jù)壓縮算法在處理面域空間數(shù)據(jù)壓縮時(shí)，可以在邊界曲線分段壓縮的基礎(chǔ)上，增加一個(gè)步驟，即對(duì)邊界曲線的端點(diǎn)進(jìn)行可刪性檢驗(yàn)：如果前一曲線最后提取的中間特征點(diǎn)與后一曲線最先提取的中間特征點(diǎn)之間的曲線滿足極差控制條件，則兩條曲線的連接節(jié)點(diǎn)可以刪減；否則，不可刪減。由于各段邊界曲線的數(shù)據(jù)文件要重新生成，所以當(dāng)兩段曲線的公共節(jié)點(diǎn)刪減之后，相當(dāng)于兩條曲線合并為一條曲線。此時(shí)可能會(huì)擾亂拓?fù)潢P(guān)系(如曲線AB或BC為多邊形的公共邊，或AB和BC均為多邊形的公共邊），因此在處理公共節(jié)點(diǎn)的取舍時(shí)要慎重，應(yīng)該對(duì)此加以限制。231.6面域的數(shù)據(jù)壓縮算法在處理面域空間數(shù)據(jù)壓縮時(shí)，可以在242柵格數(shù)據(jù)的壓縮2.1鏈?zhǔn)骄幋a2.2游程長度編碼2.3塊式編碼2.4差分映射法2.5四叉樹編碼242柵格數(shù)據(jù)的壓縮2.1鏈?zhǔn)骄幋a252柵格數(shù)據(jù)的壓縮柵格數(shù)據(jù)文件記錄有3個(gè)基本方式：基于像元、基于層和基于面域。共同點(diǎn)：對(duì)像元坐標(biāo)和屬性的記錄。因此基于柵格的空間數(shù)據(jù)壓縮的實(shí)質(zhì)是研究柵格數(shù)據(jù)的編碼，通過編碼盡量減少像元數(shù)量的存儲(chǔ)。分類：柵格數(shù)據(jù)的壓縮分為無損壓縮技術(shù)和有損壓縮技術(shù)。252柵格數(shù)據(jù)的壓縮柵格數(shù)據(jù)文件記錄有3個(gè)基本方式：基于像262柵格數(shù)據(jù)的壓縮無損壓縮方法利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真，但壓縮率受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，一般為2：1~5:1。有損壓縮方法利用了數(shù)據(jù)在使用中存在某些成分不敏感的特性，允許壓縮過程中損失一定的信息；雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對(duì)數(shù)據(jù)內(nèi)涵的影響較小，卻換來了大得多的壓縮比。262柵格數(shù)據(jù)的壓縮無損壓縮方法利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮272.1鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a又稱為弗里曼鏈碼（Freeman，1961年）或邊界鏈碼。如圖5.10所示，其中的多邊形邊界可表示為：由某一原點(diǎn)開始并按某些基本方向確定的單位矢量鏈?；痉较蚩啥x為:東=0，東南=1，南=2，西南=3，西=4，西北=5，北=6，東北=7，8個(gè)基本方向。272.1鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a又稱為弗里曼鏈碼（Freeman282.1鏈?zhǔn)骄幋a如果確定原點(diǎn)為像元（10，1)，則該多邊形邊界按順時(shí)針方向的鏈?zhǔn)骄幋a(圖5.11)為：10，1，7，0，1，0，7，1，7,0，0,2，3，2，2，1，0，7，0，0，0，0，2，4，3，4，4，3，4，4，5，4，5，4，5，4，5，4，6，6。282.1鏈?zhǔn)骄幋a如果確定原點(diǎn)為像元（10，1)，則該多邊292.1鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a的優(yōu)點(diǎn)：鏈?zhǔn)骄幋a對(duì)多邊形的表示具有很強(qiáng)的數(shù)據(jù)壓縮能力，且具有一定的運(yùn)算功能，如面積和周長計(jì)算等，探測(cè)邊界急彎和凹進(jìn)部分等都比較容易；鏈?zhǔn)骄幋a的缺點(diǎn)是對(duì)疊置運(yùn)算如組合、相交等則很難實(shí)施，對(duì)局部修改將改變整體結(jié)構(gòu)，效率較低，而且由于鏈碼以每個(gè)區(qū)域?yàn)閱挝淮鎯?chǔ)邊界，相鄰區(qū)域的邊界則被重復(fù)存儲(chǔ)而產(chǎn)生冗余。292.1鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a的優(yōu)點(diǎn)：鏈?zhǔn)骄幋a對(duì)多邊形的表示具302.2游程長度編碼

游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程長度編碼結(jié)構(gòu)是逐行將相鄰?fù)档木W(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。游程長度編碼結(jié)構(gòu)的建立方法是：將柵格矩陣的數(shù)據(jù)序列X1，X2，…，Xn，映射為相應(yīng)的二元組序列(Ai，Pi），i=1，2,…，K，且K≤n。其中，A為屬性值，P為游程，K為游程序號(hào)。302.2游程長度編碼游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程長度編312.2游程長度編碼游程長度編碼這種數(shù)據(jù)結(jié)構(gòu)特別適用于二值圖像數(shù)據(jù)的表示

游程編碼能否壓縮數(shù)據(jù)量，主要決定于柵格數(shù)據(jù)的性質(zhì)，通常可通過事先測(cè)試，估算圖層的數(shù)據(jù)冗余度Re：Re=1-Q/mn312.2游程長度編碼游程長度編碼這種數(shù)據(jù)結(jié)構(gòu)特別適用于二值322.2游程長度編碼Q為圖層內(nèi)相鄰屬性值變化次數(shù)的累加和；m為圖層網(wǎng)格的行數(shù)；n為圖層網(wǎng)格的列數(shù)。當(dāng)Re的值大于1/5的情況下，表明柵格數(shù)據(jù)的壓縮可取得明顯的效果。壓縮效果可由壓縮比S=n/K來表征，即壓縮比的值愈大，表示壓縮效果愈顯著。322.2游程長度編碼Q為圖層內(nèi)相鄰屬性值變化次數(shù)的累加和；332.3塊式編碼

塊式編碼是將游程長度編碼擴(kuò)大到二維的情況，把多邊形范圍劃分成由像元組成的正方形，然后對(duì)各個(gè)正方形進(jìn)行編碼。塊式編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置（行號(hào)，列號(hào))和半徑，再加上記錄單元的代碼組成。根據(jù)這一編碼原則，圖5.15所示多邊形只需17個(gè)單位正方形，9個(gè)4單位的正方形和1個(gè)16單位的正方形就能完整表示，總共要57個(gè)數(shù)據(jù)，其中27對(duì)坐標(biāo)，3個(gè)塊的半徑。332.3塊式編碼塊式編碼是將游程長度編碼擴(kuò)大到二維的情況342.3塊式編碼塊式編碼的特點(diǎn)：一個(gè)多邊形所能包含的正方形越大，多邊形的邊界越簡單，塊式編碼的效果越好。游程和塊式編碼都對(duì)大的復(fù)雜多邊形效果并不好。塊式編碼在合并、插入、檢查延伸性、計(jì)算面積等操作時(shí)有明顯的優(yōu)越性。342.3塊式編碼塊式編碼的特點(diǎn)：一個(gè)多邊形所能包含的正方形352.4差分映射法

差分映射法，就是選擇某一參照值對(duì)有關(guān)柵格的屬性值進(jìn)行求差運(yùn)算，根據(jù)差值得到一個(gè)新的柵格數(shù)據(jù)層。參照值的選擇有多種方式，即分行選取和全區(qū)選取。若分行選取，則可選為該行首列的屬性值，也可以選為該行的屬性平均值；若全區(qū)選取，則可選為首行首列的屬性值，也可以選為全區(qū)的屬性平均值。352.4差分映射法差分映射法，就是選擇某一參照值對(duì)有關(guān)柵362.4差分映射法圖5.16為柵格數(shù)據(jù)示例。圖5.17所示為按分行選取方式，以行首屬性值為參照，對(duì)圖5.16作差分映射后的結(jié)果。可以看出，經(jīng)差分映射處理后，除第一列外，其余柵格的數(shù)據(jù)出現(xiàn)為零、位數(shù)降低或數(shù)字減少。362.4差分映射法圖5.16為柵格數(shù)據(jù)示例。圖5.17所示372.4差分映射法表5.1為經(jīng)差分映射處理前后的各柵格屬性記錄所需字節(jié)數(shù)的對(duì)比，可見，所需字節(jié)數(shù)由原來的79減少為44，減少44.3%。372.4差分映射法表5.1為經(jīng)差分映射處理前后的各柵格屬性382.5四叉樹編碼

四叉樹又稱四元樹或四分樹，是最有效的柵格數(shù)據(jù)壓縮編碼方法之一。四分樹將整個(gè)圖像區(qū)域逐步分解為一系列方形區(qū)域，且每一個(gè)方形區(qū)域具有單一的屬性。最小區(qū)域?yàn)橐粋€(gè)像元。382.5四叉樹編碼四叉樹又稱四元樹或四分樹，是最有效的393拓?fù)潢P(guān)系的生成

拓?fù)淇臻g關(guān)系是一種對(duì)空間結(jié)構(gòu)進(jìn)行明確定義的數(shù)學(xué)方法，具有拓?fù)潢P(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)就是拓?fù)鋽?shù)據(jù)結(jié)構(gòu)。它描述了基本空間目標(biāo)點(diǎn)、線、面之間的關(guān)聯(lián)、鄰接和包含關(guān)系。矢量數(shù)據(jù)拓?fù)潢P(guān)系在空間數(shù)據(jù)的查詢和分析過程中非常重要，拓?fù)鋽?shù)據(jù)結(jié)構(gòu)是地理信息系統(tǒng)分析和應(yīng)用功能所必需的。拓?fù)淇臻g關(guān)系信息是空間分析、輔助決策等的基礎(chǔ)，也是GIS區(qū)別于CAD(計(jì)算機(jī)輔助設(shè)計(jì))等的主要標(biāo)志。對(duì)于拓?fù)潢P(guān)系的自動(dòng)建立問題，研究的焦點(diǎn)是如何提高算法與過程的效率和自動(dòng)化程度，本節(jié)將講述其實(shí)現(xiàn)的基本步驟和要點(diǎn)。393拓?fù)潢P(guān)系的生成拓?fù)淇臻g關(guān)系是一種對(duì)空間結(jié)構(gòu)進(jìn)行明確403拓?fù)潢P(guān)系的生成拓?fù)潢P(guān)系自動(dòng)生成算法的一般過程為：（1）弧段處理：使整幅圖形中的所有弧段，除在端點(diǎn)處相交外，沒有其他交點(diǎn)，即沒有相交或自相交的弧段。（2）結(jié)點(diǎn)匹配：建立結(jié)點(diǎn)、弧段關(guān)系。（3）建立多邊形：以左轉(zhuǎn)算法或右轉(zhuǎn)算法跟蹤，生成多邊形，建立多邊形與弧段的拓?fù)潢P(guān)系。（4）建立多邊形與多邊形的拓?fù)潢P(guān)系：調(diào)整弧段的左右多邊形標(biāo)識(shí)號(hào)。多邊形內(nèi)部標(biāo)識(shí)號(hào)的自動(dòng)生成。403拓?fù)潢P(guān)系的生成拓?fù)潢P(guān)系自動(dòng)生成算法的一般過程為：413拓?fù)潢P(guān)系的生成3.1基本數(shù)據(jù)結(jié)構(gòu)3.2弧段的預(yù)處理3.3結(jié)點(diǎn)匹配算法3.4建立拓?fù)潢P(guān)系

413拓?fù)潢P(guān)系的生成3.1基本數(shù)據(jù)結(jié)構(gòu)423.1基本數(shù)據(jù)結(jié)構(gòu)（1）拓?fù)浣Y(jié)點(diǎn)（2）拓?fù)浠《渭捌浔硎荆?）拓?fù)涿婕捌浔硎荆?）拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系423.1基本數(shù)據(jù)結(jié)構(gòu)（1）拓?fù)浣Y(jié)點(diǎn)433.1基本數(shù)據(jù)結(jié)構(gòu)（1）拓?fù)浣Y(jié)點(diǎn)結(jié)點(diǎn)用來描述如管線的交點(diǎn)、道路路口等現(xiàn)實(shí)世界的特征對(duì)象，結(jié)點(diǎn)可以用來檢測(cè)弧段與弧段的連接關(guān)系和多邊形特征是否能正確地完成。只與一條弧段相連接的起點(diǎn)或終點(diǎn)叫做懸掛結(jié)點(diǎn)，如圖5.18所示的P點(diǎn)就是懸掛結(jié)點(diǎn)。結(jié)點(diǎn)一般包括結(jié)點(diǎn)號(hào)、結(jié)點(diǎn)坐標(biāo)、與該結(jié)點(diǎn)連接的弧段集合。433.1基本數(shù)據(jù)結(jié)構(gòu)（1）拓?fù)浣Y(jié)點(diǎn)443.1基本數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可以表示為：443.1基本數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可以表示為：453.1基本數(shù)據(jù)結(jié)構(gòu)（2）拓?fù)浠《渭捌浔硎?/p>

拓?fù)浠《沃柑幱趦蓚€(gè)結(jié)點(diǎn)之間的點(diǎn)序列串，可以給弧段定義一個(gè)方向，或者定義為數(shù)字化弧段時(shí)從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的采點(diǎn)方向，或者硬性定義一個(gè)方向。定義方向后弧段開始的結(jié)點(diǎn)就稱為起始結(jié)點(diǎn)，弧段結(jié)束的結(jié)點(diǎn)就稱為結(jié)束結(jié)點(diǎn)，由起始結(jié)點(diǎn)到終止結(jié)點(diǎn)的方向稱為“起終方向”，由終止結(jié)點(diǎn)到起始結(jié)點(diǎn)的方向稱為“終起方向”?；《纹鸾K方向左側(cè)的多邊形稱為弧段的左多邊形，弧段起終方向右側(cè)的多邊形稱為弧段的右多邊形。453.1基本數(shù)據(jù)結(jié)構(gòu)（2）拓?fù)浠《渭捌浔硎?63.1基本數(shù)據(jù)結(jié)構(gòu)如果弧段的起始結(jié)點(diǎn)或終止結(jié)點(diǎn)只與一條弧段相關(guān)聯(lián)，則該弧段稱為懸掛弧段，如圖5.19所示的弧段L為懸掛弧。一般可以通過標(biāo)識(shí)懸掛弧段來檢測(cè)原始矢量數(shù)據(jù)的質(zhì)量。

弧段一般包括弧段號(hào)、弧段節(jié)點(diǎn)坐標(biāo)串、弧段起始和終止結(jié)點(diǎn)、弧段左右多邊形。463.1基本數(shù)據(jù)結(jié)構(gòu)如果弧段的起始結(jié)點(diǎn)或終止結(jié)點(diǎn)只與一條473.1基本數(shù)據(jù)結(jié)構(gòu)473.1基本數(shù)據(jù)結(jié)構(gòu)483.1基本數(shù)據(jù)結(jié)構(gòu)（3）拓?fù)涿婕捌浔硎就負(fù)涿媸怯梢粭l或若干條弧段首尾相連接而成的邊線所包含的區(qū)域，內(nèi)部包含有其他拓?fù)涿娴耐負(fù)涿嬉话惴Q為復(fù)雜面，被包含的拓?fù)涿娣Q為島，沒有島的拓?fù)涿娣Q為簡單面，如圖5.20所示。對(duì)于拓?fù)涿嬉部梢远x正反方向，一般定義為：當(dāng)沿拓?fù)涿娴倪吔缜斑M(jìn)時(shí)，被弧段所包圍的面域始終處于弧段的右側(cè)時(shí)的方向就是正方向；反之，則是反方向。483.1基本數(shù)據(jù)結(jié)構(gòu)（3）拓?fù)涿婕捌浔硎?93.1基本數(shù)據(jù)結(jié)構(gòu)如圖5.21所示，箭頭所指向的方向就是正方向，可以看出對(duì)于拓?fù)涿娴耐膺吔纾槙r(shí)針方向是正方向，而對(duì)于內(nèi)邊界逆時(shí)針方向就是正方向。493.1基本數(shù)據(jù)結(jié)構(gòu)如圖5.21所示，箭頭所指向的方向就503.1基本數(shù)據(jù)結(jié)構(gòu)多邊形一般包括多邊形號(hào)、中心點(diǎn)坐標(biāo)、多邊形屬性數(shù)據(jù)、多邊形的組成弧段號(hào)、多邊形島的信息。考慮到組成弧段的方向和多邊形頂點(diǎn)序列的方向存在可能的不一致性以及效率問題，可以改為記錄組成多邊形的弧段指針和方向性信息，即弧段方向與多邊形的方向是否一致。對(duì)于島的信息則通過將構(gòu)成多邊形的邊線分塊來處理的方式體現(xiàn)，比如多邊形包含島嶼，則可以使多邊形的外邊界成為多邊形的第一部分，島嶼作為多邊形的第二、三、四等部分的方式加以解決。

503.1基本數(shù)據(jù)結(jié)構(gòu)多邊形一般包括多邊形號(hào)、中心點(diǎn)坐標(biāo)、5151523.1基本數(shù)據(jù)結(jié)構(gòu)(4)拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系523.1基本數(shù)據(jù)結(jié)構(gòu)(4)拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系533.2弧段的預(yù)處理

拓?fù)潢P(guān)系自動(dòng)建立的第一步就是處理弧段，使得弧段不存在自相交和相交現(xiàn)象。（1）直線段相交的判斷方法（2）自相交弧段處理（3）弧段相交打斷處理533.2弧段的預(yù)處理拓?fù)潢P(guān)系自動(dòng)建立的第一步就是處理弧段54(1)直線段相交的判斷方法直線相交的判定方法有很多種，這里介紹較快的一種算法。設(shè)直線L過點(diǎn)P0（x0，y0）和點(diǎn)P1（x1，y1），則直線L的方程可以表示為：將方程化為參數(shù)形式：y=y0+(y1-y0)t,x=x0+(x1-x0)t，其中t∈[0,1]。設(shè)有兩條直線L1和L2，它們的參數(shù)方程分別為y=y0+(y1-y0)t，x=x0+(x1-x0)t

和y‘=y0＇+(y1＇-y0＇)ｖ，x＇=x0’+(x1＇-x0＇)ｖ54(1)直線段相交的判斷方法直線相交的判定方法有很多種，這55(1)直線段相交的判斷方法判斷兩線段有無交點(diǎn)的關(guān)鍵變?yōu)榕袛鄑和v；是否符合不等式0≤t≤1且0≤v≤1。令：如果dx

?

dy'-dy

?

dx＇=0，說明兩線段平行或者重合，沒有交點(diǎn)，或者交點(diǎn)在兩線段的頭或尾上；否則如果滿足不等式0≤t≤1且0≤v≤1，兩線段有交點(diǎn)，交點(diǎn)在兩線段的中間。55(1)直線段相交的判斷方法判斷兩線段有無交點(diǎn)的關(guān)鍵變?yōu)榕?6（2）自相交弧段處理具有自相交特征的弧段至少具有4個(gè)(結(jié))節(jié)點(diǎn)，由3個(gè)點(diǎn)或2個(gè)點(diǎn)組成的弧段不可能自相交。依次取出每一條弧段，如果弧段的(結(jié))節(jié)點(diǎn)個(gè)數(shù)不少于4個(gè)，就利用直線段相交的方法，對(duì)組成弧段的各直線段進(jìn)行判斷，如果相交，將線段斷開為兩條，自相交的弧段可能不止有一處相交，可以通過遞歸的方法將弧段分開。56（2）自相交弧段處理具有自相交特征的弧段至少具有4個(gè)(結(jié)5757585859（3）弧段相交打斷處理弧段與弧段相交關(guān)系的判斷，可以通過取每一條弧段與其他未判斷過的所有弧段目標(biāo)進(jìn)行相交關(guān)系判斷而得，從而要進(jìn)行（n-1)+(n-2)+…+3+2+1=n（n–1）/2次判斷。具體方法為：取出第一條弧段，與其他n-1條弧段進(jìn)行相交判斷，求得交點(diǎn)后，將交點(diǎn)分別插入第一條弧段和與其相交弧段的對(duì)應(yīng)位置上，并記錄位置。將第一條弧段與所有其他弧段的相交關(guān)系判斷完畢后，通過記錄下的交點(diǎn)位置將第一條弧段分割，然后依次取出下一條弧段進(jìn)行同樣的處理，直到所有弧段處理完畢。59（3）弧段相交打斷處理弧段與弧段相交關(guān)系的判斷，可以通過60（3）弧段相交打斷處理由于GIS的數(shù)據(jù)量大，造成了判斷的工作量大、效率低下的弊端，在判斷兩條弧段的關(guān)系時(shí)，應(yīng)盡可能地減少計(jì)算量。減少計(jì)算量方法：分兩步，首先是判斷兩條弧段的最小矩形壁包(MBR)是否相交或具有包含關(guān)系，如果不相交或沒有包含關(guān)系，那么可以斷定兩條弧段是互不相交的；如果相交或具有包含關(guān)系，則進(jìn)一步判斷第一條弧段的每一條組成線段是否和第二條弧段的MBR相交或被包含，如果不相交或沒有被包含則可以判斷這一部分線段不會(huì)和第二條弧段相交，否則可以使用這一條線段與組成第二條弧段的各個(gè)線段進(jìn)行相交關(guān)系的判定來確定交點(diǎn)。60（3）弧段相交打斷處理由于GIS的數(shù)據(jù)量大，造成了判斷的613.3結(jié)點(diǎn)匹配算法

結(jié)點(diǎn)匹配就是把一定容差范圍內(nèi)的弧段的結(jié)點(diǎn)合并成為一個(gè)結(jié)點(diǎn)，其坐標(biāo)值可以是取多個(gè)結(jié)點(diǎn)的平均值，或者選中一個(gè)結(jié)點(diǎn)作為所有結(jié)點(diǎn)的坐標(biāo)區(qū)中心的坐標(biāo)。613.3結(jié)點(diǎn)匹配算法結(jié)點(diǎn)匹配就是把一定容差范圍內(nèi)的弧段的623.3結(jié)點(diǎn)匹配算法每條弧段對(duì)應(yīng)著兩個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)在合并前對(duì)應(yīng)著一條弧段，在合并結(jié)點(diǎn)的過程中，需要將結(jié)點(diǎn)對(duì)應(yīng)的弧段也合并在一起。具體的思路是將所有的結(jié)點(diǎn)加入結(jié)點(diǎn)集合，從結(jié)點(diǎn)集合中取出一個(gè)結(jié)點(diǎn)作為中心點(diǎn)，從余下的結(jié)點(diǎn)中找出容差范圍內(nèi)的其他結(jié)點(diǎn)，將這些結(jié)點(diǎn)所對(duì)應(yīng)的弧段加入中心結(jié)點(diǎn)的弧段集合中，同時(shí)將弧段的對(duì)應(yīng)的結(jié)點(diǎn)變?yōu)橹行慕Y(jié)點(diǎn)，并修改弧段的相應(yīng)坐標(biāo)。623.3結(jié)點(diǎn)匹配算法每條弧段對(duì)應(yīng)著兩個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)在合并633.4建立拓?fù)潢P(guān)系

（１）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角,并按由小到大排序（２）左轉(zhuǎn)算法（３）島的判斷633.4建立拓?fù)潢P(guān)系（１）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角,并按64（１）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角每個(gè)結(jié)點(diǎn)都關(guān)聯(lián)有若干條弧段，結(jié)點(diǎn)或者為弧段的頭結(jié)點(diǎn)或者為弧段的尾結(jié)點(diǎn)，設(shè)結(jié)點(diǎn)為N，則弧段的方位角定義為：結(jié)點(diǎn)N與弧段上與其最接近結(jié)點(diǎn)V的連線與Ｘ軸的正向夾角。64（１）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角每個(gè)結(jié)點(diǎn)都關(guān)聯(lián)有若干條弧段65（１）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角設(shè)結(jié)點(diǎn)N的坐標(biāo)為(x0，y0)，節(jié)點(diǎn)v的坐標(biāo)為(x1，y1)，則有：dx=x1-x0，dy=y1-y0，那么有當(dāng)dx=0時(shí):計(jì)算出結(jié)點(diǎn)N所關(guān)聯(lián)的弧段的方位角后，按角的大小將這些弧排序，形成排序的關(guān)聯(lián)弧段集合。65（１）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角設(shè)結(jié)點(diǎn)N的坐標(biāo)為(x0，y66（2）左轉(zhuǎn)算法算法基本思想：從組成多邊形邊界的某一條弧段開始，如果該弧段的方向角最小或介于同一結(jié)點(diǎn)的其他弧段方向角之間，則逆時(shí)針方向?qū)ふ易钚A角偏差所對(duì)應(yīng)的弧段為多邊形的后續(xù)弧段；如果該弧段與X軸正向夾角為最大，則從該弧段的同一結(jié)點(diǎn)出發(fā)的其他弧段中，方向角最小的弧段是該多邊形的后續(xù)弧段。66（2）左轉(zhuǎn)算法算法基本思想：從組成多邊形邊界的某一條弧段67（2）左轉(zhuǎn)算法算法描述如下：（1）順序取一個(gè)結(jié)點(diǎn)作為起始結(jié)點(diǎn)，取完為止；取過該結(jié)點(diǎn)的方位角最小的未使用過的或僅使用過一次，且使用過的方向與本次相反的弧段作為起始弧段。（2）取這條弧段的另一個(gè)結(jié)點(diǎn)，找這個(gè)結(jié)點(diǎn)關(guān)聯(lián)的弧段集合中的本條弧段的下一條弧段，如果條弧段是最后一條弧段，則取弧段集合的第一條弧段，作為下一條弧段。67（2）左轉(zhuǎn)算法算法描述如下：68（2）左轉(zhuǎn)算法（3）判斷是否回到起點(diǎn)，如果是，則形成了一個(gè)多邊形，記錄下它，并且根據(jù)弧段的方向，設(shè)置組成該多邊形的左右多邊形信息；否則轉(zhuǎn)(2)。（4）取起始點(diǎn)上開始的，剛才所形成多邊形的最后一條邊作為新的起始弧段，轉(zhuǎn)(2)；若這條弧段已經(jīng)使用過兩次，即形成了兩個(gè)多邊形，轉(zhuǎn)(1)。在構(gòu)建多邊形時(shí)要注意懸掛結(jié)點(diǎn)和懸掛線的標(biāo)識(shí)，一般可以采用棧的形式處理。68（2）左轉(zhuǎn)算法（3）判斷是否回到起點(diǎn)，如果是，則形成了一69（2）左轉(zhuǎn)算法（1）從N1結(jié)點(diǎn)開始，選擇具有最小方位角的弧段N1N2作為起始弧段；轉(zhuǎn)入N2點(diǎn)，根據(jù)左轉(zhuǎn)算法選擇N2N5弧段，轉(zhuǎn)入N5結(jié)點(diǎn)選擇N5N1弧段，形成多邊形A1，設(shè)置組成多邊形A1的弧段的左右多邊形信息。（2）A1的結(jié)束弧段為N5N1，選N1作為起始點(diǎn)，N1N5作為起始弧段，根據(jù)左轉(zhuǎn)算法，形成多邊形A2，設(shè)置左右多邊形信息。

69（2）左轉(zhuǎn)算法（1）從N1結(jié)點(diǎn)開始，選擇具有最小方位角的70（2）左轉(zhuǎn)算法（3）A2的結(jié)束弧段為N4N1，選N1作為起始點(diǎn)，N1N4作為起始弧段，根據(jù)、左轉(zhuǎn)算法，形成多邊形A3，這個(gè)多邊形的方向是逆時(shí)針方向，對(duì)于逆時(shí)針方向的多邊形，不設(shè)置左右多邊形信息。70（2）左轉(zhuǎn)算法（3）A2的結(jié)束弧段為N4N1，選N1作為71（2）左轉(zhuǎn)算法（4）A3的結(jié)束弧段為N2N1，N1N2已經(jīng)被使用過兩次，所以選取下一個(gè)結(jié)點(diǎn)N2作為起始結(jié)點(diǎn)。從N2結(jié)點(diǎn)開始，具有最小方位角的弧段是N2N1，但N2N1已經(jīng)被使用兩次，不選；繼續(xù)選取下一條弧段N2N5；然而上一次該弧段的訪問方向與本次相同，所以也不選；繼續(xù)選取下一條弧段N2N3作為起始弧段，形成多邊形A4。（5）依照此規(guī)則形成多邊形A5，即完成了圖5.24的拓?fù)錁?gòu)建，共可形成A1、A2、A3、A4、A5五個(gè)多邊形。71（2）左轉(zhuǎn)算法（4）A3的結(jié)束弧段為N2N1，N1N272（3）島的判斷島的判斷是指找出多邊形互相包含的情況，即尋找復(fù)雜多邊形。找到島后才可以完成多邊形的拓?fù)潢P(guān)系的建立。根據(jù)左轉(zhuǎn)算法，由單條弧段或多條弧段順序構(gòu)成的且不與其他多邊形相交的多邊形即單多邊形會(huì)被追蹤兩次，形成兩個(gè)多邊形，一個(gè)多邊形節(jié)點(diǎn)方向是順時(shí)針的，另一個(gè)多邊形的節(jié)點(diǎn)方向是逆時(shí)針的，如果一個(gè)多邊形包含另一個(gè)多邊形，則必然是順時(shí)針多邊形包含逆時(shí)針多邊形。72（3）島的判斷島的判斷是指找出多邊形互相包含的情況，即尋73（3）島的判斷島的判斷決定于多邊形節(jié)點(diǎn)的順序問題，多邊形節(jié)點(diǎn)的順序問題可以通過計(jì)算多邊形的面積加以解決。任意多邊形的面積可以通過積分來解決，設(shè)多邊形的節(jié)點(diǎn)坐標(biāo)串為（x1，y1），（x2，y2），…，（xn，yn)，那么多邊形的面積可以表示為式中，△x=xi+1-xi。所以多邊形的面積可以表示為：當(dāng)多邊形由順時(shí)針方向構(gòu)成時(shí)，面積為正；否則，面積為負(fù)。

73（3）島的判斷島的判斷決定于多邊形節(jié)點(diǎn)的順序問題，多邊形74（3）島的判斷島的判斷問題的算法如下：（1）計(jì)算所有多邊形的面積。（2）分別對(duì)面積為正的多邊形和面積為負(fù)的多邊形排序，分別形成正多邊形和負(fù)多邊形集合。（3）如果負(fù)多邊形集合的個(gè)數(shù)為1，結(jié)束程序;否則，從面積為正的多邊形集合中，順序取出一個(gè)多邊形，如果正多邊形巳經(jīng)都被訪問過，則程序結(jié)束。74（3）島的判斷島的判斷問題的算法如下：75（3）島的判斷（4）依次從負(fù)多邊形集合中取出負(fù)多邊形，判斷當(dāng)前取出的正多邊形是否包含該負(fù)多邊形，如果包含，就將該負(fù)多邊形加入當(dāng)前取出的正多邊形中，形成復(fù)雜多邊形，設(shè)置負(fù)多邊形的組成弧段的拓?fù)湫畔?，并從?fù)多邊形集合中刪除該負(fù)多邊形。當(dāng)所有負(fù)多邊形都被訪問一遍后轉(zhuǎn)(3)。75（3）島的判斷（4）依次從負(fù)多邊形集合中取出負(fù)多邊形，判76（3）島的判斷上述算法中，判斷負(fù)多邊形是否被正多邊形包含是關(guān)鍵，具體的算法為：（1）判斷負(fù)多邊形面積的絕對(duì)值是否小于正多邊形的面積，如果不小于，則負(fù)多邊形必不為正多邊形所包含，結(jié)束程序；否則執(zhí)行下一步。（2）判斷負(fù)多邊形的最小外接矩形是否和正多邊形的最小外接矩形相交或被包含，如果不相交或不被包含，則負(fù)多邊形必不被正多邊形所包含，結(jié)束程序；否則執(zhí)行下一步。（3）依次取負(fù)多邊形上的點(diǎn)，判斷點(diǎn)是否在正多邊形中，如果所有點(diǎn)都在正多邊形中則負(fù)多邊形被正多邊形所包含，否則，負(fù)多邊形不被正多邊形所包含。76（3）島的判斷上述算法中，判斷負(fù)多邊形是否被正多邊形包含77空間數(shù)據(jù)組織算法《地理信息系統(tǒng)算法基礎(chǔ)》第六章1空間數(shù)據(jù)組織算法《地理信息系統(tǒng)算法基礎(chǔ)》第六章78本講內(nèi)容1矢量數(shù)據(jù)的壓縮2柵格數(shù)據(jù)的壓縮3拓?fù)潢P(guān)系的生成

2本講內(nèi)容1矢量數(shù)據(jù)的壓縮791矢量數(shù)據(jù)的壓縮矢量數(shù)據(jù)的壓縮包括兩個(gè)方面的內(nèi)容：一是在不擾亂拓?fù)潢P(guān)系的前提下，對(duì)采樣點(diǎn)數(shù)據(jù)進(jìn)行合理的抽?。欢菍?duì)矢量坐標(biāo)數(shù)據(jù)重新進(jìn)行編碼，以減少所需要的存儲(chǔ)空間。矢量數(shù)據(jù)的壓縮往往是不可逆的，數(shù)據(jù)壓縮后，數(shù)據(jù)量變小了，數(shù)據(jù)的精度降低了。31矢量數(shù)據(jù)的壓縮矢量數(shù)據(jù)的壓縮包括兩個(gè)方面的內(nèi)容：801矢量數(shù)據(jù)的壓縮1.1間隔取點(diǎn)法1.2垂距法和偏角法1.3道格拉斯-普克法1.4光欄法1.5曲線壓縮算法的比較1.6面域的數(shù)據(jù)壓縮算法41矢量數(shù)據(jù)的壓縮1.1間隔取點(diǎn)法811.1間隔取點(diǎn)法原理：每隔K個(gè)點(diǎn)取一點(diǎn)，或舍去那些離已選點(diǎn)比規(guī)定距離更近的點(diǎn)，但首、末點(diǎn)一定要保留，如圖5.1所示。

優(yōu)缺點(diǎn)：可大量壓縮數(shù)字化儀用連續(xù)方法獲取的點(diǎn)列中的點(diǎn)、曲率顯著變化的點(diǎn)，但不一定能恰當(dāng)?shù)乇Ａ舴较蛏锨曙@著變化的點(diǎn)。51.1間隔取點(diǎn)法原理：每隔K個(gè)點(diǎn)取一點(diǎn)，或舍去那些離已選821.2垂距法和偏角法原理：按垂距或偏角的限差，選取符合或超過限差的點(diǎn)。優(yōu)缺點(diǎn)：不能同時(shí)考慮相鄰點(diǎn)間的方向與距離，且有可能舍去不該舍去的點(diǎn)，但較前一種方法有進(jìn)步。61.2垂距法和偏角法原理：按垂距或偏角的限差，選取符合或831.3道格拉斯-普克法

原理：將一條曲線首、末點(diǎn)連一條直線，求出其余各點(diǎn)到該直線的距離，選其最大者與規(guī)定的臨界值相比較，若大于臨界值，則離該直線距離最大的點(diǎn)保留，否則將直線兩端間各點(diǎn)全部舍去。

如圖5.3所示，經(jīng)數(shù)據(jù)采樣得到的曲線MN由點(diǎn)序{P1，P2，P3，…，Pn}組成，n個(gè)點(diǎn)的坐標(biāo)集為(x1,y1),(x2,y2),(x3,y3),…,(xn,yn)。其中P1，Pn代分別對(duì)應(yīng)曲線的起點(diǎn)M和終點(diǎn)N。根據(jù)應(yīng)用需要和數(shù)據(jù)精度要求，給定控制數(shù)據(jù)壓縮的極差為ε，ε表示為被舍棄的點(diǎn)偏離特征點(diǎn)連線之間的垂直距離。71.3道格拉斯-普克法原理：將一條曲線首、末點(diǎn)連一條直841.3道格拉斯-普克法曲線的空間數(shù)據(jù)壓縮過程如下：第一步：確定曲線MN對(duì)應(yīng)弦的直線方程。由起點(diǎn)M、終點(diǎn)N建立直線―方程為將上式化簡為一般形式為：Ax+By+C=0第二步：求曲線MN上各點(diǎn)Pi到弦線MN的距離di。

Pi(xi，yi)到弦線MN的距離為第三步：求距離di的最大值dh第四步：比較dh與ε的大小，并計(jì)算開關(guān)Q：81.3道格拉斯-普克法曲線的空間數(shù)據(jù)壓縮過程如下：851.3道格拉斯-普克法第五步：決定取舍，提取中間特征點(diǎn)。(1)如果Q=0，則直接可以用弦線MN(M、N為特征點(diǎn))代替曲線MN；轉(zhuǎn)第六步。(2)如果Q=1，則將dh所對(duì)應(yīng)的點(diǎn)Pi(Xi，yi)抽出，暫時(shí)作為中間特征點(diǎn)；然后連接新弦線MPj；轉(zhuǎn)第一步(以MPj已代替MN，繼續(xù)計(jì)算和判斷)。若Q=0，則可以用弦線MPj代替曲線MPj；將Pj作為中間特征點(diǎn)取出；順序排在M點(diǎn)之后，成為繼M之后的第一個(gè)中間特征點(diǎn)；并連接PjN，轉(zhuǎn)第一步（以PjN代替MN，繼續(xù)計(jì)算和判斷)……91.3道格拉斯-普克法第五步：決定取舍，提取中間特征點(diǎn)。861.3道格拉斯-普克法

若Q=1，則不可以用弦線MPj代替曲線MPj；找到此時(shí)dh所對(duì)應(yīng)的點(diǎn)Pk，并連接新弦線MPk；轉(zhuǎn)第一步(以MPk代替MN，繼續(xù)計(jì)算和判斷)……

第六步：形成新的數(shù)據(jù)文件。將所有提取出的中間特征點(diǎn)從起點(diǎn)M開始，順序排列至終點(diǎn)N，并寫入新的數(shù)據(jù)文件，即得到化簡后的折線的數(shù)據(jù)文件。101.3道格拉斯-普克法若Q=1，則不可以871.3道格拉斯-普克法如圖5.3所示，曲線MN的特征點(diǎn)提取過程如下：(1)找到曲線MN上dh對(duì)應(yīng)點(diǎn)位為1號(hào)點(diǎn)；經(jīng)判斷可以用弦線M1代替曲線M1，故1號(hào)點(diǎn)是繼似點(diǎn)之后提取出的第一個(gè)特征點(diǎn)；(2)連接弦線1N；經(jīng)判斷，不可以用弦線1N代替曲線1N；找到曲線lN上dh的對(duì)應(yīng)點(diǎn)位為2號(hào)點(diǎn)；故連接1、2號(hào)點(diǎn)之弦線12；經(jīng)判斷，還是不可以用弦線12代替曲線12；找到曲線12上dh的對(duì)應(yīng)點(diǎn)位為3號(hào)點(diǎn)；再連接1、3號(hào)點(diǎn)之弦線13；經(jīng)判斷，可以用弦線13代替曲線13；故3號(hào)點(diǎn)是繼1號(hào)點(diǎn)之后提取出的第二個(gè)特征點(diǎn)；111.3道格拉斯-普克法如圖5.3所示，曲線MN的特征點(diǎn)881.3道格拉斯-普克法(3)連接弦線3N；經(jīng)判斷，不可以用弦線3N代替曲線3N；找到曲線3N上之dh的對(duì)應(yīng)點(diǎn)位仍為2號(hào)點(diǎn)；然后，連接3、2號(hào)點(diǎn)之弦線32；經(jīng)判斷，可以用弦線32代替曲線32；故2號(hào)點(diǎn)是繼1號(hào)點(diǎn)、3號(hào)點(diǎn)之后提取出的第三個(gè)特征點(diǎn)；(4)連接2、N號(hào)點(diǎn)之弦線2N；經(jīng)判斷，可以用弦線2N代替曲線2N；中間特征點(diǎn)提取結(jié)束。至此可知，曲線MN可以用特征點(diǎn)M、1、3、2、N順序連接的折線簡化表示。

121.3道格拉斯-普克法(3)連接弦線3N；經(jīng)判斷，不可891.4光欄法

原理：預(yù)先定義的一個(gè)扇形(“喇叭口”），根據(jù)曲線上各節(jié)點(diǎn)是在扇形外還是在扇形內(nèi)，決定節(jié)點(diǎn)是保留還是舍去。設(shè)有曲線點(diǎn)列{Pi}，i=1，2，…，n，“光欄口徑”為d(由用戶自己定義），則該方法實(shí)施的具體步驟：(1)連接p1和p2，過p2點(diǎn)作一條垂直于p1p2的直線，在該垂線上取兩點(diǎn)a1和a2，使a1p1=a2p2=d/2，此時(shí)a1和a2為“光欄”邊界點(diǎn)，p1與a1、p1與a2的連線為以P1為頂點(diǎn)的扇形的兩條邊，這就定義了一個(gè)扇形(這個(gè)扇形的口朝向曲線的前進(jìn)方向，邊長是任意的）。通過p1并在扇形內(nèi)的所有直線都具有這種性質(zhì)，即p1p2上各點(diǎn)到這些直線的垂距都不大于d/2。131.4光欄法原理：預(yù)先定義的一個(gè)扇形(“喇叭口”），901.4光欄法(2)若p3點(diǎn)在扇形內(nèi)，則舍丟p2點(diǎn)。然后連接p1和p3，過p3作p1p3的垂線，該垂線與前面定義的扇形邊交于c1和c2。在垂線上找到b1和b2點(diǎn)，使p3b1=p3b2=d/2，若b1和b2點(diǎn)落在原扇形外面（圖5.4中為b2點(diǎn)），則用c1或c2取代(圖5.4中由c2取代b2)。此時(shí)用p1b1和p1c2定義一個(gè)新的扇形，這當(dāng)然是口徑(b1c2)縮小了的“光欄”。(3)檢查下一節(jié)點(diǎn)，若該點(diǎn)在新扇形內(nèi)，則重復(fù)第(2)步；直到發(fā)現(xiàn)有一個(gè)節(jié)點(diǎn)在最新定義的扇形外為止。(4)當(dāng)發(fā)現(xiàn)在扇形外的節(jié)點(diǎn)，如圖5.4中的p4，此時(shí)保留點(diǎn)p3，以p3作為新起點(diǎn)，重復(fù)(1)?(2)步。如此繼續(xù)下去，直到整個(gè)點(diǎn)列檢測(cè)完為止。所有被保留的點(diǎn)（含首、末點(diǎn)），順序地構(gòu)成了簡化后的新點(diǎn)列。141.4光欄法(2)若p3點(diǎn)在扇形內(nèi)，則舍丟p2點(diǎn)。然后911.4光欄法151.4光欄法921.5曲線壓縮算法的比較

評(píng)價(jià)依據(jù)：壓縮后的總長度、原曲線及壓縮后曲線的線性位移(矢高和面積)

等。線性位移量評(píng)價(jià)：道格拉斯-普克法具有最小的線性位移；偏角法在所有的壓縮水平上較其他3種方法具有更大的線性位移量，但僅依據(jù)矢高位移量又很難對(duì)間隔取點(diǎn)法的算法作出結(jié)論，而在舍去30%-70%的點(diǎn)時(shí)，無論按矢高位移量還是按面積位移量來評(píng)價(jià)，垂距法顯然較偏角法和間隔取點(diǎn)法好161.5曲線壓縮算法的比較評(píng)價(jià)依據(jù)：壓縮后的總長度、原曲931.5曲線壓縮算法的比較結(jié)論：淘汰的點(diǎn)數(shù)越多，它們的壓縮效果越趨于一致。在一般情況下，道格拉斯-普克方法壓縮效果占優(yōu)，其次是垂距法、間隔取點(diǎn)法和偏角法，但道格拉斯-普克方法需對(duì)整條曲線完成數(shù)字化后方能進(jìn)行壓縮，且計(jì)算工作量較大。光欄法則不僅算法嚴(yán)密，能按給定閾值保留曲線特征點(diǎn)，并能實(shí)時(shí)處理，運(yùn)算量少，占用內(nèi)存少。171.5曲線壓縮算法的比較結(jié)論：淘汰的點(diǎn)數(shù)越多，它們的壓縮941.6面域的數(shù)據(jù)壓縮算法面域空間數(shù)據(jù)的壓縮過程可以看成是組成其邊界的曲線段的分別壓縮，每段邊界曲線的壓縮過程如前所述。

封閉曲線的數(shù)據(jù)壓縮公共節(jié)點(diǎn)的取舍問題181.6面域的數(shù)據(jù)壓縮算法面域空間數(shù)據(jù)的壓縮過程可以看成是951.6面域的數(shù)據(jù)壓縮算法封閉曲線的數(shù)據(jù)壓縮面域由首尾相連的封閉曲線組成。此時(shí)，可以人為地將該封閉線分割為首尾相連的兩段曲線，然后就可以按前述方法進(jìn)行壓縮。曲線分割的原則是：（1）原節(jié)點(diǎn)是分割點(diǎn)之一；（2）離原節(jié)點(diǎn)最遠(yuǎn)的下一節(jié)點(diǎn)是分割點(diǎn)之二。191.6面域的數(shù)據(jù)壓縮算法封閉曲線的數(shù)據(jù)壓縮961.6面域的數(shù)據(jù)壓縮算法如圖5.7所示，多邊形P的邊界曲線由從節(jié)點(diǎn)A出發(fā)的曲線封閉而成；其中曲線上B點(diǎn)離節(jié)點(diǎn)A最遠(yuǎn)。因而，多邊形P的邊界曲線可以分割為AMB和BNA兩段，進(jìn)而對(duì)曲線段AMB和BNA分別進(jìn)行壓縮。201.6面域的數(shù)據(jù)壓縮算法如圖5.7所示，多邊形P的邊界曲971.6面域的數(shù)據(jù)壓縮算法公共節(jié)點(diǎn)的取舍問題在某些特定情況下，面域的邊界曲線由多段首尾相連的曲線連接而成，其壓縮可以分段進(jìn)行。此時(shí)各段曲線的起點(diǎn)和終點(diǎn)必然作為特征點(diǎn)提取出來，因而可能產(chǎn)生數(shù)據(jù)冗余。比如，當(dāng)前后曲線段過渡時(shí)很平緩，曲線段的公共節(jié)點(diǎn)可以不成為特征點(diǎn)，即該點(diǎn)前后的兩段曲線可以直接用該點(diǎn)前后的兩個(gè)特征點(diǎn)的連線來代替。211.6面域的數(shù)據(jù)壓縮算法公共節(jié)點(diǎn)的取舍問題981.6面域的數(shù)據(jù)壓縮算法如圖5.9所示，1、2號(hào)點(diǎn)分別是面域P的邊界曲線AB、BC段的內(nèi)部特征提取點(diǎn)，因而可以用弦1B、B2分別代替曲線1B和B2。而實(shí)際上，整個(gè)曲線1B2仍可以用弦12來代替。221.6面域的數(shù)據(jù)壓縮算法991.6面域的數(shù)據(jù)壓縮算法在處理面域空間數(shù)據(jù)壓縮時(shí)，可以在邊界曲線分段壓縮的基礎(chǔ)上，增加一個(gè)步驟，即對(duì)邊界曲線的端點(diǎn)進(jìn)行可刪性檢驗(yàn)：如果前一曲線最后提取的中間特征點(diǎn)與后一曲線最先提取的中間特征點(diǎn)之間的曲線滿足極差控制條件，則兩條曲線的連接節(jié)點(diǎn)可以刪減；否則，不可刪減。由于各段邊界曲線的數(shù)據(jù)文件要重新生成，所以當(dāng)兩段曲線的公共節(jié)點(diǎn)刪減之后，相當(dāng)于兩條曲線合并為一條曲線。此時(shí)可能會(huì)擾亂拓?fù)潢P(guān)系(如曲線AB或BC為多邊形的公共邊，或AB和BC均為多邊形的公共邊），因此在處理公共節(jié)點(diǎn)的取舍時(shí)要慎重，應(yīng)該對(duì)此加以限制。231.6面域的數(shù)據(jù)壓縮算法在處理面域空間數(shù)據(jù)壓縮時(shí)，可以在1002柵格數(shù)據(jù)的壓縮2.1鏈?zhǔn)骄幋a2.2游程長度編碼2.3塊式編碼2.4差分映射法2.5四叉樹編碼242柵格數(shù)據(jù)的壓縮2.1鏈?zhǔn)骄幋a1012柵格數(shù)據(jù)的壓縮柵格數(shù)據(jù)文件記錄有3個(gè)基本方式：基于像元、基于層和基于面域。共同點(diǎn)：對(duì)像元坐標(biāo)和屬性的記錄。因此基于柵格的空間數(shù)據(jù)壓縮的實(shí)質(zhì)是研究柵格數(shù)據(jù)的編碼，通過編碼盡量減少像元數(shù)量的存儲(chǔ)。分類：柵格數(shù)據(jù)的壓縮分為無損壓縮技術(shù)和有損壓縮技術(shù)。252柵格數(shù)據(jù)的壓縮柵格數(shù)據(jù)文件記錄有3個(gè)基本方式：基于像1022柵格數(shù)據(jù)的壓縮無損壓縮方法利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真，但壓縮率受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，一般為2：1~5:1。有損壓縮方法利用了數(shù)據(jù)在使用中存在某些成分不敏感的特性，允許壓縮過程中損失一定的信息；雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對(duì)數(shù)據(jù)內(nèi)涵的影響較小，卻換來了大得多的壓縮比。262柵格數(shù)據(jù)的壓縮無損壓縮方法利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮1032.1鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a又稱為弗里曼鏈碼（Freeman，1961年）或邊界鏈碼。如圖5.10所示，其中的多邊形邊界可表示為：由某一原點(diǎn)開始并按某些基本方向確定的單位矢量鏈?；痉较蚩啥x為:東=0，東南=1，南=2，西南=3，西=4，西北=5，北=6，東北=7，8個(gè)基本方向。272.1鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a又稱為弗里曼鏈碼（Freeman1042.1鏈?zhǔn)骄幋a如果確定原點(diǎn)為像元（10，1)，則該多邊形邊界按順時(shí)針方向的鏈?zhǔn)骄幋a(圖5.11)為：10，1，7，0，1，0，7，1，7,0，0,2，3，2，2，1，0，7，0，0，0，0，2，4，3，4，4，3，4，4，5，4，5，4，5，4，5，4，6，6。282.1鏈?zhǔn)骄幋a如果確定原點(diǎn)為像元（10，1)，則該多邊1052.1鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a的優(yōu)點(diǎn)：鏈?zhǔn)骄幋a對(duì)多邊形的表示具有很強(qiáng)的數(shù)據(jù)壓縮能力，且具有一定的運(yùn)算功能，如面積和周長計(jì)算等，探測(cè)邊界急彎和凹進(jìn)部分等都比較容易；鏈?zhǔn)骄幋a的缺點(diǎn)是對(duì)疊置運(yùn)算如組合、相交等則很難實(shí)施，對(duì)局部修改將改變整體結(jié)構(gòu)，效率較低，而且由于鏈碼以每個(gè)區(qū)域?yàn)閱挝淮鎯?chǔ)邊界，相鄰區(qū)域的邊界則被重復(fù)存儲(chǔ)而產(chǎn)生冗余。292.1鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a的優(yōu)點(diǎn)：鏈?zhǔn)骄幋a對(duì)多邊形的表示具1062.2游程長度編碼

游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程長度編碼結(jié)構(gòu)是逐行將相鄰?fù)档木W(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。游程長度編碼結(jié)構(gòu)的建立方法是：將柵格矩陣的數(shù)據(jù)序列X1，X2，…，Xn，映射為相應(yīng)的二元組序列(Ai，Pi），i=1，2,…，K，且K≤n。其中，A為屬性值，P為游程，K為游程序號(hào)。302.2游程長度編碼游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程長度編1072.2游程長度編碼游程長度編碼這種數(shù)據(jù)結(jié)構(gòu)特別適用于二值圖像數(shù)據(jù)的表示

游程編碼能否壓縮數(shù)據(jù)量，主要決定于柵格數(shù)據(jù)的性質(zhì)，通?？赏ㄟ^事先測(cè)試，估算圖層的數(shù)據(jù)冗余度Re：Re=1-Q/mn312.2游程長度編碼游程長度編碼這種數(shù)據(jù)結(jié)構(gòu)特別適用于二值1082.2游程長度編碼Q為圖層內(nèi)相鄰屬性值變化次數(shù)的累加和；m為圖層網(wǎng)格的行數(shù)；n為圖層網(wǎng)格的列數(shù)。當(dāng)Re的值大于1/5的情況下，表明柵格數(shù)據(jù)的壓縮可取得明顯的效果。壓縮效果可由壓縮比S=n/K來表征，即壓縮比的值愈大，表示壓縮效果愈顯著。322.2游程長度編碼Q為圖層內(nèi)相鄰屬性值變化次數(shù)的累加和；1092.3塊式編碼

塊式編碼是將游程長度編碼擴(kuò)大到二維的情況，把多邊形范圍劃分成由像元組成的正方形，然后對(duì)各個(gè)正方形進(jìn)行編碼。塊式編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置（行號(hào)，列號(hào))和半徑，再加上記錄單元的代碼組成。根據(jù)這一編碼原則，圖5.15所示多邊形只需17個(gè)單位正方形，9個(gè)4單位的正方形和1個(gè)16單位的正方形就能完整表示，總共要57個(gè)數(shù)據(jù)，其中27對(duì)坐標(biāo)，3個(gè)塊的半徑。332.3塊式編碼塊式編碼是將游程長度編碼擴(kuò)大到二維的情況1102.3塊式編碼塊式編碼的特點(diǎn)：一個(gè)多邊形所能包含的正方形越大，多邊形的邊界越簡單，塊式編碼的效果越好。游程和塊式編碼都對(duì)大的復(fù)雜多邊形效果并不好。塊式編碼在合并、插入、檢查延伸性、計(jì)算面積等操作時(shí)有明顯的優(yōu)越性。342.3塊式編碼塊式編碼的特點(diǎn)：一個(gè)多邊形所能包含的正方形1112.4差分映射法

差分映射法，就是選擇某一參照值對(duì)有關(guān)柵格的屬性值進(jìn)行求差運(yùn)算，根據(jù)差值得到一個(gè)新的柵格數(shù)據(jù)層。參照值的選擇有多種方式，即分行選取和全區(qū)選取。若分行選取，則可選為該行首列的屬性值，也可以選為該行的屬性平均值；若全區(qū)選取，則可選為首行首列的屬性值，也可以選為全區(qū)的屬性平均值。352.4差分映射法差分映射法，就是選擇某一參照值對(duì)有關(guān)柵1122.4差分映射法圖5.16為柵格數(shù)據(jù)示例。圖5.17所示為按分行選取方式，以行首屬性值為參照，對(duì)圖5.16作差分映射后的結(jié)果?？梢钥闯觯?jīng)差分映射處理后，除第一列外，其余柵格的數(shù)據(jù)出現(xiàn)為零、位數(shù)降低或數(shù)字減少。362.4差分映射法圖5.16為柵格數(shù)據(jù)示例。圖5.17所示1132.4差分映射法表5.1為經(jīng)差分映射處理前后的各柵格屬性記錄所需字節(jié)數(shù)的對(duì)比，可見，所需字節(jié)數(shù)由原來的79減少為44，減少44.3%。372.4差分映射法表5.1為經(jīng)差分映射處理前后的各柵格屬性1142.5四叉樹編碼

四叉樹又稱四元樹或四分樹，是最有效的柵格數(shù)據(jù)壓縮編碼方法之一。四分樹將整個(gè)圖像區(qū)域逐步分解為一系列方形區(qū)域，且每一個(gè)方形區(qū)域具有單一的屬性。最小區(qū)域?yàn)橐粋€(gè)像元。382.5四叉樹編碼四叉樹又稱四元樹或四分樹，是最有效的1153拓?fù)潢P(guān)系的生成

拓?fù)淇臻g關(guān)系是一種對(duì)空間結(jié)構(gòu)進(jìn)行明確定義的數(shù)學(xué)方法，具有拓?fù)潢P(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)就是拓?fù)鋽?shù)據(jù)結(jié)構(gòu)。它描述了基本空間目標(biāo)點(diǎn)、線、面之間的關(guān)聯(lián)、鄰接和包含關(guān)系。矢量數(shù)據(jù)拓?fù)潢P(guān)系在空間數(shù)據(jù)的查詢和分析過程中非常重要，拓?fù)鋽?shù)據(jù)結(jié)構(gòu)是地理信息系統(tǒng)分析和應(yīng)用功能所必需的。拓?fù)淇臻g關(guān)系信息是空間分析、輔助決策等的基礎(chǔ)，也是GIS區(qū)別于CAD(計(jì)算機(jī)輔助設(shè)計(jì))等的主要標(biāo)志。對(duì)于拓?fù)潢P(guān)系的自動(dòng)建立問題，研究的焦點(diǎn)是如何提高算法與過程的效率和自動(dòng)化程度，本節(jié)將講述其實(shí)現(xiàn)的基本步驟和要點(diǎn)。393拓?fù)潢P(guān)系的生成拓?fù)淇臻g關(guān)系是一種對(duì)空間結(jié)構(gòu)進(jìn)行明確1163拓?fù)潢P(guān)系的生成拓?fù)潢P(guān)系自動(dòng)生成算法的一般過程為：（1）弧段處理：使整幅圖形中的所有弧段，除在端點(diǎn)處相交外，沒有其他交點(diǎn)，即沒有相交或自相交的弧段。（2）結(jié)點(diǎn)匹配：建立結(jié)點(diǎn)、弧段關(guān)系。（3）建立多邊形：以左轉(zhuǎn)算法或右轉(zhuǎn)算法跟蹤，生成多邊形，建立多邊形與弧段的拓?fù)潢P(guān)系。（4）建立多邊形與多邊形的拓?fù)潢P(guān)系：調(diào)整弧段的左右多邊形標(biāo)識(shí)號(hào)。多邊形內(nèi)部標(biāo)識(shí)號(hào)的自動(dòng)生成。403拓?fù)潢P(guān)系的生成拓?fù)潢P(guān)系自動(dòng)生成算法的一般過程為：1173拓?fù)潢P(guān)系的生成3.1基本數(shù)據(jù)結(jié)構(gòu)3.2弧段的預(yù)處理3.3結(jié)點(diǎn)匹配算法3.4建立拓?fù)潢P(guān)系

413拓?fù)潢P(guān)系的生成3.1基本數(shù)據(jù)結(jié)構(gòu)1183.1基本數(shù)據(jù)結(jié)構(gòu)（1）拓?fù)浣Y(jié)點(diǎn)（2）拓?fù)浠《渭捌浔硎荆?）拓?fù)涿婕捌浔硎荆?）拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系423.1基本數(shù)據(jù)結(jié)構(gòu)（1）拓?fù)浣Y(jié)點(diǎn)1193.1基本數(shù)據(jù)結(jié)構(gòu)（1）拓?fù)浣Y(jié)點(diǎn)結(jié)點(diǎn)用來描述如管線的交點(diǎn)、道路路口等現(xiàn)實(shí)世界的特征對(duì)象，結(jié)點(diǎn)可以用來檢測(cè)弧段與弧段的連接關(guān)系和多邊形特征是否能正確地完成。只與一條弧段相連接的起點(diǎn)或終點(diǎn)叫做懸掛結(jié)點(diǎn)，如圖5.18所示的P點(diǎn)就是懸掛結(jié)點(diǎn)。結(jié)點(diǎn)一般包括結(jié)點(diǎn)號(hào)、結(jié)點(diǎn)坐標(biāo)、與該結(jié)點(diǎn)連接的弧段集合。433.1基本數(shù)據(jù)結(jié)構(gòu)（1）拓?fù)浣Y(jié)點(diǎn)1203.1基本數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可以表示為：443.1基本數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可以表示為：1213.1基本數(shù)據(jù)結(jié)構(gòu)（2）拓?fù)浠《渭捌浔硎?/p>

拓?fù)浠《沃柑幱趦蓚€(gè)結(jié)點(diǎn)之間的點(diǎn)序列串，可以給弧段定義一個(gè)方向，或者定義為數(shù)字化弧段時(shí)從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的采點(diǎn)方向，或者硬性定義一個(gè)方向。定義方向后弧段開始的結(jié)點(diǎn)就稱為起始結(jié)點(diǎn)，弧段結(jié)束的結(jié)點(diǎn)就稱為結(jié)束結(jié)點(diǎn)，由起始結(jié)點(diǎn)到終止結(jié)點(diǎn)的方向稱為“起終方向”，由終止結(jié)點(diǎn)到起始結(jié)點(diǎn)的方向稱為“終起方向”?；《纹鸾K方向左側(cè)的多邊形稱為弧段的左多邊形，弧段起終方向右側(cè)的多邊形稱為弧段的右多邊形。453.1基本數(shù)據(jù)結(jié)構(gòu)（2）拓?fù)浠《渭捌浔硎?223.1基本數(shù)據(jù)結(jié)構(gòu)如果弧段的起始結(jié)點(diǎn)或終止結(jié)點(diǎn)只與一條弧段相關(guān)聯(lián)，則該弧段稱為懸掛弧段，如圖5.19所示的弧段L為懸掛弧。一般可以通過標(biāo)識(shí)懸掛弧段來檢測(cè)原始矢量數(shù)據(jù)的質(zhì)量。

弧段一般包括弧段號(hào)、弧段節(jié)點(diǎn)坐標(biāo)串、弧段起始和終止結(jié)點(diǎn)、弧段左右多邊形。463.1基本數(shù)據(jù)結(jié)構(gòu)如果弧段的起始結(jié)點(diǎn)或終止結(jié)點(diǎn)只與一條1233.1基本數(shù)據(jù)結(jié)構(gòu)473.1基本數(shù)據(jù)結(jié)構(gòu)1243.1基本數(shù)據(jù)結(jié)構(gòu)（3）拓?fù)涿婕捌浔硎就負(fù)涿媸怯梢粭l或若干條弧段首尾相連接而成的邊線所包含的區(qū)域，內(nèi)部包含有其他拓?fù)涿娴耐負(fù)涿嬉话惴Q為復(fù)雜面，被包含的拓?fù)涿娣Q為島，沒有島的拓?fù)涿娣Q為簡單面，如圖5.20所示。對(duì)于拓?fù)涿嬉部梢远x正反方向，一般定義為：當(dāng)沿拓?fù)涿娴倪吔缜斑M(jìn)時(shí)，被弧段所包圍的面域始終處于弧段的右側(cè)時(shí)的方向就是正方向；反之，則是反方向。483.1基本數(shù)據(jù)結(jié)構(gòu)（3）拓?fù)涿婕捌浔硎?253.1基本數(shù)據(jù)結(jié)構(gòu)如圖5.21所示，箭頭所指向的方向就是正方向，可以看出對(duì)于拓?fù)涿娴耐膺吔?，順時(shí)針方向是正方向，而對(duì)于內(nèi)邊界逆時(shí)針方向就是正方向。493.1基本數(shù)據(jù)結(jié)構(gòu)如圖5.21所示，箭頭所指向的方向就1263.1基本數(shù)據(jù)結(jié)構(gòu)多邊形一般包括多邊形號(hào)、中心點(diǎn)坐標(biāo)、多邊形屬性數(shù)據(jù)、多邊形的組成弧段號(hào)、多邊形島的信息?？紤]到組成弧段的方向和多邊形頂點(diǎn)序列的方向存在可能的不一致性以及效率問題，可以改為記錄組成多邊形的弧段指針和方向性信息，即弧段方向與多邊形的方向是否一致。對(duì)于島的信息則通過將構(gòu)成多邊形的邊線分塊來處理的方式體現(xiàn)，比如多邊形包含島嶼，則可以使多邊形的外邊界成為多邊形的第一部分，島嶼作為多邊形的第二、三、四等部分的方式加以解決。

503.1基本數(shù)據(jù)結(jié)構(gòu)多邊形一般包括多邊形號(hào)、中心點(diǎn)坐標(biāo)、127511283.1基本數(shù)據(jù)結(jié)構(gòu)(4)拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系523.1基本數(shù)據(jù)結(jié)構(gòu)(4)拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系1293.2弧段的預(yù)處理

拓?fù)潢P(guān)系自動(dòng)建立的第一步就是處理弧段，使得弧段不存在自相交和相交現(xiàn)象。（1）直線段相交的判斷方法（2）自相交弧段處理（3）弧段相交打斷處理533.2弧段的預(yù)處理拓?fù)潢P(guān)系自動(dòng)建立的第一步就是處理弧段130(1)直線段相交的判斷方法直線相交的判定方法有很多種，這里介紹較快的一種算法。設(shè)直線L過點(diǎn)P0（x0，y0）和點(diǎn)P1（x1，y1），則直線L的方程可以表示為：將方程化為參數(shù)形式：y=y0+(y1-y0)t,x=x0+(x1-x0)t，其中t∈[0,1]。設(shè)有兩條直線L1和L2，它們的參數(shù)方程分別為y=y0+(y1-y0)t，x=x0+(x1-x0)t

和y‘=y0＇+(y1＇-y0＇)ｖ，x＇=x0’+(x1＇-x0＇)ｖ54(1)直線段相交的判斷方法直線相交的判定方法有很多種，這131(1)直線段相交的判斷方法判斷兩線段有無交點(diǎn)的關(guān)鍵變?yōu)榕袛鄑和v；是否符合不等式0≤t≤1且0≤v≤1。令：如果dx

?

dy'-dy

?

dx＇=0，說明兩線段平行或者重合，沒有交點(diǎn)，或者交點(diǎn)在兩線段的頭或尾上；否則如果滿足不等式0≤t≤1且0≤v≤1，兩線段有交點(diǎn)，交點(diǎn)在兩線段的中間。55(1)直線段相交的判斷方法判斷兩線段有無交點(diǎn)的關(guān)鍵變?yōu)榕?32（2）自相交弧段處理具有自相交特征的弧段至少具有4個(gè)(結(jié))節(jié)點(diǎn)，由3個(gè)點(diǎn)或2個(gè)點(diǎn)組成的弧段不可能自相交。依次取出每一條弧段，如果弧段的(結(jié))節(jié)點(diǎn)個(gè)數(shù)不少于4個(gè)，就利用直線段相交的方法，對(duì)組成弧段的各直線段進(jìn)行判斷，如果相交，將線段斷開為兩條，自相交的弧段可能不止有一處相交，可以通過遞歸的方法將弧段分開。56（2）自相交弧段處理具有自相交特征的弧段至少具有4個(gè)(結(jié)1335713458135（3）弧段相交打斷處理弧段與弧段相交關(guān)系的判斷，可以通過取每一條弧段與其他未判斷過的所有弧段目標(biāo)進(jìn)行相交關(guān)系判斷而得，從而要進(jìn)行（n-1)+(n-2)+…+3+2+1=n（n–1）/2次判斷。具體方法為：取出第一條弧段，與其他n-1條弧段進(jìn)行相交判斷，求得交點(diǎn)后，將交點(diǎn)分別插入第一條弧段和與其相交弧段的對(duì)應(yīng)位置上，并記錄位置。將第一條弧段與所有其他弧段的相交關(guān)系判斷完畢后，通過記錄下的交點(diǎn)位置將第一條弧段分割，然后依次取出下一條弧段進(jìn)行同樣的處理，直到所有弧段處理完畢。59（3）弧段相交打斷處理弧段與弧段相交關(guān)系的判斷，可以通過136（3）弧段相交打斷處理由于GIS的數(shù)據(jù)量大，造成了判斷的工作量大、效率低下的弊端，在判斷兩條弧段的關(guān)系時(shí)，應(yīng)盡可能地減少計(jì)算量。減少計(jì)算量方法：分兩步，首先是判斷兩條弧段的最小矩形壁包(MBR)是否相交或具有包含關(guān)系，如果不相交或沒有包含關(guān)系，那么可以斷定兩條弧段是互不相交的；如果相交或具有包含關(guān)系，則進(jìn)一步判斷第一條弧段的每一條組成線段是否和第二條弧段的MBR相交或被包含，如果不相交或沒有被包含則可以判斷這一部分線段不會(huì)和第二條弧段相交，否則可以使用這一條線段與組成第二條弧段的各個(gè)線段進(jìn)行相交關(guān)系的判定來確定交點(diǎn)。60（3）弧段相交打斷處理由于GIS的數(shù)據(jù)量大，造成了判斷的1373.3結(jié)點(diǎn)匹配算法

結(jié)點(diǎn)匹配就是把一定容差范圍內(nèi)的弧段的結(jié)點(diǎn)合并成為一個(gè)結(jié)點(diǎn)，其坐標(biāo)值可以是取多個(gè)結(jié)點(diǎn)的平均值，或者選中一個(gè)結(jié)點(diǎn)作為所有結(jié)點(diǎn)的坐標(biāo)區(qū)中心的坐標(biāo)。613.3結(jié)點(diǎn)匹配算法結(jié)點(diǎn)匹配就是把一定容差范圍內(nèi)的弧段的1383.3結(jié)點(diǎn)匹配算法每條弧段對(duì)應(yīng)著兩個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)在合并前對(duì)應(yīng)著一條弧段，在合并結(jié)點(diǎn)的過程中，需要將結(jié)點(diǎn)對(duì)應(yīng)的弧段也合并在一起。具體的思路是將所有的結(jié)點(diǎn)加入結(jié)點(diǎn)集合，從結(jié)點(diǎn)集合中取出一個(gè)結(jié)點(diǎn)作為中心點(diǎn)，從余下的結(jié)點(diǎn)中找出容差范圍內(nèi)的其他結(jié)點(diǎn)，將這些結(jié)點(diǎn)所對(duì)應(yīng)的弧段加入中心結(jié)點(diǎn)的弧段集合中，同時(shí)將弧段的對(duì)應(yīng)的結(jié)點(diǎn)變?yōu)橹行慕Y(jié)點(diǎn)，并修改弧段的相應(yīng)坐標(biāo)。623.3結(jié)點(diǎn)匹配算法每條弧段對(duì)應(yīng)著兩個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)在合