【正文】 內(nèi)部 采用射線算法 ， 要注意的是：射線與多邊形邊界相交時(shí) ， 有一些特殊情況會(huì)影響交點(diǎn)的個(gè)數(shù) ， 必須予以排除 。 ? 以柵格行列為參考坐標(biāo)軸，以多邊形邊界上某一點(diǎn)為起始點(diǎn)順時(shí)針方向搜索邊界。 矢量化過程中 ， 達(dá)到某個(gè)單元值與周圍均不同 ，則該單元代表一個(gè)點(diǎn) 。 （ ） 兩種數(shù)據(jù)結(jié)構(gòu)的互換 柵格向矢量轉(zhuǎn)換 ??細(xì)化 也稱為柵格數(shù)據(jù)的軸化，就是將占用多個(gè)柵格寬度的 圖形要素縮減為只有單個(gè)柵格寬度的圖形要素的過程。 （ 2）骨 架 法 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 1 0 0 2 4 1 0 3 1 0 0 0 0 0 0 0 4 0 3 3 4 4 1 2 2 0 0 0 0 0 0 0 0 0 0 4 2 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 ? 跟 蹤 ? 細(xì)化后的二值圖像形成了骨架圖，跟蹤就 是把骨架轉(zhuǎn)換為矢量圖形的坐標(biāo)序列。 具體步驟： ? 邊界點(diǎn)和結(jié)點(diǎn)的提取。 ⑶ 多余點(diǎn)的去除： 某一弧段上連續(xù)三點(diǎn)，若滿足直線方程，則中間一點(diǎn)予以去除。 （ ）柵格 矢量數(shù)據(jù)一體化結(jié)構(gòu) 由于柵格數(shù)據(jù)結(jié)構(gòu)的精度較低，需利用細(xì)分格網(wǎng)的方法，來提高點(diǎn)、線和面狀目標(biāo)邊界線的數(shù)據(jù)表達(dá)精度。 點(diǎn)狀地物和結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu) （ ）柵格 矢量數(shù)據(jù)一體化結(jié)構(gòu) — 設(shè)計(jì) 點(diǎn)標(biāo)識(shí)號(hào) M1 M2 高程 Z … … … … … … … … 10025 43 4082 432 10026 105 7725 463 … … … … … … … … 線狀地物的數(shù)據(jù)結(jié)構(gòu) （ ）柵格 矢量數(shù)據(jù)一體化結(jié)構(gòu) — 設(shè)計(jì) 線狀地物有形狀沒有面積，和點(diǎn)狀地物一樣不必用一個(gè)完全的覆蓋層分解四叉樹，而只要 用一串?dāng)?shù)據(jù)表達(dá)每個(gè)線狀地物的路徑 即可。 （ ）柵格 矢量數(shù)據(jù)一體化結(jié)構(gòu) — 設(shè)計(jì) （ ）柵格 矢量數(shù)據(jù)一體化結(jié)構(gòu) — 設(shè)計(jì) （ ）柵格 矢量數(shù)據(jù)一體化結(jié)構(gòu) — 設(shè)計(jì) 帶指針的二維行程表 弧段文件 面文件 （ ）柵格 矢量數(shù)據(jù)一體化結(jié)構(gòu) — 設(shè)計(jì) 這種數(shù)據(jù)結(jié)構(gòu)是 面向地物 的，具有 矢量 的特點(diǎn)。 。 其中邊界由弧段組成，它同 樣引用弧段結(jié)構(gòu)表的弧段信息。 這種結(jié)構(gòu) 簡單靈活 ，便于點(diǎn)的插入和刪除，還能處理一個(gè)柵格內(nèi)包含多個(gè)點(diǎn)狀目標(biāo)的情況。 (2)對(duì)線狀目標(biāo) ，它有形狀，但沒有面積，在計(jì)算機(jī)內(nèi)部需用一組元 子來填滿整個(gè)路徑，并表示該弧段相關(guān)的拓?fù)湫畔ⅰ? 3)若四個(gè)柵格有 二個(gè)不同的編號(hào)且對(duì)角線上編號(hào)完全相同 為結(jié)點(diǎn)。 （ ） 兩種數(shù)據(jù)結(jié)構(gòu)的互換 柵格向矢量轉(zhuǎn)換 ① 基本步驟： 多邊形 (面實(shí)體 )的柵格數(shù)據(jù)向矢量數(shù)據(jù)的轉(zhuǎn)換實(shí)質(zhì)上就是將空間具有相同屬性代碼的柵格象元集合表示為以邊界弧段以及邊界的拓?fù)湫畔⑺_定的多邊形區(qū)域 。 V值是該柵格與北、東和北東三個(gè)相鄰柵格像元值之和，即 ? 在 V值圖上保留最大 V值的柵格，刪去其他柵格，但必須保證連通。設(shè)閾值為 ，則二值化后的像元灰度值為： ? 式中 f(i,j)為原像元灰度。當(dāng)邊界平行柵格行行走時(shí) ,不做運(yùn)算 。 P Q R a b c d g f e Y X （ ） 兩種數(shù)據(jù)結(jié)構(gòu)的互換 矢量向柵格轉(zhuǎn)換 ④ 面的填充 — 邊界 代數(shù)算法 [任伏虎 ] ⑴ 單個(gè)多邊形 ? 初始化柵格陣列，所有單元賦值為 0。 常用算法： 法 （ ） 兩種數(shù)據(jù)結(jié)構(gòu)的互換 矢量向柵格轉(zhuǎn)換 ④ 面的填充 — 內(nèi)部點(diǎn)擴(kuò)散算法 該算法由每個(gè)多邊形一個(gè)內(nèi)部點(diǎn) （ 種子點(diǎn) ）開始 ， 向其八個(gè)方向的鄰點(diǎn)擴(kuò)散 ， 判斷各個(gè)新加入點(diǎn)是否在多邊形邊界上 ， 如果是邊界上 ，則該新加入點(diǎn)不作為種子點(diǎn) ， 否則把非邊界點(diǎn)的鄰點(diǎn)作為新的種子點(diǎn)與原有種子點(diǎn)一起進(jìn)行新的擴(kuò)散運(yùn)算 ， 并將該種子點(diǎn)賦以該多邊形的編號(hào) 。 ? 確定直線經(jīng)過的中間柵格列值 。 （ ） 兩種數(shù)據(jù)結(jié)構(gòu)的互換 矢量向柵格轉(zhuǎn)換 ① 確定柵格單元的大小 矢量數(shù)據(jù)向柵格數(shù)據(jù)轉(zhuǎn)換時(shí)，首先必須確定柵格元素的大小，即分辨率。 X4,y4 C X4,y4。 弧段文件 ：弧記錄組成（記錄弧的起止點(diǎn)號(hào)和左右多邊形號(hào)）。 ? 缺點(diǎn) ： ? 運(yùn)算繁瑣。 邊界坐標(biāo)數(shù)據(jù)與多邊形單元實(shí)體一一對(duì)應(yīng)，各個(gè)多邊形的邊界都有單獨(dú)編碼和數(shù)字化。 二、矢量數(shù)據(jù)結(jié)構(gòu) （三）編碼內(nèi)容 （ ）點(diǎn)實(shí)體 二、矢量數(shù)據(jù)結(jié)構(gòu) （三）編碼內(nèi)容 （ ）線實(shí)體 ? 由直線元素構(gòu)成的各種線性要素。 5) 與非樹表示法比較 ， 四叉樹表示法的缺點(diǎn)在于轉(zhuǎn)換的不穩(wěn)定性或叫 滑動(dòng)變異 例如 ， 兩個(gè)圖像的差異僅由于平移 ， 就會(huì)構(gòu)成極為不同的四叉樹 ， 因而很難根據(jù)四叉樹來判斷這兩個(gè)圖像是否全同 ， 故不利于做形狀分析和模式識(shí)別 ， A 0 A 1 A 4 A 5 A 2 B 3 B 6 B 7 A 8 A 9 B 12 B 13 A 10 A 11 B 14 B 15 A A A A A B B B A A B B A A B B 6) 一個(gè) 物體 的圖像 在構(gòu)成四叉樹時(shí)會(huì)被分割到若干個(gè)象限中，使它失去了內(nèi)在的相關(guān)性 。然后再歸并更高一層父結(jié)點(diǎn)，如此循環(huán)，直到不能歸并為止。經(jīng)過一次檢測(cè)后，再檢測(cè)上層相鄰四個(gè)塊編碼的屬性值，如相同再合并。 2)線性四叉樹及編碼 以四叉樹的方式組織數(shù)據(jù)，但不以四叉樹方式存儲(chǔ)數(shù)據(jù)。 最后得到一顆四分叉的倒向樹。 ? 缺點(diǎn)： 適合類型區(qū)面積較大的專題圖、遙感影像分類集中的分類圖，不適合類型連續(xù)變化或類型區(qū)分散的分類圖。 但難于實(shí)現(xiàn)疊置運(yùn)算，不便于合并插入操作。 （ 1）直接?xùn)鸥窬幋a （ 2）費(fèi)爾曼鏈碼 （邊界編碼） ? 將線狀地物或區(qū)域邊界表示為：由某一起始點(diǎn)和某些基本方向上的單位矢量鏈組成。 中心點(diǎn)法常用于具有連續(xù)分布特性的地理要素，如降雨量分布、人口密度圖等 。 遙感影像數(shù)據(jù)， 對(duì)地面景象的輻射和反射能量的掃描抽樣，并按不同的光譜段量化后，以數(shù)字形式記錄下來的象素值序列。 ?屬性特征顯性表示。 一、基于規(guī)則格網(wǎng)空間數(shù)據(jù)模型的數(shù)據(jù) 結(jié)構(gòu) (柵格數(shù)據(jù)結(jié)構(gòu) ) （一）概念 柵格數(shù)據(jù)結(jié)構(gòu)是最簡單最直觀的空間數(shù)據(jù)結(jié)構(gòu)，又稱網(wǎng)格結(jié)構(gòu)或像元結(jié)構(gòu)。 矢量數(shù)據(jù)結(jié)構(gòu)：主導(dǎo)了 CAD系統(tǒng)和有著強(qiáng)大制圖功能的 GIS。 大小由行列號(hào)決定， 劃分程度 決定點(diǎn)大小、點(diǎn)數(shù)多少、 表達(dá)內(nèi)容的復(fù)雜程度及精度高低。 由矢量數(shù)據(jù)轉(zhuǎn)換而來 。 每個(gè)柵格元素只能取一個(gè)值，實(shí)際上一個(gè)柵格可能對(duì)應(yīng)于實(shí)體中幾種不同屬性值，存在柵格數(shù)據(jù)取值問題 A B C D （四）柵格結(jié)構(gòu)的建立 三）柵格屬性值的確定 中心點(diǎn)法 用處于 柵格中心 處的地物類型或現(xiàn)象特性決定柵格代碼。 2 2 2 1 1 7 7 7 2 2 2 2 1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 7 7 7 7 7 4 4 4 4 7 7 7 7 （ 1）直接?xùn)鸥窬幋a (1,1,2),(1,2,2),(1,3,2), (1,4,1),(1,5,1),(1,6,7), (1,7,7),(1,8,7), (2,1,2),(2,2,2),(2,3,2), …… 如果行列號(hào)記錄在專門文件中，則只記錄屬性值： （ 2,2,2,1,1,7,7,7,2,2,2,2,1,7,7,7?? ） 優(yōu)點(diǎn)： 1易于實(shí)現(xiàn)用循環(huán)語句編程，實(shí)現(xiàn)快速運(yùn)算 2易于實(shí)現(xiàn)空間屬性的分解與分類，易于實(shí)現(xiàn)空間分析中疊加等操作 缺點(diǎn)： 數(shù)據(jù)存儲(chǔ)量大 基本要素包括：行，列，屬性值（ N， M， Xij） 其中行、列值隱性，屬性值顯性。 2 8 5 0 0 0 2 0 0 0 0 0 8 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 2 0 0 0 5 5 0 2 0 5 5 5 5 5 0 2 0 5 5 5 5 5 2 0 0 0 5 5 0 0 2 0 0 0 0 0 0 0 （ 2）費(fèi)爾曼鏈碼 （邊界編碼） 特征碼 高程 起止行列 鏈 碼 2 100m 1， 4 4,5,4,5,5,4 5 200m 4， 7 2,4,4,6,5,6,7,0,2,2,1 7 0 1 6 2 5 4 3 4 5 4 5 4 5 4 2 4 4 6 5 6 7 0 2 2 1 （ 2）費(fèi)爾曼鏈碼 （邊界編碼） ? 優(yōu)缺點(diǎn)： 數(shù)據(jù)壓縮率強(qiáng)，便于計(jì)算 長度 ， 面積 ，轉(zhuǎn)折方向的 凸凹度 ，易于儲(chǔ)存。 ? 優(yōu)點(diǎn)： 數(shù)據(jù)壓縮率高，易于實(shí)現(xiàn)疊加，檢索和合并運(yùn)算。 不單一：遞歸分割。所以， 常規(guī)四叉樹并不廣泛用于存儲(chǔ)數(shù)據(jù) ，其價(jià)值在于建立索引文件，進(jìn)行數(shù)據(jù)檢索。檢查相鄰 4個(gè) m碼的屬性值，如相同進(jìn)行合并，除去最低值。 否則不予歸并。 3) 四叉樹雖可修改 ， 但很費(fèi)事 （ 具體的數(shù)據(jù)結(jié)構(gòu)中會(huì)提到 ） （三）四叉樹優(yōu)缺點(diǎn) 4) 四叉樹未能直接表示物體間的拓?fù)潢P(guān)系 。 ? 點(diǎn)是空間上不能再分的地理實(shí)體，可以是具體 的或抽象的 。由多邊形邊界的 x, y坐標(biāo)對(duì)集合組成。 二、矢量數(shù)據(jù)結(jié)構(gòu) （四）矢量數(shù)據(jù)結(jié)構(gòu)編碼 （ ）樹狀索引結(jié)構(gòu)編碼 數(shù)據(jù)記錄形式： 多邊形文件 多邊形與線索引文件 線文件 邊界線與點(diǎn)索引文件 點(diǎn)文件 點(diǎn)文件： 點(diǎn)號(hào) — x,y坐標(biāo) 線文件： 線號(hào) — 起點(diǎn) — 終點(diǎn) — 點(diǎn)號(hào)序列 多邊形文件： 多邊形號(hào) — 邊界線號(hào)序列 例： P148P149 索引式 B C D E a b c f g h e f i b c i j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 線與多邊形之間的樹狀索引 點(diǎn)與邊界線之間的樹狀索引 二、矢量數(shù)據(jù)結(jié)構(gòu) （四）矢量數(shù)據(jù)結(jié)構(gòu)編碼 （ ）樹狀索引結(jié)構(gòu)編碼 ? 優(yōu)點(diǎn)： 數(shù)據(jù)冗余小、編排直觀、鄰域信息和島狀信息 可以得到一定處理。 二、矢量數(shù)據(jù)結(jié)構(gòu) （四）矢量數(shù)據(jù)結(jié)構(gòu)編碼 （ ）鏈狀雙重獨(dú)立結(jié)構(gòu) 弧段坐標(biāo)文件 ：一系列點(diǎn)的位置坐標(biāo)組成。 X11,y11。 在進(jìn)行兩種坐標(biāo)數(shù)據(jù)轉(zhuǎn)換時(shí)，通常使直角坐標(biāo)的 x， y軸分別同柵格數(shù)據(jù)的行、列平行。 ? 由上述行列值求出直線所在行列值的范圍。 （ ） 兩種數(shù)據(jù)結(jié)構(gòu)的互換 矢量向柵格轉(zhuǎn)換 ④ 面的填充 矢量數(shù)據(jù)結(jié)構(gòu)中面域用邊界線表示，面域內(nèi)部是空心的；柵格數(shù)據(jù)結(jié)構(gòu)中整