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

1、1空間數(shù)據(jù)組織算法 第六章2本講內(nèi)容1 矢量數(shù)據(jù)的緊縮2 柵格數(shù)據(jù)的緊縮3 拓?fù)潢P(guān)系的生成 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ù)的精度降低了。41 矢量數(shù)據(jù)的緊縮1.1 間隔取點(diǎn)法1.2 垂距法和偏角法1.3 道格拉斯-普克法1.4 光欄法1.5 曲線緊縮算法的比較1.6 面域的數(shù)據(jù)緊縮算法51.1 間隔取點(diǎn)法原理：每隔K個(gè)點(diǎn)取一點(diǎn)，或舍去那些離已選點(diǎn)比規(guī)定間隔更近的點(diǎn)，但首、末點(diǎn)一定要保管，如圖5.1所

2、示。 優(yōu)缺陷：可大量緊縮數(shù)字化儀用延續(xù)方法獲取的點(diǎn)列中的點(diǎn)、曲率顯著變化的點(diǎn)，但不一定能恰當(dāng)?shù)乇９芊较蛏锨曙@著變化的點(diǎn)。61.2 垂距法和偏角法原理：按垂距或偏角的限差，選取符合或超越限差的點(diǎn)。優(yōu)缺陷：不能同時(shí)思索相鄰點(diǎn)間的方向與間隔，且有能夠舍去不該舍去的點(diǎn)，但較前一種方法有提高。71.3 道格拉斯-普克法 原理：將一條曲線首、末點(diǎn)連一條直線，求出其他各點(diǎn)到該直線的間隔，選其最大者與規(guī)定的臨界值相比較，假設(shè)大于臨界值，那么離該直線間隔最大的點(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), (

3、x2,y2), (x3,y3),(xn,yn)。其中P1，Pn代分別對(duì)應(yīng)曲線的起點(diǎn)M和終點(diǎn)N。根據(jù)運(yùn)用需求和數(shù)據(jù)精度要求，給定控制數(shù)據(jù)緊縮的極差為，表示為被舍棄的點(diǎn)偏離特征點(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：91.3 道格拉斯-普克法第五步：決議取舍，提取中間特征點(diǎn)。(1)假設(shè)Q=0，那

4、么直接可以用弦線MN(M、N為特征點(diǎn))替代曲線MN；轉(zhuǎn)第六步。(2)假設(shè)Q = 1，那么將dh所對(duì)應(yīng)的點(diǎn)Pi(Xi，yi )抽出，暫時(shí)作為中間特征點(diǎn)；然后銜接新弦線MPj；轉(zhuǎn)第一步(以MPj已替代MN，繼續(xù)計(jì)算和判別)。 假設(shè)Q = 0，那么可以用弦線MPj替代曲線MPj；將Pj作為中間特征點(diǎn)取出；順序排在M點(diǎn)之后，成為繼M之后的第一個(gè)中間特征點(diǎn)；并銜接PjN，轉(zhuǎn)第一步以PjN替代MN，繼續(xù)計(jì)算和判別)101.3 道格拉斯-普克法 假設(shè)Q = 1，那么不可以用弦線MPj替代曲線MPj；找到此時(shí)dh所對(duì)應(yīng)的點(diǎn)Pk， 并銜接新弦線MPk；轉(zhuǎn)第一步(以MPk替代MN，繼續(xù)計(jì)算和判別) 第六步：構(gòu)成新

5、的數(shù)據(jù)文件。 將一切提取出的中間特征點(diǎn)從起點(diǎn)M開場(chǎng)，順序陳列至終點(diǎn)N，并寫入新的數(shù)據(jù)文件，即得到化簡后的折線的數(shù)據(jù)文件。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)

6、之后提取出的第二個(gè)特征點(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)提取終了。至此可知，曲線MN可以用特征點(diǎn)M、1、3、2、N順序銜接的折線簡化表示。 131.4 光欄法 原理：預(yù)先定義的一個(gè)扇形(“喇叭口，根據(jù)曲線上各節(jié)點(diǎn)是在扇形外還是在扇形內(nèi)，決議節(jié)點(diǎn)是保管還是舍去。設(shè)有曲線點(diǎn)列Pi，i=1，2，n，“光欄口徑

7、為d(由用戶本人定義，那么該方法實(shí)施的詳細(xì)步驟：(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)方向，邊長是恣意的。經(jīng)過p1并在扇形內(nèi)的一切直線都具有這種性質(zhì)， 即p1p2上各點(diǎn)到這些直線的垂距都不大于d/2。141.4 光欄法(2)假設(shè)p3點(diǎn)在扇形內(nèi)，那么舍丟p2點(diǎn)。然后銜接p1和p3，過p3作p1p3的垂線，該垂線與前面定義的扇形邊交于c1和c2。在垂線上找到b1和b2點(diǎn)，使p3b1 =p3

8、b2=d/2，假設(shè)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)，假設(shè)該點(diǎn)在新扇形內(nèi)，那么反復(fù)第(2)步；直到發(fā)現(xiàn)有一個(gè)節(jié)點(diǎn)在最新定義的扇形外為止。(4)當(dāng)發(fā)如今扇形外的節(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)列。 151.4 光欄法161.5曲線緊縮算法的比較 評(píng)價(jià)根據(jù)：緊縮后的總長度、原曲線及緊縮后曲線的線性位移(矢

9、高和面積) 等。線性位移量評(píng)價(jià)：道格拉斯-普克法具有最小的線性位移；偏角法在一切的緊縮程度上較其他3種方法具有更大的線性位移量，但僅根據(jù)矢高位移量又很難對(duì)間隔取點(diǎn)法的算法作出結(jié)論，而在舍去30%-70%的點(diǎn)時(shí)，無論按矢高位移量還是按面積位移量來評(píng)價(jià)，垂距法顯然較偏角法和間隔取點(diǎn)法好171.5曲線緊縮算法的比較結(jié)論：淘汰的點(diǎn)數(shù)越多，它們的緊縮效果越趨于一致。在普通情況下， 道格拉斯-普克方法緊縮效果占優(yōu)，其次是垂距法、間隔取點(diǎn)法和偏角法，但道格拉斯-普克方法需對(duì)整條曲線完成數(shù)字化后方能進(jìn)展緊縮， 且計(jì)算任務(wù)量較大。光欄法那么不僅算法嚴(yán)密，能按給定閾值保管曲線特征點(diǎn)，并能實(shí)時(shí)處置，運(yùn)算量少，占用內(nèi)

10、存少。181.6面域的數(shù)據(jù)緊縮算法面域空間數(shù)據(jù)的緊縮過程可以看成是組成其邊境的曲線段的分別緊縮，每段邊境曲線的緊縮過程如前所述。 封鎖曲線的數(shù)據(jù)緊縮公共節(jié)點(diǎn)的取舍問題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)之二。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和

11、 BNA分別進(jìn)展緊縮。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)的連線來替代。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來替代。231.6面域的數(shù)據(jù)緊縮算法在處置面域空間數(shù)據(jù)緊縮

12、時(shí)，可以在邊境曲線分段緊縮的根底上，添加一個(gè)步驟，即對(duì)邊境曲線的端點(diǎn)進(jìn)展可刪性檢驗(yàn)：假設(shè)前一曲線最后提取的中間特征點(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ì)此加以限制。242 柵格數(shù)據(jù)的緊縮2.1 鏈?zhǔn)骄幋a2.2 游程長度編碼2.3 塊式編碼2.4 差分映射法2.5 四叉樹編碼252 柵格數(shù)據(jù)的緊縮

13、柵格數(shù)據(jù)文件記錄有3個(gè)根本方式：基于像元、基于層和基于面域。共同點(diǎn)：對(duì)像元坐標(biāo)和屬性的記錄。因此基于柵格的空間數(shù)據(jù)緊縮的本質(zhì)是研討柵格數(shù)據(jù)的編碼，經(jīng)過編碼盡量減少像元數(shù)量的存儲(chǔ)。分類：柵格數(shù)據(jù)的緊縮分為無損緊縮技術(shù)和有損緊縮技術(shù)。262 柵格數(shù)據(jù)的緊縮無損緊縮方法利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)展緊縮，可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真，但緊縮率遭到數(shù)據(jù)統(tǒng)計(jì)冗余度的實(shí)際限制，普通為2：1 5:1。有損緊縮方法利用了數(shù)據(jù)在運(yùn)用中存在某些成分不敏感的特性，允許緊縮過程中損失一定的信息；雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對(duì)數(shù)據(jù)內(nèi)涵的影響較小，卻換來了大得多的緊縮比。272.1 鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a又稱為弗里

14、曼鏈碼Freeman，1961年或邊境鏈碼。如圖5.10所示，其中的多邊形邊境可表示為：由某一原點(diǎn)開場(chǎng)并按某些根本方向確定的單位矢量鏈。根本方向可定義為:東=0，東南=1，南=2，西南=3，西=4，西北=5，北= 6，東北=7，8個(gè)根本方向。282.1 鏈?zhǔn)骄幋a假設(shè)確定原點(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。292.1 鏈?zhǔn)骄幋a鏈?zhǔn)骄幋a的優(yōu)點(diǎn)：鏈?zhǔn)骄幋a對(duì)多邊形的表示具有很強(qiáng)的數(shù)據(jù)緊縮才干，且具

15、有一定的運(yùn)算功能，如面積和周長計(jì)算等，探測(cè)邊境急彎和凹進(jìn)部分等都比較容易；鏈?zhǔn)骄幋a的缺陷是對(duì)疊置運(yùn)算如組合、相交等那么很難實(shí)施，對(duì)部分修正將改動(dòng)整體構(gòu)造，效率較低，而且由于鏈碼以每個(gè)區(qū)域?yàn)閱挝淮鎯?chǔ)邊境，相鄰區(qū)域的邊境那么被反復(fù)存儲(chǔ)而產(chǎn)生冗余。302.2游程長度編碼 游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程長度編碼構(gòu)造是逐行將相鄰?fù)档木W(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長度，其目的是緊縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。游程長度編碼構(gòu)造的建立方法是：將柵格矩陣的數(shù)據(jù)序列X1，X2，Xn，映射為相應(yīng)的二元組序列(Ai，Pi，i=1，2,，K，且Kn。其中，A為屬性值，P為游程，K為游程序號(hào)。312.2游

16、程長度編碼游程長度編碼這種數(shù)據(jù)構(gòu)造特別適用于二值圖像數(shù)據(jù)的表示 游程編碼能否緊縮數(shù)據(jù)量，主要決議于柵格數(shù)據(jù)的性質(zhì)，通?？山?jīng)過事先測(cè)試，估算圖層的數(shù)據(jù)冗余度Re：Re=1-Q/mn322.2游程長度編碼Q為圖層內(nèi)相鄰屬性值變化次數(shù)的累加和；m為圖層網(wǎng)格的行數(shù)；n為圖層網(wǎng)格的列數(shù)。當(dāng)Re的值大于1/5的情況下，闡明柵格數(shù)據(jù)的緊縮可獲得明顯的效果。緊縮效果可由緊縮比S =n /K來表征，即緊縮比的值愈大，表示緊縮效果愈顯著。332.3塊式編碼 塊式編碼是將游程長度編碼擴(kuò)展到二維的情況，把多邊形范圍劃分成由像元組成的正方形，然后對(duì)各個(gè)正方形進(jìn)展編碼。塊式編碼的數(shù)據(jù)構(gòu)造由初始位置行號(hào)，列號(hào))和半徑，再加

17、上記錄單元的代碼組成。根據(jù)這一編碼原那么，圖5.15所示多邊形只需17個(gè)單位正方形，9個(gè)4單位的正方形和1個(gè)16單位的正方形就能完好表示，總共要57個(gè)數(shù)據(jù)，其中27對(duì)坐標(biāo)，3個(gè)塊的半徑。342.3塊式編碼塊式編碼的特點(diǎn)：一個(gè)多邊形所能包含的正方形越大，多邊形的邊境越簡單，塊式編碼的效果越好。游程和塊式編碼都對(duì)大的復(fù)雜多邊形效果并不好。塊式編碼在合并、插入、檢查延伸性、計(jì)算面積等操作時(shí)有明顯的優(yōu)越性。352.4差分映射法 差分映射法，就是選擇某一參照值對(duì)有關(guān)柵格的屬性值進(jìn)展求差運(yùn)算，根據(jù)差值得到一個(gè)新的柵格數(shù)據(jù)層。參照值的選擇有多種方式，即分行選取和全區(qū)選取。假設(shè)分行選取，那么可選為該行首列的屬

18、性值，也可以選為該行的屬性平均值；假設(shè)全區(qū)選取，那么可選為首行首列的屬性值，也可以選為全區(qū)的屬性平均值。 362.4差分映射法圖5.16為柵格數(shù)據(jù)例如。圖5.17所示為按分行選取方式，以行首屬性值為參照，對(duì)圖5.16作差分映射后的結(jié)果?？梢钥闯觯?jīng)差分映射處置后，除第一列外，其他柵格的數(shù)據(jù)出現(xiàn)為零、位數(shù)降低或數(shù)字減少。372.4差分映射法表5.1為經(jīng)差分映射處置前后的各柵格屬性記錄所需字節(jié)數(shù)的對(duì)比，可見，所需字節(jié)數(shù)由原來的79減少為 44，減少 44.3%。382.5 四叉樹編碼 四叉樹又稱四元樹或四分樹，是最有效的柵格數(shù)據(jù)緊縮編碼方法之一。四分樹將整個(gè)圖像區(qū)域逐漸分解為一系列方形區(qū)域，且每一

19、個(gè)方形區(qū)域具有單一的屬性。最小區(qū)域?yàn)橐粋€(gè)像元。 393 拓?fù)潢P(guān)系的生成 拓?fù)淇臻g關(guān)系是一種對(duì)空間構(gòu)造進(jìn)展明確定義的數(shù)學(xué)方法，具有拓?fù)潢P(guān)系的矢量數(shù)據(jù)構(gòu)培育是拓?fù)鋽?shù)據(jù)構(gòu)造。它描畫了根本空間目的點(diǎn)、線、面之間的關(guān)聯(lián)、鄰接和包含關(guān)系。矢量數(shù)據(jù)拓?fù)潢P(guān)系在空間數(shù)據(jù)的查詢和分析過程中非常重要，拓?fù)鋽?shù)據(jù)構(gòu)造是地理信息系統(tǒng)分析和運(yùn)用功能所必需的。拓?fù)淇臻g關(guān)系信息是空間分析、輔助決策等的根底，也是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)。403 拓?fù)潢P(guān)系的生成拓?fù)潢P(guān)系自動(dòng)生成算法的普經(jīng)過程為：

20、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)生成。413 拓?fù)潢P(guān)系的生成3.1 根本數(shù)據(jù)構(gòu)造3.2 弧段的預(yù)處置3.3 結(jié)點(diǎn)匹配算法 3.4 建立拓?fù)潢P(guān)系 423.1 根本數(shù)據(jù)構(gòu)造1拓?fù)浣Y(jié)點(diǎn)2拓?fù)浠《渭捌浔硎?拓?fù)涿婕捌浔硎?拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系433.1 根本數(shù)據(jù)構(gòu)造1拓?fù)浣Y(jié)點(diǎn)結(jié)點(diǎn)用來描畫如管線的交點(diǎn)、道路路口等現(xiàn)實(shí)世界的特征對(duì)象，結(jié)點(diǎn)可以用

21、來檢測(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)銜接的弧段集合。443.1 根本數(shù)據(jù)構(gòu)造結(jié)點(diǎn)的數(shù)據(jù)構(gòu)造可以表示為：453.1 根本數(shù)據(jù)構(gòu)造2拓?fù)浠《渭捌浔硎?拓?fù)浠《沃柑幱趦蓚€(gè)結(jié)點(diǎn)之間的點(diǎn)序列串，可以給弧段定義一個(gè)方向，或者定義為數(shù)字化弧段時(shí)從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的采點(diǎn)方向，或者硬性定義一個(gè)方向。 定義方向后弧段開場(chǎng)的結(jié)點(diǎn)就稱為起始結(jié)點(diǎn)，弧段終了的結(jié)點(diǎn)就稱為終了結(jié)點(diǎn)，由起始結(jié)點(diǎn)到終止結(jié)點(diǎn)的方向稱為“起終方向，由終止結(jié)點(diǎn)到起始結(jié)點(diǎn)的方向稱為“終起方向?；《纹鸾K方向左側(cè)的多

22、邊形稱為弧段的左多邊形，弧段起終方向右側(cè)的多邊形稱為弧段的右多邊形。463.1 根本數(shù)據(jù)構(gòu)造假設(shè)弧段的起始結(jié)點(diǎn)或終止結(jié)點(diǎn)只與一條弧段相關(guān)聯(lián)，那么該弧段稱為懸掛弧段，如圖5.19所示的弧段L為懸掛弧。普通可以經(jīng)過標(biāo)識(shí)懸掛弧段來檢測(cè)原始矢量數(shù)據(jù)的質(zhì)量。 弧段普通包括弧段號(hào)、弧段節(jié)點(diǎn)坐標(biāo)串、弧段起始和終止結(jié)點(diǎn)、弧段左右多邊形。 473.1 根本數(shù)據(jù)構(gòu)造483.1 根本數(shù)據(jù)構(gòu)造3拓?fù)涿婕捌浔硎就負(fù)涿媸怯梢粭l或假設(shè)干條弧段首尾相銜接而成的邊線所包含的區(qū)域，內(nèi)部包含有其他拓?fù)涿娴耐負(fù)涿嫫胀ǚQ為復(fù)雜面，被包含的拓?fù)涿娣Q為島，沒有島的拓?fù)涿娣Q為簡單面，如圖5.20所示。對(duì)于拓?fù)涿嬉部梢远x正反方向，普通定義為

23、：當(dāng)沿拓?fù)涿娴倪吘城斑M(jìn)時(shí)，被弧段所包圍的面域一直處于弧段的右側(cè)時(shí)的方向就是正方向；反之，那么是反方向。493.1 根本數(shù)據(jù)構(gòu)造如圖5.21所示，箭頭所指向的方向就是正方向，可以看出對(duì)于拓?fù)涿娴耐膺吘?，順時(shí)針方向是正方向，而對(duì)于內(nèi)邊境逆時(shí)針方向就是正方向。503.1 根本數(shù)據(jù)構(gòu)造多邊形普通包括多邊形號(hào)、中心點(diǎn)坐標(biāo)、多邊形屬性數(shù)據(jù)、多邊形的組成弧段號(hào)、多邊形島的信息。思索到組成弧段的方向和多邊形頂點(diǎn)序列的方向存在能夠的不一致性以及效率問題，可以改為記錄組成多邊形的弧段指針和方向性信息，即弧段方向與多邊形的方向能否一致。對(duì)于島的信息那么經(jīng)過將構(gòu)成多邊形的邊線分塊來處置的方式表達(dá)，比如多邊形包含島嶼，

24、那么可以使多邊形的外邊境成為多邊形的第一部分，島嶼作為多邊形的第二、三、四等部分的方式加以處理。 51523.1 根本數(shù)據(jù)構(gòu)造(4)拓?fù)浣Y(jié)點(diǎn)、弧段和面之間的關(guān)系533.2弧段的預(yù)處置 拓?fù)潢P(guān)系自動(dòng)建立的第一步就是處置弧段，使得弧段不存在自相交和相交景象。1直線段相交的判別方法2自相交弧段處置3弧段相交打斷處置54(1)直線段相交的判別方法直線相交的斷定方法有很多種，這里引見較快的一種算法。設(shè)直線L過點(diǎn)P0 x0，y0和點(diǎn)P1x1，y1，那么直線L的方程可以表示為：將方程化為參數(shù)方式：y=y0+(y1-y0)t, x=x0+(x1-x0)t，其中t0,1。設(shè)有兩條直線L1和L2，它們的參數(shù)方程分

25、別為y=y0+(y1-y0)t，x=x0+(x1-x0)t 和y=y0+(y1-y0)，x=x0+(x1-x0)55(1)直線段相交的判別方法判別兩線段有無交點(diǎn)的關(guān)鍵變?yōu)榕袆et和v；能否符合不等式0t1且0v1。令：假設(shè)dx dy - dy dx = 0，闡明兩線段平行或者重合，沒有交點(diǎn)，或者交點(diǎn)在兩線段的頭或尾上；否那么假設(shè)滿足不等式0t1且0v1，兩線段有交點(diǎn)，交點(diǎn)在兩線段的中間。562自相交弧段處置具有自相交特征的弧段至少具有4個(gè)(結(jié))節(jié)點(diǎn)，由3個(gè)點(diǎn)或2個(gè)點(diǎn)組成的弧段不能夠自相交。依次取出每一條弧段，假設(shè)弧段的(結(jié))節(jié)點(diǎn)個(gè)數(shù)不少于4個(gè)，就利用直線段相交的方法，對(duì)組成弧段的各直線段進(jìn)展判別

26、，假設(shè)相交，將線段斷開為兩條，自相交的弧段能夠不止有一處相交，可以經(jīng)過遞歸的方法將弧段分開。5758593弧段相交打斷處置弧段與弧段相交關(guān)系的判別，可以經(jīng)過取每一條弧段與其他未判別過的一切弧段目的進(jìn)展相交關(guān)系判別而得，從而要進(jìn)展n - 1) + ( n - 2) + 3 + 2 + 1 = nn 1/2次判別。詳細(xì)方法為：取出第一條弧段，與其他n - 1條弧段進(jìn)展相交判別，求得交點(diǎn)后，將交點(diǎn)分別插入第一條弧段和與其相交弧段的對(duì)應(yīng)位置上，并記錄位置。將第一條弧段與一切其他弧段的相交關(guān)系判別終了后，經(jīng)過記錄下的交點(diǎn)位置將第一條弧段分割，然后依次取出下一條弧段進(jìn)展同樣的處置，直到一切弧段處置終了。

27、603弧段相交打斷處置由于GIS的數(shù)據(jù)量大，呵斥了判別的任務(wù)量大、效率低下的弊端，在判別兩條弧段的關(guān)系時(shí)，應(yīng)盡能夠地減少計(jì)算量。減少計(jì)算量方法：分兩步，首先是判別兩條弧段的最小矩形壁包(MBR)能否相交或具有包含關(guān)系，假設(shè)不相交或沒有包含關(guān)系，那么可以斷定兩條弧段是互不相交的；假設(shè)相交或具有包含關(guān)系，那么進(jìn)一步判別第一條弧段的每一條組成線段能否和第二條弧段的MBR相交或被包含，假設(shè)不相交或沒有被包含那么可以判別這一部分線段不會(huì)和第二條弧段相交，否那么可以運(yùn)用這一條線段與組成第二條弧段的各個(gè)線段進(jìn)展相交關(guān)系的斷定來確定交點(diǎn)。613.3結(jié)點(diǎn)匹配算法 結(jié)點(diǎn)匹配就是把一定容差范圍內(nèi)的弧段的結(jié)點(diǎn)合并成為

28、一個(gè)結(jié)點(diǎn)，其坐標(biāo)值可以是取多個(gè)結(jié)點(diǎn)的平均值，或者選中一個(gè)結(jié)點(diǎn)作為一切結(jié)點(diǎn)的坐標(biāo)區(qū)中心的坐標(biāo)。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)的弧段也合并在一同。詳細(xì)的思緒是將一切的結(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)。 633.4建立拓?fù)潢P(guān)系 計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角,并按由小到大排序左轉(zhuǎn)算法島的判別64計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角每個(gè)結(jié)點(diǎn)都關(guān)聯(lián)有假設(shè)干條弧段，結(jié)點(diǎn)或者為弧段

29、的頭結(jié)點(diǎn)或者為弧段的尾結(jié)點(diǎn)，設(shè)結(jié)點(diǎn)為N，那么弧段的方位角定義為：結(jié)點(diǎn)N與弧段上與其最接近結(jié)點(diǎn)V的連線與軸的正向夾角。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)的弧段的方位角后，按角的大小將這些弧排序，構(gòu)成排序的關(guān)聯(lián)弧段集合。662左轉(zhuǎn)算法算法根本思想：從組成多邊形邊境的某一條弧段開場(chǎng)，假設(shè)該弧段的方向角最小或介于同一結(jié)點(diǎn)的其他弧段方向角之間，那么逆時(shí)針方向?qū)ひ捵钚A角偏向所對(duì)應(yīng)的弧段為多邊形的后續(xù)弧段；假設(shè)該弧段與X軸正向夾角為最大，那么從該弧段的同一結(jié)點(diǎn)出發(fā)的

30、其他弧段中，方向角最小的弧段是該多邊形的后續(xù)弧段。672左轉(zhuǎn)算法算法描畫如下：1順序取一個(gè)結(jié)點(diǎn)作為起始結(jié)點(diǎn)，取完為止；取過該結(jié)點(diǎn)的方位角最小的未運(yùn)用過的或僅運(yùn)用過一次，且運(yùn)用過的方向與本次相反的弧段作為起始弧段。2取這條弧段的另一個(gè)結(jié)點(diǎn)，找這個(gè)結(jié)點(diǎn)關(guān)聯(lián)的弧段集合中的本條弧段的下一條弧段，假設(shè)條弧段是最后一條弧段，那么取弧段集合的第一條弧段，作為下一條弧段。682左轉(zhuǎn)算法3判別能否回到起點(diǎn)，假設(shè)是，那么構(gòu)成了一個(gè)多邊形，記錄下它，并且根據(jù)弧段的方向，設(shè)置組成該多邊形的左右多邊形信息；否那么轉(zhuǎn)(2)。4取起始點(diǎn)上開場(chǎng)的，剛剛所構(gòu)成多邊形的最后一條邊作為新的起始弧段， 轉(zhuǎn)(2)；假設(shè)這條弧段曾經(jīng)運(yùn)用

31、過兩次，即構(gòu)成了兩個(gè)多邊形，轉(zhuǎn)(1)。在構(gòu)建多邊形時(shí)要留意懸掛結(jié)點(diǎn)和懸掛線的標(biāo)識(shí)，普通可以采用棧的方式處置。692左轉(zhuǎn)算法1從N1結(jié)點(diǎn)開場(chǎng)，選擇具有最小方位角的弧段N1N2作為起始弧段；轉(zhuǎn)入N2點(diǎn)，根據(jù)左轉(zhuǎn)算法選擇N2N5弧段，轉(zhuǎn)入N5結(jié)點(diǎn)選擇N5N1弧段，構(gòu)成多邊形A1，設(shè)置組成多邊形A1的弧段的左右多邊形信息。2A1的終了弧段為N5N1，選N1作為起始點(diǎn)，N1N5作為起始弧段，根據(jù)左轉(zhuǎn)算法，構(gòu)成多邊形A2，設(shè)置左右多邊形信息。 702左轉(zhuǎn)算法3A2的終了弧段為N4N1，選N1作為起始點(diǎn)，N1N4作為起始弧段，根據(jù) 、左轉(zhuǎn)算法，構(gòu)成多邊形A3，這個(gè)多邊形的方向是逆時(shí)針方向，對(duì)于逆時(shí)針方向的多邊形，不設(shè)置左右多邊形信息。712左轉(zhuǎn)算法4A3的終了弧段為N2N1， N1N2曾經(jīng)被運(yùn)用過兩次，所以選取下一個(gè)結(jié)點(diǎn)N2