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

1、1空間數(shù)據(jù)組織算法 地理信息系統(tǒng)算法基礎第六章2本講內容v1 矢量數(shù)據(jù)的壓縮v2 柵格數(shù)據(jù)的壓縮v3 拓撲關系的生成 31 矢量數(shù)據(jù)的壓縮v矢量數(shù)據(jù)的壓縮包括兩個方面的內容：矢量數(shù)據(jù)的壓縮包括兩個方面的內容：v一是在不擾亂拓撲關系的前提下，對采樣點數(shù)據(jù)進行合理的一是在不擾亂拓撲關系的前提下，對采樣點數(shù)據(jù)進行合理的抽??；抽稀；v二是對矢量坐標數(shù)據(jù)重新進行編碼，以減少所需要的存儲空二是對矢量坐標數(shù)據(jù)重新進行編碼，以減少所需要的存儲空間。間。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 間隔取點法間隔取點法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 間隔取點法原理原理：每隔每隔K K個點取一點，或舍個點取一點，或舍去那些離已選點比規(guī)定距離更去那些離已選點比規(guī)定距離更近的點，但首、末點一定要保近的點，但首、末點一定要保留，如圖留，如圖5.15.1所示。所示。 優(yōu)缺點優(yōu)缺點：可大量壓縮數(shù)字化儀可大量壓縮數(shù)字化儀用連續(xù)方法獲取的點列中的點、用連續(xù)方法獲取的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、因此在處理公共節(jié)點的取均為多邊形的公共邊），因此在處理公共節(jié)點的取舍時要慎重，應該對此加以限制。舍時要慎重，應該對此加以限制。242 柵格數(shù)據(jù)的壓縮v2.1 2.1 鏈式編碼鏈式編碼v2.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個基本方式：個基本方式：基于像元、基于層和基基于像元、基于層和基于面域。于面域。v共同點：對像元坐標和屬性的記錄。共同點：對像元坐標和屬性的記錄。v因此基于柵格的空間數(shù)據(jù)壓縮的因此基于柵格的空間數(shù)據(jù)壓

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

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

25、的單位矢量鏈?；痉较蚩啥x為義為: :東東=0=0，東南，東南=1=1，南，南=2=2，西南，西南=3=3，西，西=4=4，西北，西北=5=5，北，北= 6= 6，東北東北=7=7，8 8個基本方向個基本方向。282.1 鏈式編碼如果確定原點為像元如果確定原點為像元（1010，1)1)，則該多邊形，則該多邊形邊界按順時針方向的鏈邊界按順時針方向的鏈式編碼式編碼 ( (圖圖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 鏈式編碼v鏈式編碼的優(yōu)點鏈式編碼的優(yōu)點：鏈式編碼對多邊形的表示具有很強的數(shù)據(jù)：鏈式編碼對多邊形的表示具有很強的數(shù)據(jù)壓縮能力，且具有一定的運算功能，如面積和周長計算等，壓縮能力，且具有一定的運算功能，如面積和周長計算等，探測邊界急彎和凹進部分等都比較容易；探測邊界急彎和凹進部分等都比較容易；v鏈式編碼的缺點鏈式編碼的缺點是對疊置運算如組合、相交等則很難實施，是對疊置運算如組合、相交等則很難實施，對局部修改將改變整體結構，效率較低，而且由于鏈碼以每對局部修改將改變

27、整體結構，效率較低，而且由于鏈碼以每個區(qū)域為單位存儲邊界，相鄰區(qū)域的邊界則被重復存儲而產個區(qū)域為單位存儲邊界，相鄰區(qū)域的邊界則被重復存儲而產生冗余。生冗余。302.2游程長度編碼 v游程指相鄰同值網(wǎng)格的數(shù)量，游程長度編碼結構是逐游程指相鄰同值網(wǎng)格的數(shù)量，游程長度編碼結構是逐行行將相將相鄰同值的網(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長鄰同值的網(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。v游程長度編碼結構的建立方法游程長度編碼結構的建立方法是：將柵格矩陣的數(shù)據(jù)序列是：將柵格矩陣的數(shù)據(jù)序列X X1 1，X

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

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

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

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

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

33、結果。可以看作差分映射后的結果。可以看出，經(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ù)的對比，可見，所需字節(jié)數(shù)由原來的的對比，可見，所需字節(jié)數(shù)由原來的7979減少為減少為 4444，減少，減少 44.3%44.3%。382.5 四叉樹編碼 v四叉樹又稱四元樹或四分樹，是四叉樹又稱四元樹或四分樹，是最有效最有效的柵格數(shù)據(jù)壓縮編碼的柵格數(shù)據(jù)壓縮編碼方法方法之一之一

34、。四分樹將整個圖像區(qū)域逐步分解為一系列方形區(qū)。四分樹將整個圖像區(qū)域逐步分解為一系列方形區(qū)域，且每一個方形區(qū)域具有單一的屬性。最小區(qū)域為一個像域，且每一個方形區(qū)域具有單一的屬性。最小區(qū)域為一個像元。元。 393 拓撲關系的生成 v拓撲空間關系是一種對空間結構進行明確定義的數(shù)學方法，拓撲空間關系是一種對空間結構進行明確定義的數(shù)學方法，具有拓撲關系的矢量數(shù)據(jù)結構就是拓撲數(shù)據(jù)結構。具有拓撲關系的矢量數(shù)據(jù)結構就是拓撲數(shù)據(jù)結構。v它描述了基本空間目標點、線、面之間的關聯(lián)、鄰接和包含它描述了基本空間目標點、線、面之間的關聯(lián)、鄰接和包含關系。關系。v矢量數(shù)據(jù)拓撲關系在空間數(shù)據(jù)的查詢和分析過程中非常重要，矢量數(shù)

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

36、v拓撲關系自動生成算法的一般過程為：拓撲關系自動生成算法的一般過程為：（1 1）弧段處理：弧段處理：使整幅圖形中的所有弧段，除在端點處相交使整幅圖形中的所有弧段，除在端點處相交外，沒有其他交點，即沒有相交或自相交的弧段。外，沒有其他交點，即沒有相交或自相交的弧段。（2 2）結點匹配：結點匹配：建立結點、弧段關系。建立結點、弧段關系。（3 3）建立多邊形：建立多邊形：以左轉算法或右轉算法跟蹤，生成多邊形，以左轉算法或右轉算法跟蹤，生成多邊形，建立多邊形與弧段的拓撲關系。建立多邊形與弧段的拓撲關系。（4 4）建立多邊形與多邊形的拓撲關系：建立多邊形與多邊形的拓撲關系：調整弧段的左右多邊調整弧段的左

37、右多邊形標識號。多邊形標識號。多邊 形內部標識號的自動生成。形內部標識號的自動生成。413 拓撲關系的生成v3.1 3.1 基本數(shù)據(jù)結構基本數(shù)據(jù)結構v3.2 3.2 弧段的預處理弧段的預處理v3.3 3.3 結點匹配算法結點匹配算法 v3.4 3.4 建立拓撲關系建立拓撲關系 423.1 基本數(shù)據(jù)結構v（1 1）拓撲結點）拓撲結點v（2 2）拓撲弧段及其表示）拓撲弧段及其表示v（3 3）拓撲面及其表示）拓撲面及其表示v（4 4）拓撲結點、弧段和面之間的關系）拓撲結點、弧段和面之間的關系433.1 基本數(shù)據(jù)結構v（1 1）拓撲結點）拓撲結點v結點用來描述如管線的交點、道路路口等現(xiàn)實世界的特征對結

38、點用來描述如管線的交點、道路路口等現(xiàn)實世界的特征對象，結點可以用來檢測弧段與弧段的連接關系和多邊形特征象，結點可以用來檢測弧段與弧段的連接關系和多邊形特征是否能正確地完成。只與一條弧段相連接的起點或終點叫做是否能正確地完成。只與一條弧段相連接的起點或終點叫做懸掛結點懸掛結點，如圖，如圖5.185.18所示的所示的P P點就是懸掛結點。點就是懸掛結點。v結點一般包括結點號、結點坐標、與該結點連接的弧段集合。結點一般包括結點號、結點坐標、與該結點連接的弧段集合。443.1 基本數(shù)據(jù)結構v結點的數(shù)據(jù)結構可以表示為：結點的數(shù)據(jù)結構可以表示為：453.1 基本數(shù)據(jù)結構v（2 2）拓撲弧段及其表示）拓撲弧

39、段及其表示 拓撲弧段指處于兩個結點之間的點序列串拓撲弧段指處于兩個結點之間的點序列串，可以給弧，可以給弧段定義一個方向，或者定義為數(shù)字化弧段時從一個結點到另一段定義一個方向，或者定義為數(shù)字化弧段時從一個結點到另一個結點的采點方向，或者硬性定義一個方向。個結點的采點方向，或者硬性定義一個方向。 定義方向后弧段開始的結點就稱為定義方向后弧段開始的結點就稱為起始結點起始結點，弧段結，弧段結束的結點就稱為束的結點就稱為結束結點結束結點，由起始結點到終止結點的方向稱為，由起始結點到終止結點的方向稱為“起終方向起終方向”，由終止結點到起始結點的方向稱為，由終止結點到起始結點的方向稱為“終起方終起方向向”。

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

41、起始和終止結點、弧段左右多邊形。終止結點、弧段左右多邊形。 473.1 基本數(shù)據(jù)結構483.1 基本數(shù)據(jù)結構v（3 3）拓撲面及其表示）拓撲面及其表示v拓撲面是由一條或若干條弧段首尾相連接而成的邊線所包含拓撲面是由一條或若干條弧段首尾相連接而成的邊線所包含的區(qū)域的區(qū)域，內部包含有其他拓撲面的拓撲面一般稱為，內部包含有其他拓撲面的拓撲面一般稱為復雜面復雜面，被包含的拓撲面稱為被包含的拓撲面稱為島島，沒有島的拓撲面稱為，沒有島的拓撲面稱為簡單面簡單面，如圖，如圖5.205.20所示。對于拓撲面也可以定義所示。對于拓撲面也可以定義正反方向正反方向，一般定義為：，一般定義為：當沿拓撲面的邊界前進時，被

42、弧段所包圍的面域始終處于弧當沿拓撲面的邊界前進時，被弧段所包圍的面域始終處于弧段的右側時的方向就是正方向；反之，則是反方向。段的右側時的方向就是正方向；反之，則是反方向。493.1 基本數(shù)據(jù)結構v如圖如圖5.215.21所示，箭頭所指向的方向就是正方向，可以看出對所示，箭頭所指向的方向就是正方向，可以看出對于拓撲面的外邊界，順時針方向是正方向，而對于內邊界逆于拓撲面的外邊界，順時針方向是正方向，而對于內邊界逆時針方向就是正方向。時針方向就是正方向。503.1 基本數(shù)據(jù)結構v多邊形一般包括多邊形一般包括多邊形號、中心點坐標、多邊形屬性數(shù)據(jù)、多邊形號、中心點坐標、多邊形屬性數(shù)據(jù)、多邊形的組成弧段號

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

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

45、線相交的判定方法有很多種，這里介紹較快的一種算法。v設直線設直線L L過點過點P P0 0（x x0 0，y y0 0）和點）和點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設有兩條直線設有兩條直線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判斷兩線段有無交點的關鍵變?yōu)榕袛嗯袛鄡删€段有無交點的關鍵變?yōu)榕袛鄑 t和和v v；是否符合不等式；是否符合不等式00t t11且且00v v11。令：。令：如果如果dxdx dydy - - dydy dxdx = 0= 0，說明兩線段平行或者重，說明兩線段平行或者重合，沒有交點，或

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

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

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

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

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

52、個結點作為所有結點的坐標區(qū)中心的坐標。結點作為所有結點的坐標區(qū)中心的坐標。623.3結點匹配算法v每條弧段對應著兩個結點，每個結點在合并前對應著一條弧每條弧段對應著兩個結點，每個結點在合并前對應著一條弧段，在合并結點的過程中，需要將結點對應的弧段也合并在段，在合并結點的過程中，需要將結點對應的弧段也合并在一起。一起。v具體的思路具體的思路是將所有的結點加入結點集合，從結點集合中取是將所有的結點加入結點集合，從結點集合中取出一個結點作為中心點，從余下的結點中找出容差范圍內的出一個結點作為中心點，從余下的結點中找出容差范圍內的其他結點，將這些結點所對應的弧段加入中心結點的弧段集其他結點，將這些結點

53、所對應的弧段加入中心結點的弧段集合中，同時將弧段的對應的結點變?yōu)橹行慕Y點，并修改弧段合中，同時將弧段的對應的結點變?yōu)橹行慕Y點，并修改弧段的相應坐標。的相應坐標。 633.4建立拓撲關系 v（）計算結點關聯(lián)弧段的方位角（）計算結點關聯(lián)弧段的方位角, ,并按由小到大排序并按由小到大排序v（）左轉算法（）左轉算法v（）島的判斷（）島的判斷64（）計算結點關聯(lián)弧段的方位角v每個結點都關聯(lián)有若干條弧段，結點或者為弧段的頭結點或每個結點都關聯(lián)有若干條弧段，結點或者為弧段的頭結點或者為弧段的尾結點，設結點為者為弧段的尾結點，設結點為N N，則弧段的，則弧段的方位角方位角定義為：定義為：結點結點N N與弧段上

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

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

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

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

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

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