【正文】 性值。再依次檢查每四個相鄰的大塊的屬性值，若不同則記錄下來，如果相同則合并，如此直到?jīng)]有可合并的為止。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 82 JJ 0 1 2 3 4 5 6 7 Jb 00 01 10 11 100 101 110 111 II Ib 0 00 000 001 010 011 100 101 110 111 1 01 002 003 012 013 102 103 112 113 2 10 020 021 030 031 120 121 130 131 3 11 022 023 032 033 122 123 132 133 4 100 200 201 210 211 300 301 310 311 5 101 202 203 212 213 302 303 312 313 6 110 220 221 230 231 320 321 330 331 7 111 222 223 232 233 322 323 332 333 0 1 MQ 屬性值 000 0 001 0 002 0 003 0 010 0 011 0 012 0 013 0 020 0 021 0 022 0 023 0 030 0 031 0 032 0 033 0 100 0 101 0 102 0 103 0 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 83 基于十進制的線性四叉樹編碼 基于四進制的編碼存在著一個問題。大多數(shù)語言不支持四進制變量，需要用十進制的 Morton碼 ——MD。因此人們逐漸提出采用十進制的 Morton碼作為線性四叉樹的地址碼。 方法： 設(shè)十進制表示的行、列號在計算機內(nèi)的二進制分別為： 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 84 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 85 然后再將得到的 Md由二進制數(shù)轉(zhuǎn)換為十進制數(shù)即可。用類似的方法，也可以由 Md碼反求柵格單元的行列號（大家在下面可以自己做一做） JJ 0 1 2 3 4 5 6 7 Jb 0 1 10 11 100 101 110 111 II Ib 0 0 0 1 4 5 16 17 20 21 1 1 2 3 6 7 18 19 22 23 2 10 8 9 12 13 24 25 28 29 3 11 10 11 14 15 26 27 30 31 4 100 32 33 36 37 48 49 52 53 5 101 34 35 38 39 50 51 54 55 6 110 40 41 44 45 56 57 60 61 7 111 42 43 46 47 58 59 62 63 Md碼 行號 列號 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 86 例如： II=5 JJ=5 Ib=1 0 1 Jb=1 0 1 Md= （ 1 1 0 0 1 1） 2 Md=51 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 87 在排好的線性表中，依次檢查每四個相鄰 Md碼對應(yīng)的屬性值，如果相同則合并為一個大塊，否則將這四個格網(wǎng)記錄下來，內(nèi)容包括 Md碼、屬性值。再依次檢查每四個相鄰的大塊的屬性值，若不同則記錄下來，如果相同則合并，如此直到?jīng)]有可合并的為止。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 88 二維游程編碼結(jié)構(gòu) 我們注意到，在生成的線性四叉樹結(jié)構(gòu)表中雖然我們對數(shù)據(jù)進行了壓縮，但仍存在前后結(jié)點值相同的情況，因而可以采取進一步的壓縮表達，即將屬性值相同的前后結(jié)點合并成一個值，形成一個線性表列。 其記錄規(guī)則：先記錄入口地址和格網(wǎng)值，依次掃描線性表，若后一格網(wǎng)的值與前一格網(wǎng)值不同，記錄后一格網(wǎng)的地址和格網(wǎng)值，可直接形成線性表。這種記錄方法，非常類似于傳統(tǒng)的一維行程編碼，所以也稱為二維游程編碼 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 89 **具體過程：如下 第一步：確定十進制線性四叉樹的 Morton地址碼 15 14 11 10 11 3 13 12 9 8 10 2 7 6 3 2 01 1 5 4 1 0 00 0 11 3 10 2 01 1 00 0 Jb JJ Ib II 行號 Md碼 列號 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 90 第二步：確定十進制線性四叉樹表 0 1 4 5 2 3 6 7 8 9 12 13 10 11 14 15 屬性值 1 0 11011514131200001110980000765400003210?????????????????????屬性值dM115114013112080400屬性值線性四叉樹表Md14 12 15 13 0 8 4 ??????????第三步：二維行程編碼 11401311200屬性值二維行程編碼表Md14 12 13 0 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 91 該編碼方法的優(yōu)點是：壓縮率高，且解壓方便；陣列中各部分的分辨率可變，即可減少存量，又可精確地表示圖形結(jié)構(gòu)，易于進行圖形操作和運算。 缺點是：具有相同形狀和大小的多邊形可得出完全不同的編碼，不利于形狀的分析和模式識別。 0 1 4 5 2 3 6 7 8 9 12 13 10 11 14 15 14 12 13 0 0 1 4 5 2 3 6 7 8 9 12 13 10 11 14 15 0 1 4 2 3 6 7 11401311200屬性值二維行程編碼表Md07160413021100屬性值二維行程編碼表Md第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 92 第三節(jié) 矢量、柵格轉(zhuǎn)換 矢柵的相互轉(zhuǎn)換，一直是地理信息系統(tǒng)的技術(shù)難題之一。 一、矢量格式向柵格格式轉(zhuǎn)換 矢量數(shù)據(jù)轉(zhuǎn)換為柵格數(shù)據(jù)也 稱柵格化， 其目的在于方便地進行空間分析，因為柵格數(shù)據(jù)對于多要素的重疊操作運算較矢量數(shù)據(jù)容易實現(xiàn)。 習(xí)慣上，在矢量數(shù)據(jù)中，點的坐標用（ X， Y）來表示，而在柵格數(shù)據(jù)中，點的坐標用點所在柵格的行列號（ I， J）來表示。 點的柵格化 將點 P的矢量坐標（ XP， YP）換算成柵格的行、列號（ II， JJ） 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 93 y x o O X0 Y0 P Yp Xp II=INT（（ Y0YP） /d） JJ=INT（（ XPX0） /d） II,JJ d II=INT（（ Y0YP） /d） JJ=INT（（ XPX0） /d） 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 94 線段的柵格化 線段柵格化步驟如下： A、兩端點柵格化 B、求出這兩個端點位置的行數(shù)差和列數(shù)差： 行數(shù)差 = II2 II 列數(shù)差 = JJ2 JJ1 C、計算直線與柵格中心線的交點坐標 若 行數(shù)差 ≥列數(shù)差 ，則逐行求出本行中心線與已知直線的交點坐標 ??????????112121 )/()()( XYYXXYYXYY 中心線第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 95 X1， Y1 X2， Y2 D、將求得的交點柵格化，并將其所在的柵格“賦值”。如圖 II1=INT（（ Y0Y1） /d） JJ1=INT（（ X1X0） /d） II1JJ1 II2=INT（（ Y0Y2） /d） JJ2=INT（（ X2X0） /d） II2JJ2 Y中心線 =Y0II1*d3/2*d Y中心線 =Y0II1*d5/2*d Y中心線 =Y0II1*d7/2*d 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 96 若 行數(shù)差＜列數(shù)差 ，則逐列求出本列中心線與已知直線的交點坐標： ??????????112121 )/()()( YYYXXXXYXX 中心線將求得的交點柵格化，并將其所在的柵格“賦值”。 X1,y1 X2,y2 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 97 這里，之所以要分兩種情況處理，是為了使產(chǎn)生的被 “ 賦值的柵格相互連通，避免出現(xiàn)間斷現(xiàn)象 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 98 具體編程思路如下 開始 直線兩端點柵格化 II1=[（ Y0Y1） /d]； JJ1=[（ X0X1） /d] II2=[（ Y0Y2） /d]； JJ2=[（ X0X2） /d] 計算兩端點的行數(shù)差和列數(shù)差 行數(shù)差 R=II2II1；列數(shù)差 C=JJ2JJ1 Y=Y1+（ XX1） *（ Y2Y1） /（ X2X1） 建立直線方程： R≥C？ Y N 逐行處理 逐列處理 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 99 掃描線開始掃描，當 K=1時，為第一條掃描線 其方程為： 逐列掃描 X=XC=X0+JJ1*d+3/2*d k≤JJ2JJ11？ 結(jié)束 N Y 求當前掃描線的直線方程 ： X=XC 求掃描線與直線的交點坐標： X=XC； Y=Y1+（ XCX1） *（ Y2Y1） /（ X2X1） 對交點進行柵格化： II=[（ Y0Y） /d]； JJ=[（ XX0） /d] 遞進掃描： K=K+1； XC=XC+d 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 100 掃描線開始掃描，當 K=1時，為第一條掃描線 其方程為： 逐行掃描 Y=YC=Y0II1*d3/2*d k≤II2II11？ 結(jié)束 N Y 求當前掃描線的直線方程 ： Y=YC 求掃描線與直線的交點坐標： Y=YC； X=X1+（ YCY1） *（ X2X1） /（ Y2Y1） 對交點進行柵格化： II=[（ Y0Y） /d]； JJ=[（ XX0） /d] 遞進掃描： K=K+1； YC=YCd 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 101 面的柵格化 面域的柵格化可分以下幾步進行： 第一步 將面域的邊界柵格化 用前面介紹的線段柵格化的方法對組成面域的每條邊進行柵格化，如圖： 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 102 R R N R R R N R N N N R N N N L N N R N R N N N N N N N N N N N N L L N L L L L L 第二步 對各個柵格像元加標記 上升像元標上 “ L”，下降像元被標上 “ R”，平坦處或升降變換處的像元被標上 “ N”，為了反映面域的拓撲關(guān)系，可約定，面域的 外廓按順時針 方向組織數(shù)據(jù)， 內(nèi)廓按逆時針 方向組織數(shù)據(jù)。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 103 第三步 配對填充 逐行掃描柵格數(shù)據(jù)，從左到右，將每行中的 L和 R配對，并在每對LR之間填上代表該多邊形面域的特定色度值。在配對時，可 不顧“ N”的存在 ，但在配對填充結(jié)束后，應(yīng)將 剩余的 N或 R（ L）置換成面域灰度值 。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 104 L L L L L N L L N N N N N N N N R N R N N N N N N L N N N R N N N R N R R R N R R 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 105 下面介紹幾種矢量向柵格轉(zhuǎn)換的算法： （多邊形填充） *內(nèi)部點擴散算法 該算法由每個多邊形一個內(nèi)部點（種子點）開始，向其八個方向的鄰點擴散，判斷各個新加入點是否在多邊形邊界上，如果是邊界點，則新加入點不作為種子點，否則把非邊界點的鄰點作為新的種子點與原有種子點一起進行新的擴散運算，并將該種子點賦予多邊形的編號。重復(fù)上述過程，直到所有種子點