【正文】 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 125 具體步驟如下： （ 1）邊界點(diǎn)和節(jié)點(diǎn)的提取 采用 2 2柵格對(duì)圖像全圖掃描 邊界點(diǎn) ：如果窗口內(nèi)四個(gè)柵格有兩個(gè)不同的編號(hào)，則為邊界點(diǎn)；并保留各柵格所有多邊形編號(hào)； 節(jié)點(diǎn) ：如果窗口內(nèi)四個(gè)柵格有二個(gè)以上不同的編號(hào)（或?qū)蔷€上柵格兩兩相同的情況）則標(biāo)識(shí)為節(jié)點(diǎn)（不同邊界弧段的圖形不連通），保留各柵格原編號(hào)信息 。 第六步，將灰度值為“ 3”的置成“ 0”，灰度值為“ 2”的置成“ 1”。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 116 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 2 2 2 1 0 1 2 2 2 1 2 4 4 4 2 0 2 4 4 4 2 2 4 4 4 2 0 2 4 4 4 2 1 2 3 4 3 2 3 4 3 2 1 0 0 2 4 4 4 4 4 2 0 0 0 0 2 4 4 4 4 4 2 0 0 0 0 2 4 4 4 4 4 2 0 0 1 2 3 4 3 2 3 4 3 2 1 2 4 4 4 2 0 2 4 4 4 2 2 4 4 4 2 0 2 4 4 4 2 1 2 2 2 1 0 1 2 2 2 1 0 0 0 0 0 0 0 0 0 00 1 1 1 0 0 1 1 1 00 1 1 1 0 0 1 1 1 00 0 0 1 0 0 0 1 0 0 00 1 1 1 1 1 00 1 1 1 1 1 00 1 1 1 1 1 00 0 0 1 0 0 0 1 0 0 00 1 1 1 0 0 1 1 1 00 1 1 1 0 0 1 1 1 00 0 0 0 0 0 0 0 0 02 2 2 22 4 4 2 2 4 4 22 3 2 2 3 22 3 2 2 3 22 4 4 4 4 22 4 4 4 4 22 3 2 2 3 22 3 2 2 3 22 4 4 2 2 4 4 22 2 2 2第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 117 c、剝皮法 從曲線的邊緣開(kāi)始，每次剝掉等于一個(gè)柵格寬的一層，直到最后留下連通的由單個(gè)柵格點(diǎn)組成的圖形。 （原圖可能是彩色的，或 0~255級(jí)灰度級(jí)） 設(shè)在原柵格數(shù)據(jù)（ G（ I， J） ）的灰度區(qū)間[Lmin， Lmax]，設(shè)定一閾值（ Lt） ∈ [Lmin，Lmax]，二值化后的 B（ I， J） 為： ??? ??LtjiGLtjiGjiB),(,0),(,1),(如果如果＜ 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 113 全彩色 灰度 二值黑白 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 114 B、柵格數(shù)據(jù)的細(xì)化 將要素占有的網(wǎng)格集縮減成為具有單網(wǎng)格寬的網(wǎng)格集的過(guò)程 （使得每一條線只保留代表其軸線的位置的單個(gè)柵格的寬度） 。 **舉一例說(shuō)明： 下行線的左邊為：右多邊形號(hào) 左多邊形號(hào) 上行線的左邊為：左多邊形號(hào) 右多邊形號(hào) 2 2 2 5 5 2 2 5 5 5 5 2 5 5 5 5 2 5 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 33 3 35 5 52 22 22 2 2 2 2 5 5 5 5 22 2 5 5 5 2 22 2 2 2 2 2 2 22 2 2 22 2 2 25 5 5 5 5 5 52 5 5 5 5第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 110 二、柵格向矢量的轉(zhuǎn)換 轉(zhuǎn)換的目的： 將柵格數(shù)據(jù)分析的結(jié)果，通過(guò)矢量繪圖裝置輸出； 為了數(shù)據(jù)壓縮； 將自動(dòng)掃描儀獲取的柵格數(shù)據(jù)加入矢量形式的數(shù)據(jù)庫(kù)。以利于配對(duì)。重復(fù)上述過(guò)程，直到所有種子點(diǎn)填滿多邊形為止。 X1,y1 X2,y2 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 97 這里，之所以要分兩種情況處理，是為了使產(chǎn)生的被 “ 賦值的柵格相互連通，避免出現(xiàn)間斷現(xiàn)象 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 98 具體編程思路如下 開(kāi)始 直線兩端點(diǎn)柵格化 II1=[（ Y0Y1） /d]； JJ1=[（ X0X1） /d] II2=[（ Y0Y2） /d]； JJ2=[（ X0X2） /d] 計(jì)算兩端點(diǎn)的行數(shù)差和列數(shù)差 行數(shù)差 R=II2II1；列數(shù)差 C=JJ2JJ1 Y=Y1+（ XX1） *（ Y2Y1） /（ X2X1） 建立直線方程： R≥C？ Y N 逐行處理 逐列處理 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 99 掃描線開(kāi)始掃描，當(dāng) K=1時(shí)，為第一條掃描線 其方程為： 逐列掃描 X=XC=X0+JJ1*d+3/2*d k≤JJ2JJ11？ 結(jié)束 N Y 求當(dāng)前掃描線的直線方程 ： X=XC 求掃描線與直線的交點(diǎn)坐標(biāo)： X=XC； Y=Y1+（ XCX1） *（ Y2Y1） /（ X2X1） 對(duì)交點(diǎn)進(jìn)行柵格化： II=[（ Y0Y） /d]； JJ=[（ XX0） /d] 遞進(jìn)掃描： K=K+1； XC=XC+d 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 100 掃描線開(kāi)始掃描，當(dāng) K=1時(shí)，為第一條掃描線 其方程為： 逐行掃描 Y=YC=Y0II1*d3/2*d k≤II2II11？ 結(jié)束 N Y 求當(dāng)前掃描線的直線方程 ： Y=YC 求掃描線與直線的交點(diǎn)坐標(biāo)： Y=YC； X=X1+（ YCY1） *（ X2X1） /（ Y2Y1） 對(duì)交點(diǎn)進(jìn)行柵格化： II=[（ Y0Y） /d]； JJ=[（ XX0） /d] 遞進(jìn)掃描： K=K+1； YC=YCd 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 101 面的柵格化 面域的柵格化可分以下幾步進(jìn)行： 第一步 將面域的邊界柵格化 用前面介紹的線段柵格化的方法對(duì)組成面域的每條邊進(jìn)行柵格化，如圖： 第二章 地 圖 數(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 第二步 對(duì)各個(gè)柵格像元加標(biāo)記 上升像元標(biāo)上 “ L”，下降像元被標(biāo)上 “ R”，平坦處或升降變換處的像元被標(biāo)上 “ N”，為了反映面域的拓?fù)潢P(guān)系，可約定，面域的 外廓按順時(shí)針 方向組織數(shù)據(jù)， 內(nèi)廓按逆時(shí)針 方向組織數(shù)據(jù)。 一、矢量格式向柵格格式轉(zhuǎn)換 矢量數(shù)據(jù)轉(zhuǎn)換為柵格數(shù)據(jù)也 稱柵格化， 其目的在于方便地進(jìn)行空間分析，因?yàn)闁鸥駭?shù)據(jù)對(duì)于多要素的重疊操作運(yùn)算較矢量數(shù)據(jù)容易實(shí)現(xiàn)。 其記錄規(guī)則：先記錄入口地址和格網(wǎng)值，依次掃描線性表，若后一格網(wǎng)的值與前一格網(wǎng)值不同，記錄后一格網(wǎng)的地址和格網(wǎng)值，可直接形成線性表。 方法： 設(shè)十進(jìn)制表示的行、列號(hào)在計(jì)算機(jī)內(nèi)的二進(jìn)制分別為： 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 84 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 85 然后再將得到的 Md由二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)即可。再依次檢查每四個(gè)相鄰的大塊的屬性值，若不同則記錄下來(lái)，如果相同則合并，如此直到?jīng)]有可合并的為止。最常用的地址碼是四進(jìn)制或十進(jìn)制的Morton碼。 這就需要大量的存儲(chǔ)空間，所以在數(shù)據(jù)壓縮方面常規(guī)四叉樹(shù)結(jié)構(gòu)作用不大，但在數(shù)據(jù)索引和圖幅索引等方面得到了很好的應(yīng)用。 常規(guī)四叉樹(shù)也可以采用“ bottomup”的方式，對(duì)柵格數(shù)據(jù)按一定順序進(jìn)行檢測(cè)，如果每相鄰四個(gè)格網(wǎng)值相同，則進(jìn)行合并，逐次往上遞歸。這種思路可用四叉樹(shù)編碼來(lái)實(shí)現(xiàn)。 CCCBBBCCBBBBCCBBBBCCAAAACAAAAAAAAAAA654321654321第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 72 ③ 塊碼 塊式編碼是將游程編碼擴(kuò)大到二維的情況，把多邊形范圍分成由像元組成的正方形，然后對(duì)各個(gè)正方形進(jìn)行編碼。單位矢量的長(zhǎng)度默認(rèn)為一個(gè)柵格單元，每個(gè)后續(xù)點(diǎn)可能位于其前繼點(diǎn)的 8個(gè)基本方向之一。 通常在文件頭中還存有該柵格數(shù)據(jù)的行數(shù)和列數(shù)。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 56 柵格數(shù)據(jù)的表示方法 點(diǎn) ——用一個(gè)柵格表示； 線 ——用沿其走向的一組相鄰柵格表示 面 ——用其所覆蓋的相鄰柵格的集合表示 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 57 柵格數(shù)據(jù)的一般組織方法 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 58 有關(guān)相鄰柵格單元 四方向相鄰 八方向相鄰 一般講，四方向相鄰的柵格圖形線畫(huà)顯得粗壯，但階梯（鋸齒）明顯；而八方向相鄰的柵格圖形顯得平滑圓潤(rùn)。各像元內(nèi)其屬性是均一的。這樣具有相同分類(lèi)碼的目標(biāo)組成類(lèi)型；多個(gè)相關(guān)聯(lián)的類(lèi)型構(gòu)成專(zhuān)題層；若干個(gè)專(zhuān)題層構(gòu)成圖幅；全部數(shù)據(jù)組成數(shù)據(jù)庫(kù)。如果節(jié)點(diǎn)弧段排序?yàn)轫槙r(shí)針，則算法中用 PL(A)代替 PR(A)，用 PR(A)代替 PL(A)，生成的多邊形弧段是順時(shí)針排列的。)，設(shè)置PR(A39。作為多邊形的第二條弧段。如果都非空，轉(zhuǎn)到第一步，當(dāng)所有弧段處理完畢后，算法結(jié)束； （ 3）如果左多邊形為空，則創(chuàng)建一個(gè)新的多邊形 P，多邊形的第一條弧段為當(dāng)前弧段，并設(shè)置 PL(A)=P，設(shè)置搜尋起始節(jié)點(diǎn)為 Ns(A)，搜尋當(dāng)前節(jié)點(diǎn)為NE(A)。 圖 24中共有 4個(gè)節(jié)點(diǎn)，以 A、 B、 C、 D表示； 6條弧段，用數(shù)字表示；以及 I、 II、 III三個(gè)多邊形（圖 24a）。如下表： 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 41 地物屬性表： 地物標(biāo)志碼 +所屬地物類(lèi)碼 +具體屬性等。 ③屬性信息：由屬性特征表來(lái)體現(xiàn)。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 37 B、結(jié)點(diǎn)連接編輯 例如，需要對(duì)結(jié)點(diǎn) N1進(jìn)行編輯，其過(guò)程相似。這種拓?fù)渚庉?，不但保證數(shù)字化原始數(shù)據(jù)的自動(dòng)查錯(cuò)，而且可以自動(dòng)形成封閉的多邊形邊界，為由各個(gè)單獨(dú)存儲(chǔ)的弧段組成所需要的各類(lèi)多邊形及建立空間數(shù)據(jù)庫(kù)奠定基礎(chǔ)。目前的計(jì)算機(jī)地圖制圖系統(tǒng)中，主要表示的是拓?fù)湓刂g的基本的拓?fù)潢P(guān)系，表示方法多種多樣。 ①拓?fù)湓?—— 點(diǎn) （節(jié)點(diǎn)）、 線 （鏈、弧、邊）、 面 （多邊形） ②基本拓?fù)潢P(guān)系 —— 鄰接、關(guān)聯(lián)、包含 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 28 鄰接 —— 相同拓?fù)湓刂g的關(guān)系 如節(jié)點(diǎn)與節(jié)點(diǎn)、鏈與鏈、面與面等?？梢?jiàn)拓?fù)潢P(guān)系能從本質(zhì)上描述地圖要素間的空間關(guān)系。 ② 點(diǎn)位字典法 以公用點(diǎn)位字典為基礎(chǔ)建立一些系統(tǒng)，這克服了獨(dú)立實(shí)體編碼的某些局限性 。每個(gè)實(shí)體的坐標(biāo)都獨(dú)立存儲(chǔ)，毫不顧及相鄰的多邊形或線或點(diǎn)狀地物。 有點(diǎn)、線、面三種基本的矢量數(shù)據(jù)結(jié)構(gòu)形式。如果相交，則應(yīng)以交點(diǎn)為界將一維矢量分成幾個(gè)一維矢量。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 16 第二節(jié) 地圖的數(shù)據(jù)結(jié)構(gòu) 地圖的數(shù)據(jù)結(jié)構(gòu) 主要指地圖數(shù)據(jù)中 空間數(shù)據(jù) 的結(jié)構(gòu)， 是指幾何數(shù)據(jù)以什么形式在計(jì)算機(jī)中存儲(chǔ)和處理。有時(shí)也把描述時(shí)間特征的數(shù)據(jù)納入該類(lèi)。這類(lèi)數(shù)據(jù)表達(dá)了各類(lèi)地理實(shí)體空間位置之間的相互關(guān)系，如空間數(shù)據(jù)的相鄰、關(guān)聯(lián)、包含等。描述面狀特征的 空間數(shù)據(jù)是一封閉的面坐標(biāo)串 (或柵格像元集合 )，通常稱之為多邊形。這里的 “ 線 ” (有時(shí)也稱 “ 弧 ” )也是一個(gè)相對(duì)的抽象概念。這里， “ 點(diǎn) ” 是一個(gè)相對(duì)的抽象概念，即從較大的空間