【正文】 填滿多邊形為止。 擴散算法程序設計比較復雜，需要在柵格陣列中進行搜索，占用內(nèi)存大。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 106 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 107 *掃描線法： 根據(jù)行（或列）中心線與面邊界的交點，排序，配對，填充。 1 2 3 4 5 6 當中心掃描線與多邊形相切時，要把切點分成兩個點；當掃描線與某一邊有部分重合時，只記錄重合的起點和終點。以利于配對。圖中有可能成為切點的拐點是 ①⑤⑥③大家看一看它們有什么特點？ 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 108 *邊界代數(shù)算法（ Boundary Algebra Filling—BAF)： 是一種基于積分思想的矢量格式向柵格格式轉(zhuǎn)換的算法。 基本思想： 先將邊界進行柵格化； 對每幅地圖的全部具有左右多邊形編號的邊界弧段，沿其前進方向逐個搜索，當邊界 上行時，將邊界線位置與左圖框之間的網(wǎng)格加上一個值 =（左多邊形編號） （右多邊形編號） ；當邊界 下行時，將邊界線位置與左圖框之間的網(wǎng)格加上一個值 =（右多邊形編號） （左多邊形編號） ；而不管邊界線的排列順序。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 109 該算法簡單可靠，而且僅采用加減運算，又不考慮邊界的順序，故運算速度快。 **舉一例說明： 下行線的左邊為：右多邊形號 左多邊形號 上行線的左邊為：左多邊形號 右多邊形號 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é) 構 110 二、柵格向矢量的轉(zhuǎn)換 轉(zhuǎn)換的目的： 將柵格數(shù)據(jù)分析的結(jié)果，通過矢量繪圖裝置輸出； 為了數(shù)據(jù)壓縮； 將自動掃描儀獲取的柵格數(shù)據(jù)加入矢量形式的數(shù)據(jù)庫。 轉(zhuǎn)換方法： 點的矢量化 對于任意一個柵格點 P而言，其轉(zhuǎn)換公式為 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 111 線狀柵格數(shù)據(jù)的矢量化 通常要分為四個步驟： 柵格數(shù)據(jù)的二值化； 細化； 矢量化； 曲線的光滑。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 112 為了便于進行柵格數(shù)據(jù)向矢量數(shù)據(jù)的轉(zhuǎn)換，需要對原始柵格圖像進行二值化處理，因為太多的灰度級不便于進行矢量化處理。 A、二值化 二值化處理就是將柵格數(shù)據(jù)壓縮到只有黑白兩個灰度級 0或 1的圖像。 （原圖可能是彩色的，或 0~255級灰度級） 設在原柵格數(shù)據(jù)（ G（ I， J） ）的灰度區(qū)間[Lmin， Lmax]，設定一閾值（ Lt） ∈ [Lmin，Lmax]，二值化后的 B（ I， J） 為： ??? ??LtjiGLtjiGjiB),(,0),(,1),(如果如果＜ 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 113 全彩色 灰度 二值黑白 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 114 B、柵格數(shù)據(jù)的細化 將要素占有的網(wǎng)格集縮減成為具有單網(wǎng)格寬的網(wǎng)格集的過程 （使得每一條線只保留代表其軸線的位置的單個柵格的寬度） 。 a、經(jīng)典的細化算法 通過 3 3的柵格像元陣來確定如何細化：凡是去掉后不影響拓撲連通的可去除；反之保留。 3 3的柵格像元陣共有 28=256種情況，去除等同情況，還有 51種，而其中只有一小部分可將中心點去掉。 1 1 0 0 去 1 0 0 0 去 去 留 留 留 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 115 b、最大數(shù)值法 (骨架法） 利用原始柵格數(shù)據(jù)計算格線交點的 V值 =四個相鄰柵格灰度值的和，選取 V最大的點； 如果細化后仍嫌太粗，可將所有最大 V值點的灰度值重新賦為 1，而將其它 V值賦為 0，進而再運用本方法進行細化，選取其中最大的 V值點； 為防止斷線，最后一次取 V2的值點。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 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é) 構 117 c、剝皮法 從曲線的邊緣開始，每次剝掉等于一個柵格寬的一層，直到最后留下連通的由單個柵格點組成的圖形。 （不允許剝?nèi)е虑€不連通的柵格） 方法： 第一步，從第 0行 0列開始，逐行（列）尋找灰度 值為 1的柵格，記錄起始像元的行、列號（ i， j）； 第二步，以（ i， j）為中心，按順時針方向檢測其八方向相鄰的灰度值； 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 118 第三步，計算（ i， j）八方向相鄰中自身連通像元塊數(shù) NB（即把（ I， j）去掉后，其周圍有幾部分互不相通的灰度為 1的像元） 1 1 1 0 I,J 1 0 1 1 1 1 0 0 I,J 0 0 1 1 1 0 1 0 I,J 0 1 1 1 0 1 0 1 I,J 1 0 1 0 1 0 1 0 I,J 0 1 0 1 NB=1 NB=2 NB=3 NB=4 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 119 3 若 NB=1，則其灰度值記為“ 3”，它可以被剝?nèi)?如圖所示 （為什么不直接賦值為“ 0” ？） I， J 若 NB≥2，則其灰度值記為“ 2” （ Why？） ，它不可以被剝?nèi)? I， J 第四步，尋找與（ I， j）相鄰的邊緣點，按順時針方向跟蹤。新的邊緣點為最后檢測到的灰度為 1的像元。 1 1 IJ 1 1 1 I+1,J+1 2 I+1， J1 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 120 第五步，判斷新的邊緣點是否是 2或 3（已跟蹤過）， 若是則轉(zhuǎn)到第六步，否則轉(zhuǎn)到 第二步 。 第六步，將灰度值為“ 3”的置成“ 0”，灰度值為“ 2”的置成“ 1”。 I， J I+1， J1 0 I， J 0 0 I+1， J+1 3 0 2 1第二章 地 圖 數(shù) 據(jù) 結(jié) 構 121 C、矢量化 （常采用跟蹤的方法） ： 第一步，逐行 (逐列 )尋找灰度為 1的柵格作為起始柵格； 第二步，計算當前所找柵格中心點坐標，并將其柵格值賦為 0； 第三步，以當前找到的柵格為中心，從上一柵格開始順時針方向判別其八方向相鄰，把首先找到的灰度值為 1的像元作為前進的方向上的下一個待處理的像元； 第四步，判斷是否檢測到當前柵格的八方向相鄰的灰度值都為 0（或已到邊界），若是，則轉(zhuǎn)到第一步；否則轉(zhuǎn)到第二步。直到跟蹤完為止。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 122 D、線的光滑處理（后面講） 面的矢量化 基本思想：跟蹤面狀柵格數(shù)據(jù)的邊緣點，將這些點的柵格坐標轉(zhuǎn)換為矢量坐標后連成線 方法一 步驟 （如同上述剝皮法） ： （ 1）逐行逐列尋找值為 1的柵格，記錄下起始像元的行列號（ i， j）； （ 2）計算找到的柵格的中心點坐標； 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 123 （ 3）以（ i， j）為中心，順時針方向檢查其八方向相鄰的灰度值，新的邊緣點為最后檢測到的灰度值為 1的像元； （ 4）判斷新的邊緣點是否已跟蹤到了起始像元，若是，則轉(zhuǎn)到第五步；否則轉(zhuǎn)到第二步； （ 5）對矢量化后的面域進行光滑處理 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 124 方法二 （雙邊界直接搜索算法） 基本思想： 通過邊界提取，將左右多邊形信息保存在邊界點上，每條邊界弧段由兩個并行的邊界鏈組成，分別記錄該邊界弧段的左右多邊形編號； 邊界搜索采用 2 2柵格窗口，在每個窗口內(nèi)的四個柵格數(shù)據(jù)的模式可以唯一地確定下一個窗口的搜索方向和該弧段的拓撲關系。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 125 具體步驟如下： （ 1）邊界點和節(jié)點的提取 采用 2 2柵格對圖像全圖掃描 邊界點 ：如果窗口內(nèi)四個柵格有兩個不同的編號，則為邊界點；并保留各柵格所有多邊形編號； 節(jié)點 ：如果窗口內(nèi)四個柵格有二個以上不同的編號（或?qū)蔷€上柵格兩兩相同的情況）則標識為節(jié)點（不同邊界弧段的圖形不連通），保留各柵格原編號信息 。 其余的歸零處理。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 126 “邊界點”的六種結(jié)構： A B A B B B A A A B A A A A A B B B A B A B B B “節(jié)點”的八種結(jié)構： B D A C A D A C B D A D B D A A B A A B B B A C B A A C B D A B 第二章 地 圖 數(shù) 據(jù) 結(jié) 構 127 a b c （ 2）計算邊界點和節(jié)點的中心坐標； （ 3）由一個節(jié)點向另一個節(jié)點搜索，并記錄下左右多邊形的編號 a c a c a c a c c c a c a c a c a c c c a a c a c a c c a c c a a a a a c c c c c a c c a c a a c c a a a a a b b b b b a b b b c c c c c c c c b b b b b b c b (4)去除多余點及曲線光滑處理