1、核心技能實訓空間數據結構轉換主講人：魏瑤陜西鐵路工程職業技術學院2017.1.16核心技能實訓空間數據結構轉換主講人：魏瑤2017.1.16目錄CONTENTS柵格化矢量化0102目錄CONTENTS柵格化矢量化0102柵格化01柵格化01將數據用矢量數字化的方法輸入計算機或以矢量的方式存在計算機中。如：行政邊界、交通干線、土地利用類型等表現為點、線、多邊形數據矢量柵格化1、柵格化將數據用矢量數字化的方法輸入計算機或以矢量的方式存在計算機中確定柵格矩陣（行列數/分辨率）點的變換、線的變換以及多邊形的變換（面的變換）1、柵格化準備好矢量數據或矢量地圖；構架一個與地圖等大小的格網， 選取好適當的格

2、網密度或分辨率，依據范圍則可以算出格網的行列數。根據地圖上的點、線、多邊形相對這個格網的配置及其屬性來確定每一個項元的數值。確定柵格矩陣（行列數/分辨率）1、柵格化準備好矢量數據或矢量1、柵格化矢量數據轉換成柵格數據后，圖形的幾何精度必然要降低，所以選擇柵格尺寸的大小要盡量滿足精度要求，使之不過多地損失地理信息。為了提高精度，柵格需要細化，但柵格細化，數據量將以平方指數遞增，因此，精度和數據量是確定柵格大小的最重要的影響因素。在轉換之前需要確定柵格單元的大小，柵格單元的大小又稱為柵格圖像的分辨率，直接決定了柵格數據的精度 確定柵格矩陣1、柵格化矢量數據轉換成柵格數據后，圖形的幾何精度必然要降低

3、1、柵格化 確定柵格矩陣YXOJIyx(0,0)XmaxYminXminYmaxI=(Ymax-Ymin)/dyJ=(Xmax-Xmin)/dxI，J為整數，尾數入上去dx=(Xmax-Xmin)/Jdy=(Ymax-Ymin)/I1、柵格化 確定柵格矩陣YXOJIyx(0,0)XmaxY1、柵格化 點的柵格化點的變換十分簡單，只要這個點落在那個網格中，就是屬于那個網格元素，根據該點狀對象的特性賦予該像元屬性值。1、柵格化 點的柵格化點的變換十分簡單，只要這個點落在那1、柵格化 線的柵格化線是由多個直線段組成的，因此線的柵格化的核心就是直線段如何由矢量數據轉換為柵格數據。YX（X1，Y1）（X

4、2，Y2）假定一線段兩端點之間經過若干個網格元素(至少一個)，兩端點坐標為(X1，Y1)，(X2，Y2)1、柵格化 線的柵格化線是由多個直線段組成的，因此線的柵格1、柵格化 面的柵格化a、 基于弧段數據的柵格化方法：按行或列做中心掃描線求交點柵格坐標的行列值判斷交點左右多邊形數值交點排序并逐段生成柵格數據特點：計算量較大，算法比較復雜。1、柵格化 面的柵格化a、 基于弧段數據的柵格化方法：1、柵格化面的柵格化邊界線的轉化與線的柵格化方法相同，接下來就是屬性的填充填充的方法很多，關鍵問題是正確判斷哪些柵格單元位于多邊形之內，哪些位于多邊形之外。為此，多邊形必須嚴格封閉，沒有縫隙1、柵格化面的柵格

5、化邊界線的轉化與線的柵格化方法相同，接下來1、柵格化面的柵格化1、柵格化面的柵格化1、柵格化 面的柵格化b、多邊形內部屬性填充方法（基于多邊形數據的柵格化方法）：內部點擴散法射線算法平行線掃描法與鉛垂線跌落法邊界代數充填算法邊界點跟蹤算法1、柵格化 面的柵格化b、多邊形內部屬性填充方法（基于多1、柵格化面的柵格化內部點擴散算法缺點程序設計復雜，需要在柵格陣列中搜索，占用內存很大，在內存受限時很難采用在一定的柵格精度上，如果復雜圖形的同一多邊形的兩條邊界落在同一個或相鄰的兩個柵格內，會造成多邊形不連通，不能完成多邊形的填充1、柵格化面的柵格化內部點擴散算法缺點程序設計復雜，需要在1、柵格化面的柵

6、格化射線法概念：射線算法，又稱為檢驗交點數，是逐點判別數據柵格點在某多邊形之外或在多邊形內來決定是否記錄該點基本原理：具體實現是由待判點向圖外某點引射線，判斷該射線與某多邊形所有邊界相交的總次數，判斷的基本原理：如相交偶數次，則待判點在該多邊形的外部如相交奇數次，則待判點在該多邊形的內部1、柵格化面的柵格化射線法概念：射線算法，又稱為檢驗交點數，1、柵格化面的柵格化N=0N=2N=1N=3N=4射線法基本原理1、柵格化面的柵格化N=0N=2N=1N=3N=4射線法基1、柵格化面的柵格化射線法特殊情況：奇異點1、柵格化面的柵格化射線法特殊情況：奇異點1、柵格化面的柵格化平行線掃描法與鉛垂線跌落法

7、基本原理射線算法的改進，將射線改為沿柵格陣列列方向或行方向掃描線，判斷與射線算法相似。省去了計算射線與多邊形邊界交點的大量運算，大大提高了效率。又稱為掃描算法XYRfebagdcMN1、柵格化面的柵格化平行線掃描法與鉛垂線跌落法基本原理射線1、柵格化面的柵格化邊界代數填充算法基本思想：基于積分思想的矢量格式向柵格格式轉換算法，它適合于記錄拓撲關系的多邊形矢量數據轉換為柵格結構實現過程：初始化的柵格陣列各柵格值為零以柵格行列為參考坐標軸，由多邊形某點開始順時針搜索邊界線邊界上行時，邊界左側行坐標相同的柵格被減去a，邊界下行時，邊界左側行坐標相同的柵格被加上a1、柵格化面的柵格化邊界代數填充算法基

8、本思想：基于積分思想的1、柵格化面的柵格化邊界代數填充算法1、柵格化面的柵格化邊界代數填充算法1、柵格化面的柵格化邊界點跟蹤算法以多邊形為單位按順時針方向跟蹤單元格：上行L；橫向N；下行R（如果為島嶼，則相反）逐行掃描，充填LR間的單元格NNLRNNLRLRLRLRNNN1、柵格化面的柵格化邊界點跟蹤算法以多邊形為單位NNLRNN矢量化02矢量化02矢量化定義與要求定義及要求：從柵格單元轉換到幾何圖形的過程稱為矢量化，矢量化過程要保證以下兩點要求：拓撲轉換，即保持柵格表示出的連通性與鄰接性轉換物體正確的外形矢量化定義與要求定義及要求：從柵格單元轉換到幾何圖形的過程稱矢量化一般轉化步驟邊界提取邊

9、緣銳化（遙感影像或分類柵格，面狀地物）線的細化（掃描矢量圖，線狀地物）二值化邊界追蹤拓撲關系生成線的簡化及曲線矢量化一般轉化步驟邊界提取矢量化一般轉化步驟1、邊界提取邊緣提取（數字圖像處理）Lenna的Sobel邊界 Lenna的Prewitt邊界原始圖片矢量化一般轉化步驟1、邊界提取邊緣提取（數字圖像處理）Le矢量化一般轉化步驟1、邊界提取線的細化將占有多個柵格寬的圖形要素縮減為只有1個像素剝皮法：每次剝掉等于一個柵格寬的一層，最后只留下彼此連通的由單個柵格組成的圖形剝皮法保持圖像的連接性不變和關鍵部分矢量化一般轉化步驟1、邊界提取線的細化將占有多個柵格寬的圖矢量化一般轉化步驟1、邊界提取線

10、的細化剝皮法算法原理剝皮法過程矢量化一般轉化步驟1、邊界提取線的細化剝皮法算法原理剝皮法矢量化一般轉化步驟1、邊界提取線的細化骨架法：確定圖形的骨架，而將非骨架上的多余柵格刪除基本原理：掃描全圖，凡是像元值為1的柵格都用V值取代。V值是該柵格與北、東和北東三個相鄰柵格像元值之和，即：保留最大V值的柵格，刪去其他柵格，但必須保證連通。因最大V值的柵格只能分布在圖形的中心線、骨架上，因此選取最大值柵格的過程就是細化的過程矢量化一般轉化步驟1、邊界提取線的細化骨架法：確定圖形的骨矢量化一般轉化步驟1、邊界提取二值化一般情況下，柵格數據是按0255的不同灰度值表達的為了簡化追蹤算法，需把256個灰階壓

11、縮為2個灰階，即0和1兩級。為此，假設任一格網的灰度值為G(i,j),閥值為T，那么，根據下式就可以得到二值圖G(i,j)=1 f(i,j)= T0 f(i,j)= T矢量化一般轉化步驟1、邊界提取二值化一般情況下，柵格數據是矢量化一般轉化步驟2、邊界追蹤目的：就是將細化處理后的柵格數據，整理為從結點出發的線段或閉合的線條，并以矢量形式存儲（坐標）基本原理：對每個邊界弧段由一個結點向另一個結點搜索，通常對每個已知邊界點需除了進入方向的其他7個方向搜索下一個邊界點，直到連成邊界弧段矢量化一般轉化步驟2、邊界追蹤目的：就是將細化處理后的柵格數矢量化一般轉化步驟目的：由于搜索是逐個柵格進行的，所以弧段或多邊形的數據列十分密集。為了減少存儲量，在保證線段精度的情況下可以刪除部分數據點曲線光滑：假象曲線為一組離散點，尋找形式較簡單、性能良好的曲線解析式插值方式逼近方式3