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

1、1空間數(shù)據(jù)組織算法 地理信息系統(tǒng)算法基礎(chǔ)第六章2本講內(nèi)容v1 矢量數(shù)據(jù)的壓縮v2 柵格數(shù)據(jù)的壓縮v3 拓?fù)潢P(guān)系的生成 31 矢量數(shù)據(jù)的壓縮v矢量數(shù)據(jù)的壓縮包括兩個(gè)方面的內(nèi)容：矢量數(shù)據(jù)的壓縮包括兩個(gè)方面的內(nèi)容：v一是在不擾亂拓?fù)潢P(guān)系的前提下，對(duì)采樣點(diǎn)數(shù)據(jù)進(jìn)行合理的一是在不擾亂拓?fù)潢P(guān)系的前提下，對(duì)采樣點(diǎn)數(shù)據(jù)進(jìn)行合理的抽?。怀橄。籿二是對(duì)矢量坐標(biāo)數(shù)據(jù)重新進(jìn)行編碼，以減少所需要的存儲(chǔ)空二是對(duì)矢量坐標(biāo)數(shù)據(jù)重新進(jìn)行編碼，以減少所需要的存儲(chǔ)空間。間。v矢量數(shù)據(jù)的壓縮往往是矢量數(shù)據(jù)的壓縮往往是不可逆不可逆的，數(shù)據(jù)壓縮后，數(shù)據(jù)量變小的，數(shù)據(jù)壓縮后，數(shù)據(jù)量變小了，數(shù)據(jù)的精度降低了。了，數(shù)據(jù)的精度降低了。41 矢量

2、數(shù)據(jù)的壓縮v1.1 1.1 間隔取點(diǎn)法間隔取點(diǎn)法v1.2 1.2 垂距法和偏角法垂距法和偏角法v1.3 1.3 道格拉斯道格拉斯- -普克法普克法v1.4 1.4 光欄法光欄法v1.5 1.5 曲線壓縮算法的比較曲線壓縮算法的比較v1.6 1.6 面域的數(shù)據(jù)壓縮算法面域的數(shù)據(jù)壓縮算法51.1 間隔取點(diǎn)法原理原理：每隔每隔K K個(gè)點(diǎn)取一點(diǎn)，或舍個(gè)點(diǎn)取一點(diǎn)，或舍去那些離已選點(diǎn)比規(guī)定距離更去那些離已選點(diǎn)比規(guī)定距離更近的點(diǎn)，但首、末點(diǎn)一定要保近的點(diǎn)，但首、末點(diǎn)一定要保留，如圖留，如圖5.15.1所示。所示。 優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)：可大量壓縮數(shù)字化儀可大量壓縮數(shù)字化儀用連續(xù)方法獲取的點(diǎn)列中的點(diǎn)、用連續(xù)方法獲取的

3、點(diǎn)列中的點(diǎn)、曲率顯著變化的點(diǎn)，但不一定曲率顯著變化的點(diǎn)，但不一定能恰當(dāng)?shù)乇Ａ舴较蛏锨曙@著能恰當(dāng)?shù)乇Ａ舴较蛏锨曙@著變化的點(diǎn)。變化的點(diǎn)。61.2 垂距法和偏角法原理原理：按垂距或偏角按垂距或偏角的限差，選取符合或的限差，選取符合或超過限差的點(diǎn)。超過限差的點(diǎn)。優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)：不能同時(shí)考不能同時(shí)考慮相鄰點(diǎn)間的方向與慮相鄰點(diǎn)間的方向與距離，且有可能舍去距離，且有可能舍去不該舍去的點(diǎn)，但較不該舍去的點(diǎn)，但較前一種方法有進(jìn)步。前一種方法有進(jìn)步。71.3 道格拉斯-普克法 v原理原理：將一條曲線首、末點(diǎn)連一條直線，求出其余各點(diǎn)到該將一條曲線首、末點(diǎn)連一條直線，求出其余各點(diǎn)到該直線的距離，選其最大者與規(guī)定的臨

4、界值相比較，若大于臨直線的距離，選其最大者與規(guī)定的臨界值相比較，若大于臨界值，則離該直線距離最大的點(diǎn)保留，否則將直線兩端間各界值，則離該直線距離最大的點(diǎn)保留，否則將直線兩端間各點(diǎn)全部舍去。點(diǎn)全部舍去。 如圖如圖5.35.3所示，經(jīng)數(shù)據(jù)采樣得所示，經(jīng)數(shù)據(jù)采樣得到的曲線到的曲線MNMN由點(diǎn)序由點(diǎn)序P1，P2，P3，Pn組成，組成，n n個(gè)點(diǎn)的坐標(biāo)個(gè)點(diǎn)的坐標(biāo)集集為(x1,y1), (x2,y2), (x3,y3),(xn,yn)。其中其中P1，Pn代分別對(duì)應(yīng)曲線的起代分別對(duì)應(yīng)曲線的起點(diǎn)點(diǎn)M和終點(diǎn)和終點(diǎn)N。根據(jù)應(yīng)用需要和數(shù)據(jù)精度要求，給定控制數(shù)據(jù)壓縮的極差為根據(jù)應(yīng)用需要和數(shù)據(jù)精度要求，給定控制數(shù)據(jù)壓縮

5、的極差為，表示為被舍棄的點(diǎn)偏離特征點(diǎn)連線之間的垂直距離。表示為被舍棄的點(diǎn)偏離特征點(diǎn)連線之間的垂直距離。 81.3 道格拉斯-普克法曲線的空間數(shù)據(jù)壓縮過程如下：曲線的空間數(shù)據(jù)壓縮過程如下：第一步第一步：確定：確定曲線MNMN對(duì)應(yīng)弦的直線方程。對(duì)應(yīng)弦的直線方程。 由起點(diǎn)由起點(diǎn)M M、終點(diǎn)、終點(diǎn)N N建立直線建立直線方程為方程為將上式化簡為一般形式為將上式化簡為一般形式為：Ax+By+C=0第二步第二步：求曲線求曲線MN上各點(diǎn)上各點(diǎn)Pi到弦線到弦線MN的距離的距離di。 Pi(xi，yi)到弦線到弦線MN的距離為的距離為第三步第三步：求距離求距離di的最大值的最大值dh第四步第四步：比較比較dh與與

6、的大小，并計(jì)算開關(guān)的大小，并計(jì)算開關(guān)Q：NMMMMNyyyyxxxx|iiidAxByC123max(,)hndd ddd1 0 hhdQd91.3 道格拉斯-普克法第五步第五步：決定取舍，提取中間特征點(diǎn)。：決定取舍，提取中間特征點(diǎn)。(1)如果如果Q=0，則直接可以用弦線，則直接可以用弦線MN(M、N為特征點(diǎn)為特征點(diǎn))代替曲線代替曲線MN；轉(zhuǎn)第六步。；轉(zhuǎn)第六步。(2)如果如果Q = 1，則將，則將dh所對(duì)應(yīng)的點(diǎn)所對(duì)應(yīng)的點(diǎn)Pi(Xi，yi )抽出，暫時(shí)作為中抽出，暫時(shí)作為中間特征點(diǎn)；然后連接新弦線間特征點(diǎn)；然后連接新弦線MPj；轉(zhuǎn)第一步；轉(zhuǎn)第一步(以以MPj已代替已代替MN，繼續(xù)計(jì)算和判斷，繼續(xù)

7、計(jì)算和判斷)。 若若Q = 0，則可以用弦線，則可以用弦線MPj代替曲線代替曲線MPj；將；將Pj作為中間特作為中間特征點(diǎn)取出；順序排在征點(diǎn)取出；順序排在M點(diǎn)之后，成為繼點(diǎn)之后，成為繼M之后的第一個(gè)中間之后的第一個(gè)中間特征點(diǎn)；并連接特征點(diǎn)；并連接PjN，轉(zhuǎn)第一步（以，轉(zhuǎn)第一步（以PjN代替代替MN，繼續(xù)計(jì)算，繼續(xù)計(jì)算和判斷和判斷)101.3 道格拉斯-普克法 若若Q = 1，則不可以用弦線，則不可以用弦線MPj代替曲線代替曲線MPj；找到此時(shí)；找到此時(shí)dh所所對(duì)應(yīng)的點(diǎn)對(duì)應(yīng)的點(diǎn)Pk， 并連接新弦線并連接新弦線MPk；轉(zhuǎn)第一步；轉(zhuǎn)第一步(以以MPk代替代替MN，繼續(xù)計(jì)算和判斷繼續(xù)計(jì)算和判斷) 第六

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

9、接弦線1N；經(jīng)判斷，不可以用弦線；經(jīng)判斷，不可以用弦線1N代替曲線代替曲線1N；找到；找到曲線曲線lN上上dh的對(duì)應(yīng)點(diǎn)位為的對(duì)應(yīng)點(diǎn)位為2號(hào)點(diǎn)；故連接號(hào)點(diǎn)；故連接1、2號(hào)點(diǎn)之弦線號(hào)點(diǎn)之弦線12；經(jīng)判斷，還是不可以用弦線經(jīng)判斷，還是不可以用弦線 12代替曲線代替曲線12；找到曲線；找到曲線12上上dh的對(duì)應(yīng)點(diǎn)位為的對(duì)應(yīng)點(diǎn)位為3號(hào)點(diǎn)；再連接號(hào)點(diǎn)；再連接1、3號(hào)點(diǎn)之弦線號(hào)點(diǎn)之弦線13；經(jīng)判斷，；經(jīng)判斷，可以用弦線可以用弦線13代替曲線代替曲線13；故；故3號(hào)點(diǎn)是繼號(hào)點(diǎn)是繼1號(hào)點(diǎn)之后提取出號(hào)點(diǎn)之后提取出的第二個(gè)特征點(diǎn)；的第二個(gè)特征點(diǎn)；121.3 道格拉斯-普克法(3)連接弦線連接弦線3N；經(jīng)判斷，不可以

10、用弦線；經(jīng)判斷，不可以用弦線3N代替曲線代替曲線3N；找到；找到曲線曲線3N上之上之dh的對(duì)應(yīng)點(diǎn)位仍為的對(duì)應(yīng)點(diǎn)位仍為2號(hào)點(diǎn)；然后，連接號(hào)點(diǎn)；然后，連接3、2號(hào)點(diǎn)號(hào)點(diǎn)之弦線之弦線32；經(jīng)判斷，可以用弦線；經(jīng)判斷，可以用弦線32代替曲線代替曲線32；故；故2號(hào)點(diǎn)是號(hào)點(diǎn)是繼繼1號(hào)點(diǎn)、號(hào)點(diǎn)、3號(hào)點(diǎn)之后提取出的第三個(gè)特征點(diǎn)；號(hào)點(diǎn)之后提取出的第三個(gè)特征點(diǎn)；(4)連接連接2、N號(hào)點(diǎn)之弦線號(hào)點(diǎn)之弦線2N；經(jīng)判斷，可以用弦線；經(jīng)判斷，可以用弦線2N代替曲線代替曲線2N；中間特征點(diǎn)提取結(jié)束。；中間特征點(diǎn)提取結(jié)束。至此可知，曲線至此可知，曲線MN可以用特征點(diǎn)可以用特征點(diǎn)M、1、3、2、N順序連接的順序連接的折線簡化

11、表示。折線簡化表示。 131.4 光欄法 原理：預(yù)先定義的一個(gè)扇形原理：預(yù)先定義的一個(gè)扇形( (“喇叭口喇叭口”），根據(jù)曲線上各節(jié)點(diǎn)），根據(jù)曲線上各節(jié)點(diǎn)是在扇形外還是在扇形內(nèi)，決定節(jié)點(diǎn)是保留還是舍去。是在扇形外還是在扇形內(nèi)，決定節(jié)點(diǎn)是保留還是舍去。設(shè)有曲線點(diǎn)列設(shè)有曲線點(diǎn)列Pi，i=1，2，n，“光欄口徑光欄口徑”為為d(由用戶自己定由用戶自己定義），則該方法實(shí)施的具體步驟：義），則該方法實(shí)施的具體步驟：(1)(1)連接連接p1和和p2，過過p2點(diǎn)作一條垂直點(diǎn)作一條垂直于于p1p2的直線，在該垂線上取兩點(diǎn)的直線，在該垂線上取兩點(diǎn)a1和和a2，使使a1p1=a2p2=d/2，此時(shí)此時(shí)a1和和a2為

12、為“光欄光欄”邊界點(diǎn)邊界點(diǎn)，p1與與a1、p1與與a2的連線為以的連線為以P P1 1為頂點(diǎn)的扇形的兩條邊，這就定義了一個(gè)扇為頂點(diǎn)的扇形的兩條邊，這就定義了一個(gè)扇形形( (這個(gè)扇形的口朝向曲線的前進(jìn)方向，邊長是任意的）。通過這個(gè)扇形的口朝向曲線的前進(jìn)方向，邊長是任意的）。通過p p1 1并在扇形內(nèi)的所有直線都具有這種性質(zhì)，并在扇形內(nèi)的所有直線都具有這種性質(zhì)， 即即p p1 1p p2 2上各點(diǎn)到這上各點(diǎn)到這些直線的垂距都不大于些直線的垂距都不大于d d/2/2。141.4 光欄法(2)若若p3點(diǎn)在扇形內(nèi)，則舍丟點(diǎn)在扇形內(nèi)，則舍丟p2點(diǎn)。然后連接點(diǎn)。然后連接p1和和p3，過過p3作作p1p3的垂

13、線，該垂線與前面定義的扇形邊交于的垂線，該垂線與前面定義的扇形邊交于c1和和c2。在垂線上。在垂線上找到找到b1和和b2點(diǎn)，使點(diǎn)，使p3b1 =p3b2=d/2，若若b1和和b2點(diǎn)落在原扇形外點(diǎn)落在原扇形外面（圖面（圖5.4中為中為b2點(diǎn)），則用點(diǎn)），則用c1或或c2取代取代(圖圖5.4中由中由c2取代取代b2)。此時(shí)用此時(shí)用p1b1和和p1c2定義一個(gè)新的扇形，這當(dāng)然是口徑定義一個(gè)新的扇形，這當(dāng)然是口徑(b1c2)縮縮小了的小了的“光欄光欄”。(3)檢查下一節(jié)點(diǎn)，若該點(diǎn)在新扇形內(nèi)，則重復(fù)第檢查下一節(jié)點(diǎn)，若該點(diǎn)在新扇形內(nèi)，則重復(fù)第(2)步；直到步；直到發(fā)現(xiàn)有一個(gè)節(jié)點(diǎn)在最新定義的扇形外為止發(fā)現(xiàn)有

14、一個(gè)節(jié)點(diǎn)在最新定義的扇形外為止。(4)當(dāng)發(fā)現(xiàn)在扇形外的節(jié)點(diǎn)，如圖當(dāng)發(fā)現(xiàn)在扇形外的節(jié)點(diǎn)，如圖5.4中的中的p4，此時(shí)保留點(diǎn)此時(shí)保留點(diǎn)p3，以以p3作為新起點(diǎn)，重復(fù)作為新起點(diǎn)，重復(fù)(1)(2)步。步。如此繼續(xù)下去，直到整個(gè)點(diǎn)列檢測(cè)完為止。所有被保留的點(diǎn)如此繼續(xù)下去，直到整個(gè)點(diǎn)列檢測(cè)完為止。所有被保留的點(diǎn)（含首、末點(diǎn)），順序地構(gòu)成了簡化后的新點(diǎn)列。（含首、末點(diǎn)），順序地構(gòu)成了簡化后的新點(diǎn)列。 151.4 光欄法161.5曲線壓縮算法的比較 v評(píng)價(jià)依據(jù)：評(píng)價(jià)依據(jù)：壓縮后的總長度、原曲線及壓縮后曲線的線性位壓縮后的總長度、原曲線及壓縮后曲線的線性位移移( (矢高和面積矢高和面積) ) 等。等。v線性位移

15、量評(píng)價(jià)：道格拉斯線性位移量評(píng)價(jià)：道格拉斯- -普克法具有最小的線性位移；普克法具有最小的線性位移；偏角法在所有的壓縮水平上較其他偏角法在所有的壓縮水平上較其他3 3種方法具有更大的線性種方法具有更大的線性位移量，但僅依據(jù)矢高位移量又很難對(duì)間隔取點(diǎn)法的算法作位移量，但僅依據(jù)矢高位移量又很難對(duì)間隔取點(diǎn)法的算法作出結(jié)論，而在出結(jié)論，而在舍去舍去30%-70%30%-70%的點(diǎn)時(shí)，無論按矢高位移量還是的點(diǎn)時(shí)，無論按矢高位移量還是按面積位移量來評(píng)價(jià)，垂距法顯然較偏角法和間隔取點(diǎn)法好按面積位移量來評(píng)價(jià)，垂距法顯然較偏角法和間隔取點(diǎn)法好171.5曲線壓縮算法的比較v結(jié)論：淘汰的點(diǎn)數(shù)越多，它們的壓縮效果越趨于

16、一致。結(jié)論：淘汰的點(diǎn)數(shù)越多，它們的壓縮效果越趨于一致。在一在一般情況下般情況下， 道格拉斯道格拉斯- -普克方法壓縮效果占優(yōu)普克方法壓縮效果占優(yōu)，其次是垂距，其次是垂距法、間隔取點(diǎn)法和偏角法，但道格拉斯法、間隔取點(diǎn)法和偏角法，但道格拉斯- -普克方法需對(duì)整條普克方法需對(duì)整條曲線完成數(shù)字化后方能進(jìn)行壓縮，曲線完成數(shù)字化后方能進(jìn)行壓縮， 且計(jì)算工作量較大。光且計(jì)算工作量較大。光欄法則不僅算法嚴(yán)密，能按給定閾值保留曲線特征點(diǎn)，并能欄法則不僅算法嚴(yán)密，能按給定閾值保留曲線特征點(diǎn)，并能實(shí)時(shí)處理，運(yùn)算量少，占用內(nèi)存少。實(shí)時(shí)處理，運(yùn)算量少，占用內(nèi)存少。181.6面域的數(shù)據(jù)壓縮算法v面域空間數(shù)據(jù)的壓縮過程面域

17、空間數(shù)據(jù)的壓縮過程可以看成是組成其邊界的曲線段的可以看成是組成其邊界的曲線段的分別壓縮，每段邊界曲線的壓縮過程如前所述分別壓縮，每段邊界曲線的壓縮過程如前所述。 v封閉曲線的數(shù)據(jù)壓縮封閉曲線的數(shù)據(jù)壓縮v公共節(jié)點(diǎn)的取舍問題公共節(jié)點(diǎn)的取舍問題191.6面域的數(shù)據(jù)壓縮算法封閉曲線的數(shù)據(jù)壓縮封閉曲線的數(shù)據(jù)壓縮v面域由首尾相連的封閉曲線組成。此時(shí)，可以人為地將該封面域由首尾相連的封閉曲線組成。此時(shí)，可以人為地將該封閉線分割為首尾相連的兩段曲線，然后就可以按前述方法進(jìn)閉線分割為首尾相連的兩段曲線，然后就可以按前述方法進(jìn)行壓縮。曲線分割的原則是：行壓縮。曲線分割的原則是：v（1 1）原節(jié)點(diǎn)是分割點(diǎn)之一；）原

18、節(jié)點(diǎn)是分割點(diǎn)之一；v（2 2）離原節(jié)點(diǎn)最遠(yuǎn)的下一節(jié)點(diǎn)是分割點(diǎn)之二。）離原節(jié)點(diǎn)最遠(yuǎn)的下一節(jié)點(diǎn)是分割點(diǎn)之二。201.6面域的數(shù)據(jù)壓縮算法v如圖如圖5.75.7所示，多邊形所示，多邊形P P的邊界曲線由從節(jié)點(diǎn)的邊界曲線由從節(jié)點(diǎn)A A出發(fā)的曲線封出發(fā)的曲線封閉而成；其中曲線上閉而成；其中曲線上B B點(diǎn)離節(jié)點(diǎn)點(diǎn)離節(jié)點(diǎn)A A最遠(yuǎn)。因而，多邊形最遠(yuǎn)。因而，多邊形P P的邊的邊界曲線可以分割為界曲線可以分割為AMBAMB和和 BNABNA兩段，進(jìn)而對(duì)曲線段兩段，進(jìn)而對(duì)曲線段AMBAMB和和 BNABNA分別進(jìn)行壓縮。分別進(jìn)行壓縮。211.6面域的數(shù)據(jù)壓縮算法公共節(jié)點(diǎn)的取舍問題公共節(jié)點(diǎn)的取舍問題v在某些特定情況

19、下，面域的邊界曲線由多段首尾相連的曲線在某些特定情況下，面域的邊界曲線由多段首尾相連的曲線連接而成，其壓縮可以分段進(jìn)行。此時(shí)各段曲線的起點(diǎn)和終連接而成，其壓縮可以分段進(jìn)行。此時(shí)各段曲線的起點(diǎn)和終點(diǎn)必然作為特征點(diǎn)提取出來，因而可能產(chǎn)生數(shù)據(jù)冗余。比如，點(diǎn)必然作為特征點(diǎn)提取出來，因而可能產(chǎn)生數(shù)據(jù)冗余。比如，當(dāng)前后曲線段過渡時(shí)很平緩，曲線段的公共節(jié)點(diǎn)可以不成為當(dāng)前后曲線段過渡時(shí)很平緩，曲線段的公共節(jié)點(diǎn)可以不成為特征點(diǎn)，即該點(diǎn)前后的兩段曲線可以直接用該點(diǎn)前后的兩個(gè)特征點(diǎn)，即該點(diǎn)前后的兩段曲線可以直接用該點(diǎn)前后的兩個(gè)特征點(diǎn)的連線來代替。特征點(diǎn)的連線來代替。221.6面域的數(shù)據(jù)壓縮算法v如圖如圖5.95.9

20、所示，所示，1 1、2 2號(hào)點(diǎn)分別是面域號(hào)點(diǎn)分別是面域P P的邊界曲線的邊界曲線ABAB、BCBC段的段的內(nèi)部特征提取點(diǎn)，內(nèi)部特征提取點(diǎn)， 因而可以用弦因而可以用弦1B1B、B2B2分別代替曲線分別代替曲線1B1B和和B2B2。而實(shí)際上，整個(gè)曲線。而實(shí)際上，整個(gè)曲線1B21B2仍可以用弦仍可以用弦1212來代替來代替。231.6面域的數(shù)據(jù)壓縮算法v在處理面域空間數(shù)據(jù)壓縮時(shí)，可以在邊界曲線分段壓縮的基在處理面域空間數(shù)據(jù)壓縮時(shí)，可以在邊界曲線分段壓縮的基礎(chǔ)上，礎(chǔ)上，增加一個(gè)步驟，即對(duì)邊界曲線的端點(diǎn)進(jìn)行可刪性檢驗(yàn)增加一個(gè)步驟，即對(duì)邊界曲線的端點(diǎn)進(jìn)行可刪性檢驗(yàn)：如果前一曲線最后提取的中間特征點(diǎn)與后一曲

21、線最先提取的如果前一曲線最后提取的中間特征點(diǎn)與后一曲線最先提取的中間特征點(diǎn)之間的曲線滿足極差控制條件，則兩條曲線的連中間特征點(diǎn)之間的曲線滿足極差控制條件，則兩條曲線的連接節(jié)點(diǎn)可以刪減；否則，不可刪減接節(jié)點(diǎn)可以刪減；否則，不可刪減。v由于各段邊界曲線的數(shù)據(jù)文件要重新生成，所以當(dāng)兩段曲線由于各段邊界曲線的數(shù)據(jù)文件要重新生成，所以當(dāng)兩段曲線的公共節(jié)點(diǎn)刪減之后，相當(dāng)于兩條曲線合并為一條曲線。此的公共節(jié)點(diǎn)刪減之后，相當(dāng)于兩條曲線合并為一條曲線。此時(shí)可能會(huì)擾亂拓?fù)潢P(guān)系時(shí)可能會(huì)擾亂拓?fù)潢P(guān)系( (如曲線如曲線ABAB或或BCBC為多邊形的公共邊，為多邊形的公共邊，或或ABAB和和BCBC均為多邊形的公共邊），

22、因此在處理公共節(jié)點(diǎn)的取均為多邊形的公共邊），因此在處理公共節(jié)點(diǎn)的取舍時(shí)要慎重，應(yīng)該對(duì)此加以限制。舍時(shí)要慎重，應(yīng)該對(duì)此加以限制。242 柵格數(shù)據(jù)的壓縮v2.1 2.1 鏈?zhǔn)骄幋a鏈?zhǔn)骄幋av2.2 2.2 游程長度編碼游程長度編碼v2.3 2.3 塊式編碼塊式編碼v2.4 2.4 差分映射法差分映射法v2.5 2.5 四叉樹編碼四叉樹編碼252 柵格數(shù)據(jù)的壓縮v柵格數(shù)據(jù)文件記錄有柵格數(shù)據(jù)文件記錄有3 3個(gè)基本方式：個(gè)基本方式：基于像元、基于層和基基于像元、基于層和基于面域。于面域。v共同點(diǎn)：對(duì)像元坐標(biāo)和屬性的記錄。共同點(diǎn)：對(duì)像元坐標(biāo)和屬性的記錄。v因此基于柵格的空間數(shù)據(jù)壓縮的因此基于柵格的空間數(shù)據(jù)壓

23、縮的實(shí)質(zhì)是研究柵格數(shù)據(jù)的編碼實(shí)質(zhì)是研究柵格數(shù)據(jù)的編碼，通過編碼盡量減少像元數(shù)量的存儲(chǔ)。通過編碼盡量減少像元數(shù)量的存儲(chǔ)。v分類：柵格數(shù)據(jù)的壓縮分為分類：柵格數(shù)據(jù)的壓縮分為無損壓縮技術(shù)和有損壓縮技術(shù)無損壓縮技術(shù)和有損壓縮技術(shù)。262 柵格數(shù)據(jù)的壓縮v無損壓縮無損壓縮方法利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，可完全恢復(fù)原方法利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真，但壓縮率受到數(shù)據(jù)統(tǒng)計(jì)冗余度的始數(shù)據(jù)而不引入任何失真，但壓縮率受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，一般為理論限制，一般為2 2：1 5:11 5:1。v有損壓縮有損壓縮方法利用了數(shù)據(jù)在使用中存在某些成分不敏感的特方法利用了數(shù)據(jù)在使用中

24、存在某些成分不敏感的特性，允許壓縮過程中損失一定的信息；雖然不能完全恢復(fù)原性，允許壓縮過程中損失一定的信息；雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對(duì)數(shù)據(jù)內(nèi)涵的影響較小，卻換來始數(shù)據(jù)，但是所損失的部分對(duì)數(shù)據(jù)內(nèi)涵的影響較小，卻換來了大得多的壓縮比。了大得多的壓縮比。272.1 鏈?zhǔn)骄幋av鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a又稱為弗里曼鏈碼（又稱為弗里曼鏈碼（FreemanFreeman，19611961年）或邊界鏈年）或邊界鏈碼。如圖碼。如圖5.105.10所示，其中的多邊形邊界可表示為：由某一原所示，其中的多邊形邊界可表示為：由某一原點(diǎn)開始并按某些基本方向確定的單位矢量鏈?；痉较蚩啥c(diǎn)開始并按某些基本方向確定

25、的單位矢量鏈?；痉较蚩啥x為義為: :東東=0=0，東南，東南=1=1，南，南=2=2，西南，西南=3=3，西，西=4=4，西北，西北=5=5，北，北= 6= 6，東北東北=7=7，8 8個(gè)基本方向個(gè)基本方向。282.1 鏈?zhǔn)骄幋a如果確定原點(diǎn)為像元如果確定原點(diǎn)為像元（1010，1)1)，則該多邊形，則該多邊形邊界按順時(shí)針方向的鏈邊界按順時(shí)針方向的鏈?zhǔn)骄幋a式編碼 ( (圖圖5.11)5.11)為：為：1010，1 1，7 7，0 0，1 1，0 0，7 7，1 1，7,07,0，0,20,2，3 3，2 2，2 2，1 1，0 0，7 7，0 0，0 0，0 0，0 0，2 2，4 4，3 3

26、，4 4，4 4，3 3， 4 4，4 4，5 5，4 4，5 5，4 4，5 5，4 4，5 5，4 4，6 6，6 6。292.1 鏈?zhǔn)骄幋av鏈?zhǔn)骄幋a的優(yōu)點(diǎn)鏈?zhǔn)骄幋a的優(yōu)點(diǎn)：鏈?zhǔn)骄幋a對(duì)多邊形的表示具有很強(qiáng)的數(shù)據(jù)：鏈?zhǔn)骄幋a對(duì)多邊形的表示具有很強(qiáng)的數(shù)據(jù)壓縮能力，且具有一定的運(yùn)算功能，如面積和周長計(jì)算等，壓縮能力，且具有一定的運(yùn)算功能，如面積和周長計(jì)算等，探測(cè)邊界急彎和凹進(jìn)部分等都比較容易；探測(cè)邊界急彎和凹進(jìn)部分等都比較容易；v鏈?zhǔn)骄幋a的缺點(diǎn)鏈?zhǔn)骄幋a的缺點(diǎn)是對(duì)疊置運(yùn)算如組合、相交等則很難實(shí)施，是對(duì)疊置運(yùn)算如組合、相交等則很難實(shí)施，對(duì)局部修改將改變整體結(jié)構(gòu)，效率較低，而且由于鏈碼以每對(duì)局部修改將改變

27、整體結(jié)構(gòu)，效率較低，而且由于鏈碼以每個(gè)區(qū)域?yàn)閱挝淮鎯?chǔ)邊界，相鄰區(qū)域的邊界則被重復(fù)存儲(chǔ)而產(chǎn)個(gè)區(qū)域?yàn)閱挝淮鎯?chǔ)邊界，相鄰區(qū)域的邊界則被重復(fù)存儲(chǔ)而產(chǎn)生冗余。生冗余。302.2游程長度編碼 v游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程長度編碼結(jié)構(gòu)是逐游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程長度編碼結(jié)構(gòu)是逐行行將相將相鄰?fù)档木W(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長鄰?fù)档木W(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。v游程長度編碼結(jié)構(gòu)的建立方法游程長度編碼結(jié)構(gòu)的建立方法是：將柵格矩陣的數(shù)據(jù)序列是：將柵格矩陣的數(shù)據(jù)序列X X1 1，X

28、 X2 2，X Xn n，映射為相應(yīng)的二元組序列，映射為相應(yīng)的二元組序列( (A Ai i，P Pi i），），i i=1=1，2,2,，K K，且，且K Knn。其中，。其中，A A為屬性值，為屬性值，P P為游程，為游程，K K為游程序?yàn)橛纬绦蛱?hào)。號(hào)。312.2游程長度編碼v游程長度編碼這種數(shù)據(jù)結(jié)構(gòu)特別適用于二值圖像數(shù)據(jù)的表示游程長度編碼這種數(shù)據(jù)結(jié)構(gòu)特別適用于二值圖像數(shù)據(jù)的表示 u游程編碼能否壓縮數(shù)據(jù)量，主要決定于柵格數(shù)據(jù)的性質(zhì)，游程編碼能否壓縮數(shù)據(jù)量，主要決定于柵格數(shù)據(jù)的性質(zhì)，通常可通過事先測(cè)試，估算圖層的數(shù)據(jù)冗余度通?？赏ㄟ^事先測(cè)試，估算圖層的數(shù)據(jù)冗余度Re：Re=1-Q/mn322.

29、2游程長度編碼vQ Q為圖層內(nèi)相鄰屬性值變化次數(shù)的累加和；為圖層內(nèi)相鄰屬性值變化次數(shù)的累加和；m m為圖層網(wǎng)格的行為圖層網(wǎng)格的行數(shù)；數(shù)；n n為圖層網(wǎng)格的列數(shù)。為圖層網(wǎng)格的列數(shù)。v當(dāng)當(dāng)ReRe的值大于的值大于1/51/5的情況下，表明柵格數(shù)據(jù)的壓縮可取得明的情況下，表明柵格數(shù)據(jù)的壓縮可取得明顯的效果。顯的效果。v壓縮效果可由壓縮比壓縮效果可由壓縮比S =n /KS =n /K來表征，即壓縮比的值愈大，來表征，即壓縮比的值愈大，表示壓縮效果愈顯著。表示壓縮效果愈顯著。332.3塊式編碼 v塊式編碼是將游程長度編碼擴(kuò)大到二塊式編碼是將游程長度編碼擴(kuò)大到二維的情況，把多邊形范圍劃分成由像維的情況，把

30、多邊形范圍劃分成由像元組成的正方形，然后對(duì)各個(gè)正方形元組成的正方形，然后對(duì)各個(gè)正方形進(jìn)行編碼。進(jìn)行編碼。v塊式塊式編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置（行編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置（行號(hào)，列號(hào)號(hào)，列號(hào)) )和半徑，再加上記錄單元的和半徑，再加上記錄單元的代碼組成。代碼組成。v根據(jù)這一編碼原則，圖根據(jù)這一編碼原則，圖5.155.15所示多邊所示多邊形只需形只需1717個(gè)單位正方形，個(gè)單位正方形，9 9個(gè)個(gè)4 4單位的單位的正方形和正方形和1 1個(gè)個(gè)1616單位的正方形就能完整單位的正方形就能完整表示，總共要表示，總共要5757個(gè)數(shù)據(jù)，其中個(gè)數(shù)據(jù)，其中2727對(duì)坐對(duì)坐標(biāo)，標(biāo)，3 3個(gè)塊的半徑。個(gè)塊的半徑。342

31、.3塊式編碼v塊式編碼的特點(diǎn)：一個(gè)多邊形所能包含的正方形越大，多邊塊式編碼的特點(diǎn)：一個(gè)多邊形所能包含的正方形越大，多邊形的邊界越簡單，塊式編碼的效果越好。形的邊界越簡單，塊式編碼的效果越好。v游程和塊式編碼都對(duì)大的復(fù)雜多邊形效果并不好。塊式編碼游程和塊式編碼都對(duì)大的復(fù)雜多邊形效果并不好。塊式編碼在合并、插入、檢查延伸性、計(jì)算面積等操作時(shí)有明顯的優(yōu)在合并、插入、檢查延伸性、計(jì)算面積等操作時(shí)有明顯的優(yōu)越性。越性。352.4差分映射法 v差分映射法，差分映射法，就是選擇某一參照值對(duì)有關(guān)柵格的屬性值進(jìn)行就是選擇某一參照值對(duì)有關(guān)柵格的屬性值進(jìn)行求差運(yùn)算，根據(jù)差值得到一個(gè)新的柵格數(shù)據(jù)層。求差運(yùn)算，根據(jù)差值

32、得到一個(gè)新的柵格數(shù)據(jù)層。v參照值的選擇有多種方式，即分行選取和全區(qū)選取。若分行參照值的選擇有多種方式，即分行選取和全區(qū)選取。若分行選取，則可選為該行首列的屬性值，也可以選為該行的屬性選取，則可選為該行首列的屬性值，也可以選為該行的屬性平均值；若全區(qū)選取，則可選為首行首列的屬性值，也可以平均值；若全區(qū)選取，則可選為首行首列的屬性值，也可以選為全區(qū)的屬性平均值。選為全區(qū)的屬性平均值。 362.4差分映射法v圖圖5.165.16為柵格數(shù)據(jù)示例。圖為柵格數(shù)據(jù)示例。圖5.175.17所示為按分行選取方式，以所示為按分行選取方式，以行首屬性值為參照，對(duì)圖行首屬性值為參照，對(duì)圖5.165.16作差分映射后的

33、結(jié)果?？梢钥醋鞑罘钟成浜蟮慕Y(jié)果。可以看出，經(jīng)差分映射處理后，除第一列外，其余柵格的數(shù)據(jù)出現(xiàn)出，經(jīng)差分映射處理后，除第一列外，其余柵格的數(shù)據(jù)出現(xiàn)為零、位數(shù)降低或數(shù)字減少。為零、位數(shù)降低或數(shù)字減少。372.4差分映射法v表表5.15.1為經(jīng)差分映射處理前后的各柵格屬性記錄所需字節(jié)數(shù)為經(jīng)差分映射處理前后的各柵格屬性記錄所需字節(jié)數(shù)的對(duì)比，可見，所需字節(jié)數(shù)由原來的的對(duì)比，可見，所需字節(jié)數(shù)由原來的7979減少為減少為 4444，減少，減少 44.3%44.3%。382.5 四叉樹編碼 v四叉樹又稱四元樹或四分樹，是四叉樹又稱四元樹或四分樹，是最有效最有效的柵格數(shù)據(jù)壓縮編碼的柵格數(shù)據(jù)壓縮編碼方法方法之一之一

34、。四分樹將整個(gè)圖像區(qū)域逐步分解為一系列方形區(qū)。四分樹將整個(gè)圖像區(qū)域逐步分解為一系列方形區(qū)域，且每一個(gè)方形區(qū)域具有單一的屬性。最小區(qū)域?yàn)橐粋€(gè)像域，且每一個(gè)方形區(qū)域具有單一的屬性。最小區(qū)域?yàn)橐粋€(gè)像元。元。 393 拓?fù)潢P(guān)系的生成 v拓?fù)淇臻g關(guān)系是一種對(duì)空間結(jié)構(gòu)進(jìn)行明確定義的數(shù)學(xué)方法，拓?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)。具有拓?fù)潢P(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)就是拓?fù)鋽?shù)據(jù)結(jié)構(gòu)。v它描述了基本空間目標(biāo)點(diǎn)、線、面之間的關(guān)聯(lián)、鄰接和包含它描述了基本空間目標(biāo)點(diǎn)、線、面之間的關(guān)聯(lián)、鄰接和包含關(guān)系。關(guān)系。v矢量數(shù)據(jù)拓?fù)潢P(guān)系在空間數(shù)據(jù)的查詢和分析過程中非常重要，矢量數(shù)

35、據(jù)拓?fù)潢P(guān)系在空間數(shù)據(jù)的查詢和分析過程中非常重要，拓?fù)鋽?shù)據(jù)結(jié)構(gòu)是地理信息系統(tǒng)分析和應(yīng)用功能所必需的。拓?fù)鋽?shù)據(jù)結(jié)構(gòu)是地理信息系統(tǒng)分析和應(yīng)用功能所必需的。v拓?fù)淇臻g關(guān)系信息是空間分析、輔助決策等的基礎(chǔ)，也是拓?fù)淇臻g關(guān)系信息是空間分析、輔助決策等的基礎(chǔ)，也是GISGIS區(qū)別于區(qū)別于CAD(CAD(計(jì)算機(jī)輔助設(shè)計(jì)計(jì)算機(jī)輔助設(shè)計(jì)) )等的主要標(biāo)志。等的主要標(biāo)志。 對(duì)于拓?fù)鋵?duì)于拓?fù)潢P(guān)系的自動(dòng)建立問題，研究的關(guān)系的自動(dòng)建立問題，研究的焦點(diǎn)焦點(diǎn)是是如何提高算法與過程的如何提高算法與過程的效率和自動(dòng)化程度，本節(jié)將講述其實(shí)現(xiàn)的基本步驟和要點(diǎn)。效率和自動(dòng)化程度，本節(jié)將講述其實(shí)現(xiàn)的基本步驟和要點(diǎn)。403 拓?fù)潢P(guān)系的生成

36、v拓?fù)潢P(guān)系自動(dòng)生成算法的一般過程為：拓?fù)潢P(guān)系自動(dòng)生成算法的一般過程為：（1 1）弧段處理：弧段處理：使整幅圖形中的所有弧段，除在端點(diǎn)處相交使整幅圖形中的所有弧段，除在端點(diǎn)處相交外，沒有其他交點(diǎn)，即沒有相交或自相交的弧段。外，沒有其他交點(diǎn)，即沒有相交或自相交的弧段。（2 2）結(jié)點(diǎn)匹配：結(jié)點(diǎn)匹配：建立結(jié)點(diǎn)、弧段關(guān)系。建立結(jié)點(diǎn)、弧段關(guān)系。（3 3）建立多邊形：建立多邊形：以左轉(zhuǎn)算法或右轉(zhuǎn)算法跟蹤，生成多邊形，以左轉(zhuǎn)算法或右轉(zhuǎn)算法跟蹤，生成多邊形，建立多邊形與弧段的拓?fù)潢P(guān)系。建立多邊形與弧段的拓?fù)潢P(guān)系。（4 4）建立多邊形與多邊形的拓?fù)潢P(guān)系：建立多邊形與多邊形的拓?fù)潢P(guān)系：調(diào)整弧段的左右多邊調(diào)整弧段的左

37、右多邊形標(biāo)識(shí)號(hào)。多邊形標(biāo)識(shí)號(hào)。多邊 形內(nèi)部標(biāo)識(shí)號(hào)的自動(dòng)生成。形內(nèi)部標(biāo)識(shí)號(hào)的自動(dòng)生成。413 拓?fù)潢P(guān)系的生成v3.1 3.1 基本數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)v3.2 3.2 弧段的預(yù)處理弧段的預(yù)處理v3.3 3.3 結(jié)點(diǎn)匹配算法結(jié)點(diǎn)匹配算法 v3.4 3.4 建立拓?fù)潢P(guān)系建立拓?fù)潢P(guān)系 423.1 基本數(shù)據(jù)結(jié)構(gòu)v（1 1）拓?fù)浣Y(jié)點(diǎn)）拓?fù)浣Y(jié)點(diǎn)v（2 2）拓?fù)浠《渭捌浔硎荆┩負(fù)浠《渭捌浔硎緑（3 3）拓?fù)涿婕捌浔硎荆┩負(fù)涿婕捌浔硎緑（4 4）拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系）拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系433.1 基本數(shù)據(jù)結(jié)構(gòu)v（1 1）拓?fù)浣Y(jié)點(diǎn)）拓?fù)浣Y(jié)點(diǎn)v結(jié)點(diǎn)用來描述如管線的交點(diǎn)、道路路口等現(xiàn)實(shí)世界的特征對(duì)結(jié)

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

39、段及其表示 拓?fù)浠《沃柑幱趦蓚€(gè)結(jié)點(diǎn)之間的點(diǎn)序列串拓?fù)浠《沃柑幱趦蓚€(gè)結(jié)點(diǎn)之間的點(diǎn)序列串，可以給弧，可以給弧段定義一個(gè)方向，或者定義為數(shù)字化弧段時(shí)從一個(gè)結(jié)點(diǎn)到另一段定義一個(gè)方向，或者定義為數(shù)字化弧段時(shí)從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的采點(diǎn)方向，或者硬性定義一個(gè)方向。個(gè)結(jié)點(diǎn)的采點(diǎn)方向，或者硬性定義一個(gè)方向。 定義方向后弧段開始的結(jié)點(diǎn)就稱為定義方向后弧段開始的結(jié)點(diǎn)就稱為起始結(jié)點(diǎn)起始結(jié)點(diǎn)，弧段結(jié)，弧段結(jié)束的結(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)的方向稱為“起終方向起終方向”，由終止結(jié)點(diǎn)到起始結(jié)點(diǎn)的方向稱為，由終止結(jié)點(diǎn)到起始結(jié)點(diǎn)的方向稱為“終起方終起方向向”。

40、弧段?；《纹鸾K方向左側(cè)的多邊形稱為弧段的左多邊形起終方向左側(cè)的多邊形稱為弧段的左多邊形，弧段，弧段起終方向右側(cè)的多邊形稱為弧段的右多邊形起終方向右側(cè)的多邊形稱為弧段的右多邊形。463.1 基本數(shù)據(jù)結(jié)構(gòu)v如果弧段的起始結(jié)點(diǎn)或終止結(jié)點(diǎn)只與一條弧段相關(guān)聯(lián)，則該如果弧段的起始結(jié)點(diǎn)或終止結(jié)點(diǎn)只與一條弧段相關(guān)聯(lián)，則該弧段稱為弧段稱為懸掛弧段懸掛弧段，如圖，如圖5.195.19所示的弧段所示的弧段L L為懸掛弧。一般為懸掛弧。一般可以通過標(biāo)識(shí)懸掛弧段來檢測(cè)原始矢量數(shù)據(jù)的質(zhì)量?？梢酝ㄟ^標(biāo)識(shí)懸掛弧段來檢測(cè)原始矢量數(shù)據(jù)的質(zhì)量。 弧段一般包括弧段號(hào)、弧段節(jié)點(diǎn)坐標(biāo)串、弧段起始和弧段一般包括弧段號(hào)、弧段節(jié)點(diǎn)坐標(biāo)串、弧段

41、起始和終止結(jié)點(diǎn)、弧段左右多邊形。終止結(jié)點(diǎn)、弧段左右多邊形。 473.1 基本數(shù)據(jù)結(jié)構(gòu)483.1 基本數(shù)據(jù)結(jié)構(gòu)v（3 3）拓?fù)涿婕捌浔硎荆┩負(fù)涿婕捌浔硎緑拓?fù)涿媸怯梢粭l或若干條弧段首尾相連接而成的邊線所包含拓?fù)涿媸怯梢粭l或若干條弧段首尾相連接而成的邊線所包含的區(qū)域的區(qū)域，內(nèi)部包含有其他拓?fù)涿娴耐負(fù)涿嬉话惴Q為，內(nèi)部包含有其他拓?fù)涿娴耐負(fù)涿嬉话惴Q為復(fù)雜面復(fù)雜面，被包含的拓?fù)涿娣Q為被包含的拓?fù)涿娣Q為島島，沒有島的拓?fù)涿娣Q為，沒有島的拓?fù)涿娣Q為簡單面簡單面，如圖，如圖5.205.20所示。對(duì)于拓?fù)涿嬉部梢远x所示。對(duì)于拓?fù)涿嬉部梢远x正反方向正反方向，一般定義為：，一般定義為：當(dāng)沿拓?fù)涿娴倪吔缜斑M(jìn)時(shí)，被

42、弧段所包圍的面域始終處于弧當(dāng)沿拓?fù)涿娴倪吔缜斑M(jìn)時(shí)，被弧段所包圍的面域始終處于弧段的右側(cè)時(shí)的方向就是正方向；反之，則是反方向。段的右側(cè)時(shí)的方向就是正方向；反之，則是反方向。493.1 基本數(shù)據(jù)結(jié)構(gòu)v如圖如圖5.215.21所示，箭頭所指向的方向就是正方向，可以看出對(duì)所示，箭頭所指向的方向就是正方向，可以看出對(duì)于拓?fù)涿娴耐膺吔纾槙r(shí)針方向是正方向，而對(duì)于內(nèi)邊界逆于拓?fù)涿娴耐膺吔纾槙r(shí)針方向是正方向，而對(duì)于內(nèi)邊界逆時(shí)針方向就是正方向。時(shí)針方向就是正方向。503.1 基本數(shù)據(jù)結(jié)構(gòu)v多邊形一般包括多邊形一般包括多邊形號(hào)、中心點(diǎn)坐標(biāo)、多邊形屬性數(shù)據(jù)、多邊形號(hào)、中心點(diǎn)坐標(biāo)、多邊形屬性數(shù)據(jù)、多邊形的組成弧段號(hào)

43、、多邊形島多邊形的組成弧段號(hào)、多邊形島的信息?？紤]到組成弧段的的信息。考慮到組成弧段的方向和多邊形頂點(diǎn)序列的方向存在可能的不一致性以及效率方向和多邊形頂點(diǎn)序列的方向存在可能的不一致性以及效率問題，可以改為記錄組成多邊形的弧段指針和方向性信息，問題，可以改為記錄組成多邊形的弧段指針和方向性信息，即弧段方向與多邊形的方向是否一致。即弧段方向與多邊形的方向是否一致。v對(duì)于島的信息則通過將構(gòu)成多邊形的邊線分塊來處理的方式對(duì)于島的信息則通過將構(gòu)成多邊形的邊線分塊來處理的方式體現(xiàn)，比如多邊形包含島嶼，則可以使多邊形的外邊界成為體現(xiàn)，比如多邊形包含島嶼，則可以使多邊形的外邊界成為多邊形的第一部分，島嶼作為多

44、邊形的第二、三、四等部分多邊形的第一部分，島嶼作為多邊形的第二、三、四等部分的方式加以解決。的方式加以解決。 51523.1 基本數(shù)據(jù)結(jié)構(gòu)(4)(4)拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系533.2弧段的預(yù)處理 v拓?fù)潢P(guān)系自動(dòng)建立的第一步就是處理弧段，使得弧段不存在拓?fù)潢P(guān)系自動(dòng)建立的第一步就是處理弧段，使得弧段不存在自相交和相交現(xiàn)象。自相交和相交現(xiàn)象。v（1 1）直線段相交的判斷方法）直線段相交的判斷方法v（2 2）自相交弧段處理）自相交弧段處理v（3 3）弧段相交打斷處理）弧段相交打斷處理54(1)直線段相交的判斷方法v直線相交的判定方法有很多種，這里介紹較快的一種算法。直

45、線相交的判定方法有很多種，這里介紹較快的一種算法。v設(shè)直線設(shè)直線L L過點(diǎn)過點(diǎn)P P0 0（x x0 0，y y0 0）和點(diǎn)）和點(diǎn)P P1 1（x x1 1，y y1 1），則直線），則直線L L的方程的方程可以表示為：可以表示為：v將方程化為參數(shù)形式：將方程化為參數(shù)形式：y y= =y y0 0+(+(y y1 1- -y y0 0) )t t, , x x= =x x0 0+(+(x x1 1- -x x0 0) )t t，其，其中中t t0,10,1。v設(shè)有兩條直線設(shè)有兩條直線L L1 1和和L L2 2，它們的參數(shù)方程分別為，它們的參數(shù)方程分別為y y= =y y0 0+(+(y y1

46、 1- -y y0 0) )t t，x x= =x x0 0+(+(x x1 1- -x x0 0) )t t 和和y y= =y y0 0+(+(y y1 1- -y y0 0) )，x x= =x x0 0+(+(x x1 1- -x x0 0) )001010yyxxtyyxx55(1)直線段相交的判斷方法v判斷兩線段有無交點(diǎn)的關(guān)鍵變?yōu)榕袛嗯袛鄡删€段有無交點(diǎn)的關(guān)鍵變?yōu)榕袛鄑 t和和v v；是否符合不等式；是否符合不等式00t t11且且00v v11。令：。令：如果如果dxdx dydy - - dydy dxdx = 0= 0，說明兩線段平行或者重，說明兩線段平行或者重合，沒有交點(diǎn)，或

47、者交點(diǎn)在兩線段的頭或尾上；否則如果合，沒有交點(diǎn)，或者交點(diǎn)在兩線段的頭或尾上；否則如果滿足不等式滿足不等式00t t11且且00v v11，兩線段有交點(diǎn)，交點(diǎn)在兩，兩線段有交點(diǎn)，交點(diǎn)在兩線段的中間。線段的中間。56（2）自相交弧段處理v具有自相交特征的弧段至少具有具有自相交特征的弧段至少具有4 4個(gè)個(gè)( (結(jié)結(jié)) )節(jié)點(diǎn)，由節(jié)點(diǎn)，由3 3個(gè)點(diǎn)或個(gè)點(diǎn)或2 2個(gè)點(diǎn)組成的弧段不可能自相交。依次取出每一條弧段，如果個(gè)點(diǎn)組成的弧段不可能自相交。依次取出每一條弧段，如果弧段的弧段的( (結(jié)結(jié)) )節(jié)點(diǎn)個(gè)數(shù)不少于節(jié)點(diǎn)個(gè)數(shù)不少于4 4個(gè)，就利用直線段相交的方法，個(gè)，就利用直線段相交的方法，對(duì)組成弧段的各直線段進(jìn)

48、行判斷，如果相交，將線段斷開為對(duì)組成弧段的各直線段進(jìn)行判斷，如果相交，將線段斷開為兩條，自相交的弧段可能不止有一處相交，可以通過遞歸的兩條，自相交的弧段可能不止有一處相交，可以通過遞歸的方法將弧段分開。方法將弧段分開。575859（3）弧段相交打斷處理v弧段與弧段相交關(guān)系的判斷，可以通過取每一條弧段與其他弧段與弧段相交關(guān)系的判斷，可以通過取每一條弧段與其他未判斷過的所有弧段目標(biāo)進(jìn)行相交關(guān)系判斷而得，從而要進(jìn)未判斷過的所有弧段目標(biāo)進(jìn)行相交關(guān)系判斷而得，從而要進(jìn)行行（n - 1) + ( n - 2) + 3 + 2 + 1 = n（n 1）/2次判斷。次判斷。v具體方法具體方法為：取出第一條弧段

49、，與其他為：取出第一條弧段，與其他n - 1n - 1條弧段進(jìn)行相條弧段進(jìn)行相交判斷，求得交點(diǎn)后，將交點(diǎn)分別插入第一條弧段和與其相交判斷，求得交點(diǎn)后，將交點(diǎn)分別插入第一條弧段和與其相交弧段的對(duì)應(yīng)位置上，并記錄位置。將第一條弧段與所有其交弧段的對(duì)應(yīng)位置上，并記錄位置。將第一條弧段與所有其他弧段的相交關(guān)系判斷完畢后，通過記錄下的交點(diǎn)位置將第他弧段的相交關(guān)系判斷完畢后，通過記錄下的交點(diǎn)位置將第一條弧段分割，然后依次取出下一條弧段進(jìn)行同樣的處理，一條弧段分割，然后依次取出下一條弧段進(jìn)行同樣的處理，直到所有弧段處理完畢直到所有弧段處理完畢。 60（3）弧段相交打斷處理v由于由于GISGIS的數(shù)據(jù)量大，造

50、成了判斷的工作量大、效率低下的的數(shù)據(jù)量大，造成了判斷的工作量大、效率低下的弊端，在判斷兩條弧段的關(guān)系時(shí)，應(yīng)盡可能地減少計(jì)算量。弊端，在判斷兩條弧段的關(guān)系時(shí)，應(yīng)盡可能地減少計(jì)算量。v減少計(jì)算量方法減少計(jì)算量方法：分兩步，首先是判斷兩條弧段的最小矩形：分兩步，首先是判斷兩條弧段的最小矩形壁包壁包(MBR)(MBR)是否相交或具有包含關(guān)系，如果不相交或沒有包是否相交或具有包含關(guān)系，如果不相交或沒有包含關(guān)系，那么可以斷定兩條弧段是互不相交的；如果相交或含關(guān)系，那么可以斷定兩條弧段是互不相交的；如果相交或具有包含關(guān)系，則進(jìn)一步判斷第一條弧段的每一條組成線段具有包含關(guān)系，則進(jìn)一步判斷第一條弧段的每一條組成

51、線段是否和第二條弧段的是否和第二條弧段的MBRMBR相交或被包含，如果不相交或沒有相交或被包含，如果不相交或沒有被包含則可以判斷這一部分線段不會(huì)和第二條弧段相交，否被包含則可以判斷這一部分線段不會(huì)和第二條弧段相交，否則可以使用這一條線段與組成第二條弧段的各個(gè)線段進(jìn)行相則可以使用這一條線段與組成第二條弧段的各個(gè)線段進(jìn)行相交關(guān)系的判定來確定交點(diǎn)。交關(guān)系的判定來確定交點(diǎn)。613.3結(jié)點(diǎn)匹配算法 v結(jié)點(diǎn)匹配結(jié)點(diǎn)匹配就是把一定容差范圍內(nèi)的弧段的結(jié)點(diǎn)合并成為一個(gè)就是把一定容差范圍內(nèi)的弧段的結(jié)點(diǎn)合并成為一個(gè)結(jié)點(diǎn)，其坐標(biāo)值可以是取多個(gè)結(jié)點(diǎn)的平均值，或者選中一個(gè)結(jié)點(diǎn)，其坐標(biāo)值可以是取多個(gè)結(jié)點(diǎn)的平均值，或者選中一

52、個(gè)結(jié)點(diǎn)作為所有結(jié)點(diǎn)的坐標(biāo)區(qū)中心的坐標(biāo)。結(jié)點(diǎn)作為所有結(jié)點(diǎn)的坐標(biāo)區(qū)中心的坐標(biāo)。623.3結(jié)點(diǎn)匹配算法v每條弧段對(duì)應(yīng)著兩個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)在合并前對(duì)應(yīng)著一條弧每條弧段對(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)對(duì)應(yīng)的弧段也合并在一起。一起。v具體的思路具體的思路是將所有的結(jié)點(diǎn)加入結(jié)點(diǎn)集合，從結(jié)點(diǎn)集合中取是將所有的結(jié)點(diǎn)加入結(jié)點(diǎn)集合，從結(jié)點(diǎn)集合中取出一個(gè)結(jié)點(diǎn)作為中心點(diǎn)，從余下的結(jié)點(diǎn)中找出容差范圍內(nèi)的出一個(gè)結(jié)點(diǎn)作為中心點(diǎn)，從余下的結(jié)點(diǎn)中找出容差范圍內(nèi)的其他結(jié)點(diǎn)，將這些結(jié)點(diǎn)所對(duì)應(yīng)的弧段加入中心結(jié)點(diǎn)的弧段集其他結(jié)點(diǎn)，將這些結(jié)點(diǎn)

53、所對(duì)應(yīng)的弧段加入中心結(jié)點(diǎn)的弧段集合中，同時(shí)將弧段的對(duì)應(yīng)的結(jié)點(diǎn)變?yōu)橹行慕Y(jié)點(diǎn)，并修改弧段合中，同時(shí)將弧段的對(duì)應(yīng)的結(jié)點(diǎn)變?yōu)橹行慕Y(jié)點(diǎn)，并修改弧段的相應(yīng)坐標(biāo)。的相應(yīng)坐標(biāo)。 633.4建立拓?fù)潢P(guān)系 v（）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角（）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角, ,并按由小到大排序并按由小到大排序v（）左轉(zhuǎn)算法（）左轉(zhuǎn)算法v（）島的判斷（）島的判斷64（）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角v每個(gè)結(jié)點(diǎn)都關(guān)聯(lián)有若干條弧段，結(jié)點(diǎn)或者為弧段的頭結(jié)點(diǎn)或每個(gè)結(jié)點(diǎn)都關(guān)聯(lián)有若干條弧段，結(jié)點(diǎn)或者為弧段的頭結(jié)點(diǎn)或者為弧段的尾結(jié)點(diǎn)，設(shè)結(jié)點(diǎn)為者為弧段的尾結(jié)點(diǎn)，設(shè)結(jié)點(diǎn)為N N，則弧段的，則弧段的方位角方位角定義為：定義為：結(jié)點(diǎn)結(jié)點(diǎn)N N與弧段上

54、與其最接近結(jié)點(diǎn)與弧段上與其最接近結(jié)點(diǎn)V V的連線與的連線與軸的正向夾角。軸的正向夾角。65（）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角v設(shè)結(jié)點(diǎn)設(shè)結(jié)點(diǎn)N N的坐標(biāo)為的坐標(biāo)為( (x x0 0，y y0 0 ) )，節(jié)點(diǎn)，節(jié)點(diǎn)v v的坐標(biāo)為的坐標(biāo)為( (x x1 1，y y1 1) )，則有：，則有：dxdx= =x x1 1- -x x0 0，dydy= =y y1 1- -y y0 0，那么有，那么有 v當(dāng)當(dāng)dx=0dx=0時(shí)時(shí): :計(jì)算出結(jié)點(diǎn)計(jì)算出結(jié)點(diǎn)N N所關(guān)聯(lián)的弧段的方位角后，按角的大小將這些所關(guān)聯(lián)的弧段的方位角后，按角的大小將這些弧排序，形成排序的關(guān)聯(lián)弧段集合弧排序，形成排序的關(guān)聯(lián)弧段集合。66（2）

55、左轉(zhuǎn)算法v算法基本思想算法基本思想：從組成多邊形邊界的某一條弧段開始，如果：從組成多邊形邊界的某一條弧段開始，如果該弧段的方向角最小或介于同一結(jié)點(diǎn)的其他弧段方向角之間，該弧段的方向角最小或介于同一結(jié)點(diǎn)的其他弧段方向角之間，則則逆時(shí)針方向逆時(shí)針方向?qū)ふ易钚A角偏差所對(duì)應(yīng)的弧段為多邊形的后尋找最小夾角偏差所對(duì)應(yīng)的弧段為多邊形的后續(xù)弧段；如果該弧段與續(xù)弧段；如果該弧段與X X軸正向夾角為最大，則從該弧段的軸正向夾角為最大，則從該弧段的同一結(jié)點(diǎn)出發(fā)的其他弧段中，方向角最小的弧段是該多邊形同一結(jié)點(diǎn)出發(fā)的其他弧段中，方向角最小的弧段是該多邊形的后續(xù)弧段。的后續(xù)弧段。67（2）左轉(zhuǎn)算法v算法描述如下：算法描

56、述如下：（1 1）順序取一個(gè)結(jié)點(diǎn)作為起始結(jié)點(diǎn)，取完為止；取過該結(jié)點(diǎn)）順序取一個(gè)結(jié)點(diǎn)作為起始結(jié)點(diǎn)，取完為止；取過該結(jié)點(diǎn)的方位角最小的未使用過的或僅使用過一次，且使用過的方的方位角最小的未使用過的或僅使用過一次，且使用過的方向與本次相反的弧段作為起始弧段。向與本次相反的弧段作為起始弧段。（2 2）取這條弧段的另一個(gè)結(jié)點(diǎn)，找這個(gè)結(jié)點(diǎn)關(guān)聯(lián)的弧段集合）取這條弧段的另一個(gè)結(jié)點(diǎn)，找這個(gè)結(jié)點(diǎn)關(guān)聯(lián)的弧段集合中的本條弧段的下一條弧段，如果條弧段是最后一條弧段，中的本條弧段的下一條弧段，如果條弧段是最后一條弧段，則取弧段集合的第一條弧段，作為下一條弧段。則取弧段集合的第一條弧段，作為下一條弧段。68（2）左轉(zhuǎn)算法（

57、3 3）判斷是否回到起點(diǎn)，如果是，則形成了一個(gè)多邊形，記）判斷是否回到起點(diǎn)，如果是，則形成了一個(gè)多邊形，記錄下它，并且根據(jù)弧段的方向，設(shè)置組成該多邊形的左右多錄下它，并且根據(jù)弧段的方向，設(shè)置組成該多邊形的左右多邊形信息；否則轉(zhuǎn)邊形信息；否則轉(zhuǎn)(2)(2)。（4 4）取起始點(diǎn)上開始的，剛才所形成多邊形的最后一條邊作）取起始點(diǎn)上開始的，剛才所形成多邊形的最后一條邊作為新的起始弧段，為新的起始弧段， 轉(zhuǎn)轉(zhuǎn)(2)(2)；若這條弧段已經(jīng)使用過兩次，即；若這條弧段已經(jīng)使用過兩次，即形成了兩個(gè)多邊形，轉(zhuǎn)形成了兩個(gè)多邊形，轉(zhuǎn)(1)(1)。v在構(gòu)建多邊形時(shí)要注意懸掛結(jié)點(diǎn)和懸掛線的標(biāo)識(shí)，一般可以在構(gòu)建多邊形時(shí)要注

58、意懸掛結(jié)點(diǎn)和懸掛線的標(biāo)識(shí)，一般可以采用棧的形式處理。采用棧的形式處理。69（2）左轉(zhuǎn)算法（1 1）從）從N N1 1結(jié)點(diǎn)開始，選擇具有最小結(jié)點(diǎn)開始，選擇具有最小方位角的弧段方位角的弧段N N1 1N N2 2作為起始弧段；轉(zhuǎn)作為起始弧段；轉(zhuǎn)入入N N2 2點(diǎn)，根據(jù)左轉(zhuǎn)算法選擇點(diǎn)，根據(jù)左轉(zhuǎn)算法選擇N N2 2N N5 5弧段，弧段，轉(zhuǎn)入轉(zhuǎn)入N N5 5結(jié)點(diǎn)選擇結(jié)點(diǎn)選擇N N5 5N N1 1弧段，形成多邊弧段，形成多邊形形A A1 1，設(shè)置組成多邊形，設(shè)置組成多邊形A A1 1的弧段的左的弧段的左右多邊形信息。右多邊形信息。（2 2）A A1 1的結(jié)束弧段為的結(jié)束弧段為N N5 5N N1 1，

59、選，選N N1 1作作為起始點(diǎn)，為起始點(diǎn)，N N1 1N N5 5作為起始弧段，根據(jù)作為起始弧段，根據(jù)左轉(zhuǎn)算法，形成多邊形左轉(zhuǎn)算法，形成多邊形A A2 2，設(shè)置左，設(shè)置左右多邊形信息。右多邊形信息。 70（2）左轉(zhuǎn)算法（3 3）A A2 2的結(jié)束弧段為的結(jié)束弧段為N N4 4N N1 1，選，選N N1 1作為起始點(diǎn)，作為起始點(diǎn)，N N1 1N N4 4作為起始弧作為起始弧段，根據(jù)段，根據(jù) 、左轉(zhuǎn)算法，形成多邊形、左轉(zhuǎn)算法，形成多邊形A A3 3，這個(gè)多邊形的方向，這個(gè)多邊形的方向是逆時(shí)針方向，對(duì)于逆時(shí)針方向的多邊形，不設(shè)置左右多邊是逆時(shí)針方向，對(duì)于逆時(shí)針方向的多邊形，不設(shè)置左右多邊形信息。形信息。71（2）左轉(zhuǎn)算法（4 4）A A3 3的結(jié)束弧段為的結(jié)束弧段為N N2 2N N1 1， N N1 1N N2 2已經(jīng)被使用過兩次，所以選取已經(jīng)被使用過兩次，所以選取下一個(gè)結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)N N2 2作為起始結(jié)點(diǎn)。從作為起始結(jié)點(diǎn)。從N N2 2結(jié)點(diǎn)開始，具有最小方結(jié)點(diǎn)開始，具有最小方位角的弧段是位角的弧段是N N2 2N N1 1，但，但N N2 2N N1 1已經(jīng)被使用兩次，不選；已經(jīng)被使用兩次，不選； 繼續(xù)選取下一條弧段繼續(xù)選取下一條弧段N N2 2N N5 5；然而上一次該弧段的訪問；然而上一次該弧段的訪問方向與本次相同，所以也不選；繼續(xù)選取下一條弧段方