地圖數(shù)據(jù)結(jié)構(gòu)1

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

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

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

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

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

6、點位字典法獨立實體法Spaghetti方法 點實體：唯一標(biāo)識碼，實體編碼，空間坐標(biāo)(x,y) 線實體：唯一標(biāo)識碼，實體編碼，空間坐標(biāo)(x1,y1,x2,y2,xn,yn) 面實體：唯一標(biāo)識碼，實體編碼，空間坐標(biāo)(x1,y1,x2,y2,xn,yn,x1,y1) 一般cad系統(tǒng)都采用這種方法多邊形坐標(biāo)位置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獨立實體法 優(yōu)點：編碼容易，數(shù)字化操作簡單，數(shù)據(jù)編碼直觀，顯示速度快。

8、缺點：相鄰多邊形的公共邊界數(shù)字化兩次，造成數(shù)據(jù)的冗余，可能出現(xiàn)重疊或裂縫，引起數(shù)據(jù)不一致，缺少拓?fù)潢P(guān)系，空間分析困難。點位字典法 點位字典法中，點文件作為一個文件，點、線和面實體都由點號組成， 點實體：唯一標(biāo)識碼，地物編碼，點號 線實體：唯一標(biāo)識碼，地物編碼，點號1 面實體：唯一標(biāo)識碼，地物編碼，點號1點位字典法點號坐標(biāo)1X1,y12X2,y23X3,y3123456789ABC目標(biāo)序號A1B2，3，4，5C6，7，8，9拓?fù)鋽?shù)據(jù)結(jié)構(gòu)及編碼 具有拓?fù)潢P(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)就是拓?fù)鋽?shù)據(jù)結(jié)構(gòu)，拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的表示方式?jīng)]有固定的格式，也沒有形成標(biāo)準(zhǔn)，但基本原理相同。 拓?fù)湓兀狐c、線、面三種要素 基本拓?fù)?/p>

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

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

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

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

13、有很強的數(shù)據(jù)壓縮能力，并具有一定的運算功能，如面積、周長等的計算，類似于矢量數(shù)據(jù)結(jié)構(gòu)，比較適合于存儲圖形數(shù)據(jù)。 缺點：疊置運算較難實施，對局部的改動會影響整體結(jié)構(gòu)，而且相鄰區(qū)域的邊界重復(fù)存儲。游程長度編碼方法(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塊狀編碼 塊狀編碼是將游程長度編碼擴展到二維情況，采用方形區(qū)域作為記錄單元，數(shù)據(jù)結(jié)構(gòu)為：行號，列號，半徑，單元代碼，行號，列號，半徑，單元代碼，。 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碼 四叉樹編碼 再進(jìn)行游

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

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

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

18、進(jìn)行壓縮，其過程和結(jié)果如下圖所示。果如下圖所示。(1)(2)(3)間隔取點壓縮法示意圖間隔取點壓縮法示意圖從該壓縮方式可看出，這種方法的優(yōu)點是算法簡單，可以從該壓縮方式可看出，這種方法的優(yōu)點是算法簡單，可以大量壓縮數(shù)字化時用連續(xù)方法獲取的點和通過柵格數(shù)據(jù)矢大量壓縮數(shù)字化時用連續(xù)方法獲取的點和通過柵格數(shù)據(jù)矢量化得到的點，其缺點是不一定能恰當(dāng)?shù)乇Ａ舴较蛏锨柿炕玫降狞c，其缺點是不一定能恰當(dāng)?shù)乇Ａ舴较蛏锨曙@著變化的點。顯著變化的點。 光欄法光欄法 光欄法的基本思想：定義一個扇形區(qū)域，通過判斷曲線上的點在扇形光欄法的基本思想：定義一個扇形區(qū)域，通過判斷曲線上的點在扇形外還是在扇形內(nèi)，確定保留還是舍去。外還是在扇形內(nèi)，確定保留還是舍去。 光欄邊界點光欄邊界點扇邊扇邊新光欄口徑新光欄口徑光欄法