1、地圖數據結構空間實體的分類 地圖學中，把地理空間的實體分為點、線、面三種要素，分別用點狀、線狀、面狀符號來表示。點實體 有特定位置，維數為0的實體 1 實體點：用來代表一個實體 2 注記點：用來定位注記 3 內點：用于記錄多邊形的屬性，存在于多邊形內 4 節點：表示線的終點和起點 5 拐點：表示線段和弧段的內部點線實體 維數為1 線段、線列、弧段、鏈、路徑、多邊線等 特征： 1 實體長度 2 彎曲度 3 方向性面實體 面實體是維數為2的實體 特征： 1 周長 2 面積 3 獨立或與其他地物的鄰近性 4 內島或齒狀外形 5 重疊性與非重疊性1、三條道路在不同的空間位置，稱為定位信息 2、三條分別

2、具有不同等級，稱為屬性信息3、三條道路互相具有鄰接關系。主干道與次干道在結點處相鄰接，主干道的結點和相鄰接，結點分別與三條路段、和相關聯等，稱為拓撲關系稱為拓撲關系；C3在C6稱的左邊，稱為方位關系方位關系；不同的道路之間有一定的距離，稱為度量關系度量關系。4、隨著時間的推移，道路還將發生變化，稱為時間特征。 地圖數據的基本特征 空間特征 屬性特征 時間特征空間特征 1 空間位置 空間位置用以描述事物或現象的地理位置，又稱幾何特征、定位特征。 2 空間關系 空間關系指地理空間實體之間存在的一些具有空間特性的關系，主要包含： 拓撲關系 方位關系 度量關系屬性特征 屬性特征用以描述事物或現象的特性

3、，如事物或現象的類別、等級、數量、名稱等。 定性屬性數據 定量屬性數據時間特征 時間特征描述地理實體隨著時間而變化的特征。地圖數據的基本類型 根據地圖數據的特征，可以把地圖數據分為空間數據、關系數據、屬性數據。 空間數據是描述地圖要素中空間特征部分的數據，也叫幾何數據。 關系數據是描述空間數據之間的空間關系的數據。 屬性數據描述空間實體屬性特征的數據。空間數據 可分為點、線、面三種類型。 點類型 線類型 面類型關系數據 關系數據是描述空間數據之間的空間關系的數據，這兒說的是拓撲關系數據。 最常見的空間實體關系有6種： 點-點、點-線、點-面、線-線、線-面、面-面 拓撲關系主要有鄰接、關聯、相

4、交、相離、包含、重合等。屬性數據 描述空間實體屬性特征的數據，描述地理現象或地理實體的定性或定量指標。地圖的數據結構 幾何數據以什么形式在計算機中存儲和處理。 矢量數據結構 柵格數據結構矢量數據結構 矢量數據結構是表達地圖空間數據的一種常見的數據結構，通過記錄坐標值的方式盡可能精確的表示呈點、線或面狀分布的地理實體。 點：由一對x,y坐標表示 線：由一串有序的x,y坐標對表示 面：由一串有序的且首尾坐標相同的x,y坐標對表示。矢量數據結構的表示 表示矢量數據的結構時，應考慮問題： 1 矢量數據的存儲和處理 2 與屬性數據的聯系 3 矢量數據之間的拓撲關系 矢量數據結構表示一般有兩類： 1 簡單

5、矢量數據結構 2 拓撲數據結構簡單矢量數據結構 簡單矢量數據結構不考慮拓撲關系，可用于矢量數據的存儲、處理、顯示、輸出及一般的查詢檢索。有點、線、面三種基本的矢量數據結構形式。 點數據結構形式： 標志碼唯一，屬性碼可有多個，屬性也可放于數據庫中，通過標志碼建立矢量數據和屬性數據的聯系標識碼屬性碼X,y坐標對簡單矢量數據結構線（弧、鏈）數據結構形式標識碼屬性碼坐標對數n坐標串(x,y)面（多邊形）數據結構形式標識碼屬性碼弧段數n弧段標識碼集簡單矢量數據結構編碼 由于簡單數據結構中不考慮拓撲關系，其編碼方法僅記錄空間實體的位置、標志及屬性信息，而不記錄拓撲關系。 編碼方法有： 1 獨立實體法 2

6、點位字典法獨立實體法Spaghetti方法 點實體：唯一標識碼，實體編碼，空間坐標(x,y) 線實體：唯一標識碼，實體編碼，空間坐標(x1,y1,x2,y2,xn,yn) 面實體：唯一標識碼，實體編碼，空間坐標(x1,y1,x2,y2,xn,yn,x1,y1) 一般cad系統都采用這種方法多邊形坐標位置1x1,y1;x2,y2;x3,y3;x4,y4;x5,y5;x6,y6;x7,y7;x8,y8;x9,y9;x10,y10;x1,y12x28,y28; x29,y29; x30,y30; x31,y31; x32,y32; x33,y33; x28,y283x1,y1; x11,y11; x

7、12,y12; x13,y13; x14,y14; x15,y15; x16,y16; x17,y17; x18,y18; x19,y19; x9,y9 x10,y10; x1,y14x18,y18; x19,y19; x9,y9; x8,y8 ; x7,y7; x20,y20; x21,y21; x22,y22; x23,y23; x24,y24; x18,y185x16,y16; x17,y17; x18,y18; x24,y24; x23,y23; x27,y27; x26,y26; x25,y25; x16,y16獨立實體法 優點：編碼容易，數字化操作簡單，數據編碼直觀，顯示速度快。

8、缺點：相鄰多邊形的公共邊界數字化兩次，造成數據的冗余，可能出現重疊或裂縫，引起數據不一致，缺少拓撲關系，空間分析困難。點位字典法 點位字典法中，點文件作為一個文件，點、線和面實體都由點號組成， 點實體：唯一標識碼，地物編碼，點號 線實體：唯一標識碼，地物編碼，點號1 面實體：唯一標識碼，地物編碼，點號1點位字典法點號坐標1X1,y12X2,y23X3,y3123456789ABC目標序號A1B2，3，4，5C6，7，8，9拓撲數據結構及編碼 具有拓撲關系的矢量數據結構就是拓撲數據結構，拓撲數據結構的表示方式沒有固定的格式，也沒有形成標準，但基本原理相同。 拓撲元素：點、線、面三種要素 基本拓撲

9、關系：鄰接、關聯、包含MNMNMN點M與點N的鄰接線M與線N的鄰接面M與面N的鄰接鄰接關系是相同拓撲元素之間的關系MNpMN面M、面N與線L的關聯L線M、線N與點P的關聯關聯是不同拓撲元素之間的關系包含是面與其他拓撲元素之間的關系，如果點、線、面在該面內，則稱為被該面包含p1、p2、p3、p4、p5、p6和p7是節點；a,b,c,d,e,f,g,h,i和j為弧段；A,B,C,D,E為多邊形。p1p6p2p3p4p5bhijagcp7defABCDE為了表示出節點、弧段以及多邊形之間的拓撲關系，可以使用如下幾個關系表：節點弧段p1a,b,hP2a,d,fP3d,c,eP4e,g,fP5g,h,i

10、P6b,i,cp7j節點與弧段的拓撲關系弧段節點(始節點，終節點)ap1,p2bp1,p6cp6,p3dp3,p2ep3,p4fp2,p4gp4,p5hp5,p1ip5,p6jp7,p7弧段與節點的拓撲關系弧段多邊形左右aABb0AcDAdCAeDCfCBgDBh0BiD0jDE弧段與多邊形的拓撲關系0代表制圖區域外部的多邊形多邊形弧段Aa,b,c,dBa,f,g,hC-d, e,-fD-c,-i,-g,-e,-jEj多邊形與弧段的拓撲關系1 有的關系表中D多邊形中沒有-j，“-”代表的是逆時針方向的弧段；2 有的關系表中D多邊形中含有-j ，“-”表示面域中含有島。拓撲數據結構編碼 雙重獨立

11、地圖編碼 鏈狀雙重獨立式編碼雙重獨立地圖編碼 由兩個主要表格組成：節點表節點號坐標節點坐標p1X1,y1P2X2,y2線段表線段號起點終點左多邊形右多邊形線段號起點終點左多邊形 右多邊形ap1p2ABbp1p60A鏈狀雙重獨立式編碼 由四個或三個文件組成 節點文件：與雙重獨立地圖編碼類似 弧段坐標文件：標識碼，弧段中間點 弧段文件：標識碼，起始節點，終止節點，左多邊形，右多邊形，內點 多邊形文件：標識碼，弧段號及面積、周長及中心點坐標等柵格數據結構 柵格結構柵格結構是以規則的像元陣列來表示空間地物或現象的分布的數據結構，其陣列中的每個數據表示地物或現象的屬性特征。換句話說，柵格數據結構就是像元

12、陣列，用每個像元的行列號確定位置，用每個像元的值表示實體的類型、等級等的屬性編碼 。柵格數據結構 點實體點實體：表示為一個像元； 線實體線實體：表示為在一定方向上連接成串的相鄰像元的集合； 面實體面實體：表示為聚集在一起的相鄰像元的集合。 柵格數據結構的表示 1 簡單數據結構的表示 把柵格數據看做一個數據矩陣，逐行記錄各像元代碼。 2 其他數據結構的表示柵格數據的壓縮編碼 1 鏈碼 2 游程長度編碼 3 塊狀編碼 4 四叉樹編碼鏈碼 由某一起始點開始并按某些基本方向確定的單位矢量鏈。前兩個數字表示起點的行列號，第三個數字開始的每個數字表示單位矢量的方向。01273654單位矢量方向鏈碼 優點：

13、有很強的數據壓縮能力，并具有一定的運算功能，如面積、周長等的計算，類似于矢量數據結構，比較適合于存儲圖形數據。 缺點：疊置運算較難實施，對局部的改動會影響整體結構，而且相鄰區域的邊界重復存儲。游程長度編碼方法(1)0,7,2,1,0,20,1,1,1,0,4,2,1,0,1,3,20,5,2,1,0,1,3,32130游程長度編碼方法(2)0,7,2,8,0,100,1,1,2,0,6,2,7,0,8,3,100,5,2,6,0,7,3,102130塊狀編碼444777770444477744448877004888770088887800088000000080000000000044477

14、77704444777444488770048887700888878000880000000800000000000塊狀編碼 塊狀編碼是將游程長度編碼擴展到二維情況，采用方形區域作為記錄單元，數據結構為：行號，列號，半徑，單元代碼，行號，列號，半徑，單元代碼，。 1,1,1,4, 1,2,2,4 ,1,4,1,7, 1,5,1,7, 1,6,2,7, 1,8,1,7, 2,1,1,0, 2,4,1,4, 2,5,1,4, 2,8,1,7, 3,1,1,4, 3,2,1,4, 3,3,1,4, 3,4,1,4, 3,5,2,8, 3,7,2,7,四叉樹編碼 Morton碼 四叉樹編碼 再進行游

15、程長度編碼游程長度編碼方法矢量數據的壓縮方法矢量數據的壓縮方法 道格拉斯道格拉斯普克法普克法 垂距法垂距法 間隔取點法間隔取點法 光欄法光欄法 道格拉斯道格拉斯普克法普克法 道格拉斯道格拉斯普克法，又稱分裂法。普克法，又稱分裂法。該算法實現的基本思路是：對每一條曲線的首末點虛連一該算法實現的基本思路是：對每一條曲線的首末點虛連一條直線，求其它所有點與該直線的距離，并找出其中的最條直線，求其它所有點與該直線的距離，并找出其中的最大距離值大距離值dmaxdmax，用，用dmaxdmax與限差與限差相比：相比： 若若dmaxdmax，這條曲線上的中間點全部舍去；，這條曲線上的中間點全部舍去； 若若d

16、maxdmax，保留，保留dmaxdmax對應的坐標點，并以該點為界，對應的坐標點，并以該點為界，把曲線分為兩部分，對這兩部分曲線重復上述操作，直至把曲線分為兩部分，對這兩部分曲線重復上述操作，直至整條曲線處理結束。整條曲線處理結束。表示被舍棄的結點偏離特征點連表示被舍棄的結點偏離特征點連線之間的垂直距離，一般取值為線之間的垂直距離，一般取值為0.2mm(若比例尺為若比例尺為1：10000，則，則實際距離為實際距離為2m) 道格拉斯普克法示意圖道格拉斯普克法示意圖 垂距垂距( (限值限值) )法法 垂距法的基本思路是：每次順序取曲線上的三個點，垂距法的基本思路是：每次順序取曲線上的三個點，計算

17、中間點與其它兩點連線的垂線距離計算中間點與其它兩點連線的垂線距離di，并與限差，并與限差比比較。若較。若d di i，則中間點去掉；若，則中間點去掉；若di，則中間點保留。，則中間點保留。然后順序取下三個點繼續處理，直到這條線結束。然后順序取下三個點繼續處理，直到這條線結束。 垂距法示意圖垂距法示意圖 間隔取點法間隔取點法間隔取點法的基本思路是：每隔間隔取點法的基本思路是：每隔n n個點個點取一點，或每隔一規定的距離取一點，但取一點，或每隔一規定的距離取一點，但首末點一定要保留。例如對一曲線每隔一首末點一定要保留。例如對一曲線每隔一個點（個點（n n=1=1）取一點進行壓縮，其過程和結）取一點

18、進行壓縮，其過程和結果如下圖所示。果如下圖所示。(1)(2)(3)間隔取點壓縮法示意圖間隔取點壓縮法示意圖從該壓縮方式可看出，這種方法的優點是算法簡單，可以從該壓縮方式可看出，這種方法的優點是算法簡單，可以大量壓縮數字化時用連續方法獲取的點和通過柵格數據矢大量壓縮數字化時用連續方法獲取的點和通過柵格數據矢量化得到的點，其缺點是不一定能恰當地保留方向上曲率量化得到的點，其缺點是不一定能恰當地保留方向上曲率顯著變化的點。顯著變化的點。 光欄法光欄法 光欄法的基本思想：定義一個扇形區域，通過判斷曲線上的點在扇形光欄法的基本思想：定義一個扇形區域，通過判斷曲線上的點在扇形外還是在扇形內，確定保留還是舍去。外還是在扇形內，確定保留還是舍去。 光欄邊界點光欄邊界點扇邊扇邊新光欄口徑新光欄口徑光欄法