《計算機地圖制圖(中國礦業(yè)大學(xué)課件)2數(shù)據(jù)結(jié)構(gòu).ppt》由會員分享，可在線閱讀，更多相關(guān)《計算機地圖制圖(中國礦業(yè)大學(xué)課件)2數(shù)據(jù)結(jié)構(gòu).ppt（91頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、計算機地圖制圖,中國礦業(yè)大學(xué)銀川學(xué)院,第二章 地圖數(shù)據(jù)結(jié)構(gòu),2.1 空間實體及其描述 2.2 矢量數(shù)據(jù)結(jié)構(gòu) 2.3 柵格數(shù)據(jù)結(jié)構(gòu) 2.4 矢柵一體化數(shù)據(jù)結(jié)構(gòu) 2.5 三維數(shù)據(jù)結(jié)構(gòu),2.1 空間實體及其描述,,1）地理實體 2）地理實體的描述 3）實體的空間特征 4）實體間的關(guān)系,2.2 矢量數(shù)據(jù)結(jié)構(gòu),,1）圖形表示 2）獲取方式 3）組織 4）編碼方式,2.3 柵格數(shù)據(jù)結(jié)構(gòu),1）圖形表示 2）數(shù)據(jù)組織 3）柵格結(jié)構(gòu)的建立 4）柵格數(shù)據(jù)編碼,,2.4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),,1）矢柵一體化概念 2）三個約定和細(xì)分格網(wǎng)法 3）一體化數(shù)據(jù)結(jié)構(gòu)設(shè)計,2.5 三維數(shù)據(jù)結(jié)構(gòu),1）概述 2）八叉樹結(jié)構(gòu) 3）三
2、維邊界表示法,,本章重點 點、線、面狀實體； 空間數(shù)據(jù)拓?fù)潢P(guān)系； 矢量數(shù)據(jù)結(jié)構(gòu)、柵格數(shù)據(jù)結(jié)構(gòu)；,2.1.1 空間實體（地理實體）,自然界現(xiàn)象和社會經(jīng)濟(jì)事件中不能再分割的單元，具有概括性，復(fù)雜性，相對意義。,2.1 空間實體及其描述,點狀實體-0維 線狀實體-1維 面狀實體-2維 體狀實體-3維,點狀實體,有特定位置，維數(shù)為0的物體。,實體點,注記點,內(nèi)點,節(jié)點（Vertex）,拐點,線狀實體,具有相同屬性的點的軌跡，由一系列有序坐標(biāo)表示的物體。,實體長度,彎曲度,方向性,,面狀實體（多邊形）,是對湖泊、島嶼、地塊等一類現(xiàn)象的描述。在數(shù)據(jù)庫中由一封閉曲線加內(nèi)點來表示。,面積范圍,周長,獨立性,內(nèi)
3、島嶼或鋸齒狀外形,重疊性與非重疊性,,體狀實體（多邊形）,描述三維空間中的現(xiàn)象的物體。,體積,周長,內(nèi)島,含有弧立塊或相鄰塊,斷面圖與剖面圖,實體類型組合,為地圖數(shù)據(jù)庫的有效建立，空間查詢，空間分析，輔助決策等提供了最基本的關(guān)系。,有助于形成標(biāo)準(zhǔn)的SQL空間查詢語言，便于空間特征的存儲，提取，查詢，更新等。,,線面,1、區(qū)域包含線：計算區(qū)域內(nèi)線的密度，某省的水系分布情況。 2、線通過區(qū)域：公路上否通過某縣。 3、線環(huán)繞區(qū)域：區(qū)域邊界，搜索左右區(qū)域名稱，中國與哪些國家接壤。 4、線與區(qū)域分離：距離。,,面面,1、包含：島,某省的湖泊分布。 2、相合：重疊，學(xué)校服務(wù)范圍與菜場服務(wù)范圍重疊區(qū)。 3、
4、相交：劃分子區(qū)。 4、相鄰：計算相鄰邊界性質(zhì)和長度，公共連接邊界。 5、分離：計算距離。,,2.1.2 空間實體的描述,空間數(shù)據(jù),內(nèi)容,數(shù)據(jù)類型,數(shù)據(jù)結(jié)構(gòu),幾何數(shù)據(jù)（空間數(shù)據(jù)、圖形數(shù)據(jù)） 關(guān)系數(shù)據(jù)實體間的鄰接、關(guān)聯(lián)包含等相互關(guān)系 屬性數(shù)據(jù)各種屬性特征和時間 元數(shù)據(jù),矢量、柵格、TIN（專用于地表或特殊造型） RDBMS屬性表----采用MIS較成熟,位置、形狀、尺寸 、 識別碼（名稱）實體的角色、功能、行為、實體的衍生信息 時間 測量方法、編碼方法、空間參考系等,空間特征：地理位置和空間關(guān)系 屬性特征名稱、等級、類別等 時間特征,基本特征,,,,,,,2.1.3 空間數(shù)據(jù)的基本特征,2.1.
5、3 空間數(shù)據(jù)的類型,1）依據(jù)數(shù)據(jù)來源： 地圖數(shù)據(jù)、地形數(shù)據(jù)、屬性數(shù)據(jù)、元數(shù)據(jù)、影象數(shù)據(jù)。,2）依表示對象：,2.1.4 實體間空間關(guān)系,1、拓?fù)淇臻g關(guān)系 2、順序空間關(guān)系（方向空間關(guān)系） 3、度量空間關(guān)系 1）地理空間中兩點間的距離有兩種度量方法： 2）距離類別：,上下左右、前后、東南西北。,a、沿真實地球表面。 b、沿地球旋轉(zhuǎn)橢球體距離。,歐氏距離、時間距離、大地測量距離。,1、定義： 指圖形保持連續(xù)狀態(tài)下變形，但圖形關(guān)系不變的性質(zhì)。 將橡皮任意拉伸，壓縮，但不能扭轉(zhuǎn)或折疊。,拓?fù)潢P(guān)系,,2、種類： 1）關(guān)聯(lián)性（不同類要素間） 結(jié)點與弧段：如V9與L5,L6,L3 多邊形與弧段
6、：P2與L3,L5,L2 2）鄰接性： (同類元素之間) 多邊形之間、結(jié)點之間。,鄰接矩陣：,重疊： 鄰接：1 不鄰接：0,連通矩陣：,重疊： 連通：1 不連通：0,3)方向性：一條弧段的起點、終點確定了弧段的方向。用于表達(dá)現(xiàn)實中的有向弧段，如城市道路單向，河流的流向等。 4)包含性：指面狀實體包含了哪些線、點或面狀實體。 5)區(qū)域定義：多邊形由一組封閉的線來定義。 6)層次關(guān)系：相同元素之間的等級關(guān)系，武漢市有各個區(qū)組成。,3、拓?fù)潢P(guān)系的表達(dá)： 拓?fù)潢P(guān)系具體可由4個關(guān)系表來表示： （1）面--鏈關(guān)系： 面 構(gòu)成面的弧段 （2）鏈--結(jié)點關(guān)系：鏈 鏈兩端的結(jié)點 （3）結(jié)點--鏈關(guān)系：結(jié)點 通過
7、該結(jié)點的鏈 （4）鏈面關(guān)系： 鏈 左面 右面,,,,,,,,,4、拓?fù)潢P(guān)系的意義： 1）能清楚地反映實體之間的邏輯結(jié)構(gòu)關(guān)系。它比幾何關(guān)系具有更大的穩(wěn)定性，不隨地圖投影變化。 2）有助于空間要素的查詢，利用拓?fù)潢P(guān)系可以解決許多實際問題。 3）根據(jù)拓?fù)潢P(guān)系可重建地理實體。,哥尼斯堡七橋問題,哥尼斯堡七橋問題,2.2 矢量數(shù)據(jù)結(jié)構(gòu),2.2.1 圖形表示,2.2.2 獲取方式,外業(yè)測量（電子手簿） 2）柵格數(shù)據(jù)轉(zhuǎn)換（柵格數(shù)據(jù)矢量化） 3）跟蹤數(shù)字化,2.2.3 矢量數(shù)據(jù)組織,應(yīng)考慮以下問題： 矢量數(shù)據(jù)自身的存貯和處理。 與屬性數(shù)據(jù)的聯(lián)系。 矢量數(shù)據(jù)之間的空間關(guān)系(拓?fù)潢P(guān)系)。,以點為例：,線（符號、方
8、向）、面（符號）都有相應(yīng)的相關(guān)屬性（矢量結(jié)構(gòu)中關(guān)于幾何位置坐標(biāo)的編碼方式）。,2.2.4 矢量數(shù)據(jù)的編碼方式,1）實體式,面條模型（spaghetti）:以實體為單位記錄坐標(biāo),優(yōu)點：結(jié)構(gòu)簡單、直觀、易實現(xiàn)以實體為單位的運算和顯示。,缺點： 1、相鄰多邊形的公共邊界被數(shù)字化并存儲兩次，造成數(shù)據(jù)冗余和碎屑多邊形（數(shù)據(jù)不一致），浪費空間，雙重邊界不能精確匹配。 2、自成體系，缺少多邊形的鄰接信息，無拓?fù)潢P(guān)系，難以進(jìn)行鄰域處理。 3、島作為一個單個圖形，沒有與外界多邊形聯(lián)系。不易檢查拓?fù)溴e誤。 所以，這種結(jié)構(gòu)只用于簡單的制圖系統(tǒng)中顯示圖形。,2）索引式（樹狀）,對所有點的坐標(biāo)按順序建坐標(biāo)文件，再建點
9、與邊（線）、線與多邊形的索引文件。,與實體式相比： 優(yōu)點：用建索引的方法消除多邊形數(shù)據(jù)的冗余和不一致，鄰接信息、島信息可在多邊形文件中通過是否公共弧段號的方式查詢。 缺點：表達(dá)拓?fù)潢P(guān)系較繁瑣，給相鄰運算、消除無用邊、處理島信息、檢索拓?fù)潢P(guān)系等帶來困難，以人工方式建立編碼表，工作量大，易出錯。,3）雙重獨立式編碼,DIME(Dual Independent Map Encoding)，是美國人口統(tǒng)計系統(tǒng)采用的一種編碼方式，是一種拓?fù)渚幋a結(jié)構(gòu)。,拓?fù)潢P(guān)系明確,4）鏈狀雙重獨立式編碼,以線段為記錄單位改為以弧段為單位。,特點：,拓?fù)潢P(guān)系明確，以弧段為記錄單位，滿足實際應(yīng)用。被一些成熟的商品化軟件采用
10、，如ARC/INFO軟件。 例：ARC文件： INFO：屬性表 AAT（Arc Attribute Table）,2.3 柵格數(shù)據(jù)結(jié)構(gòu),2.3.1 圖形表示,用密集正方形（或三角形，多邊形）將地理區(qū)域劃分為網(wǎng)格陣列。 位置由行，列號定義，屬性為柵格單元的值。 柵格數(shù)據(jù)的比例尺就是柵格(象元)的大小與地表相應(yīng)單元的大小之比。,點：單個柵格,線：相鄰柵格組,面：柵格片,2.3.2 柵格數(shù)據(jù)組織,針對一個柵格單元對應(yīng)多個屬性值的多層?xùn)鸥裎募?組織方法,2.3.3 柵格結(jié)構(gòu)的建立,1）建立途徑,手工獲取 掃描儀掃描 矢量數(shù)據(jù)轉(zhuǎn)換 遙感影像數(shù)據(jù) 格網(wǎng)DEM數(shù)據(jù),2）柵格系統(tǒng)的確定,實質(zhì)是柵格坐標(biāo)系的確
11、定--坐標(biāo)系原點和坐標(biāo)軸的確定。 起始坐標(biāo)應(yīng)與國家基本比例尺地形圖公里網(wǎng)的交點相一致，并分別采用公里網(wǎng)的縱橫坐標(biāo)軸作為柵格系統(tǒng)的坐標(biāo)軸。,3）柵格單元尺寸的確定,原則：應(yīng)能有效地逼近空間對象的分布特征，又減少數(shù)據(jù)的冗余度。 方法：用保證最小多邊形的精度標(biāo)準(zhǔn)來確定尺寸經(jīng)驗公式：,h為柵格單元邊長 Ai為區(qū)域所有多邊形的面積。,4）柵格代碼（屬性值）的確定,中心點法 面積占優(yōu)法 重要性法 長度占優(yōu)法,2.3.4 柵格數(shù)據(jù)編碼,1）直接?xùn)鸥窬幋a,將柵格數(shù)據(jù)看作一個數(shù)據(jù)矩陣，逐行記錄代碼數(shù)據(jù)。 1）每行都從左到右記錄：AAAAABBBAABBAABB 2）奇數(shù)行從左到右，偶數(shù)行從右到左； 特點：直觀
12、、基本，沒進(jìn)行任何壓縮數(shù)據(jù)處理。,將數(shù)據(jù)表示成更緊湊的格式以減少存儲空間的一項技術(shù)。分為： 無損壓縮：在編碼過程中信息沒有丟失，經(jīng)過解碼可恢復(fù)原有的信息---信息保持編碼。 有損壓縮：為最大限度壓縮數(shù)據(jù)，在編碼中損失一些認(rèn)為不太重要的信息，解碼后，這部分信息無法恢復(fù)。--信息不保持編碼。,數(shù)據(jù)壓縮,2）行程編碼（變長編碼）,將原圖表示的數(shù)據(jù)矩陣變?yōu)閿?shù)據(jù)對： 1）屬性碼，長度，行號（可不要） 2）屬性碼，點位 特點：數(shù)據(jù)量增加不明顯，壓縮率高，易于操作，適用于區(qū)域面積較大專題圖。,3）塊碼（游程編碼向二維的擴展）,采用方形區(qū)域作為記錄單元，每個記錄單元包括相鄰的若干柵格。依次掃描，編過的不重復(fù)。
13、 數(shù)據(jù)對組成：（初始行、列，半徑，屬性值） 特點：具有可變分辨率，分辨率低，壓縮比高，隨圖形復(fù)雜程度的提高而降低。,（1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),4）鏈?zhǔn)骄幋a、Freeman鏈碼、邊界鏈碼,,,將柵格數(shù)據(jù)（線狀地物面域邊界）表示為矢量鏈的記錄。,優(yōu)點：便于面積、長度、轉(zhuǎn)折方向和邊界、線段凹凸度的計算。 缺點：不易做邊界合并，插入操作、編輯較困難。區(qū)域空間分析困難，相鄰區(qū)域邊界被重復(fù)存儲。,5）四叉樹編碼,四叉樹概述：一種可變分率的非均勻網(wǎng)格系統(tǒng)。是最有效的柵格數(shù)據(jù)壓縮編碼方法之一。,基本思想： 將2n2n象元組成的圖像(不足的用背景補上)
14、按四象限進(jìn)行遞歸分割，判斷屬性是否單一。最后得到一顆四分叉的倒向樹。,樹形表示： 用一倒立樹表示這種分割和分割結(jié)果。 根：整個區(qū)域 高：深度、分幾級，幾次分割 葉：不能再分割的塊 樹叉：還需分割的塊 每個樹叉均有4個分叉，叫四叉樹。,編碼方法： 常規(guī)四叉樹：記錄葉結(jié)點，中間結(jié)點，結(jié)點之間用指針聯(lián)系。 每個結(jié)點需要6個變量： 父結(jié)點指針、四個子結(jié)點的指針和本結(jié)點的屬性值。 線性四叉樹：記錄葉結(jié)點的位置，深度，屬性。 地址碼（定位碼、Morton碼）,,,指針不僅增加了數(shù)據(jù)的存儲量，還增加了操作的復(fù)雜性，并不廣泛用于存儲數(shù)據(jù)。,,存貯量小，只對葉結(jié)點編碼，直接尋址，定位碼容易存儲和執(zhí)行實現(xiàn)集合相
15、加等組合操作。,四進(jìn)制Morton碼,方法1：四叉樹從上而下由葉結(jié)點找Morton碼。 A、分割一次，增加一位數(shù)字，大分割在前，小分割在后。所以，碼的位數(shù)表示分割的次數(shù)。 B、每一個位均是不大于3的四進(jìn)制數(shù)，表達(dá)位置。 由Morton找出四叉樹葉結(jié)點的具體位置。,方法2：四叉樹自下而上合并的方法。 1）計算每個柵格對應(yīng)的MQ MQ=2*Ib+Jb 其始行列號從0計。 2) 按碼的升序排成線性表，放在連續(xù)的內(nèi)存塊中。 3）依次檢查每四個相鄰的MQ對應(yīng)的屬性值，相同合并（不同碼位去掉），不同則存盤,直到?jīng)]有能夠合并的子塊為止。,十進(jìn)制Morton碼,按位操作的方法。 如行為2、列為3的柵格
16、的MD 步驟： (1)行、列號為二進(jìn)制 (2)I行J列交叉 (3)再化為十進(jìn)制. 實質(zhì)上是按左上、右上、左下、右下的順序，從零開始對每個柵格進(jìn)行自然編碼。,把一幅2n2n的圖像壓縮成線性四叉樹的過程：,1、按Morton碼把圖象讀入一維數(shù)組。 2、相鄰的四個象元比較，一致的合并，只記錄第一個象元的Morton碼。循環(huán)比較所形成的大塊，相同的再合并，直到不能合并為止。 3、進(jìn)一步用游程長度編碼壓縮。壓縮時只記錄第一個象元的Morton碼。,1、按Morton碼讀入一維數(shù)組。 Morton碼：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 象元值：A A A B
17、A A B B A A A A B B B B 2、四相鄰象元合并，只記錄第一個象元的Morton碼。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B 3、用游程長度編碼壓縮。 0 3 4 6 8 12 A B A B A B,四叉樹優(yōu)缺點,優(yōu)點： 1）占用空間比網(wǎng)絡(luò)法要少得多，是一種非冗余表示法。 2）四叉樹具有可變率或多重分辯率的特點使得它有很好的應(yīng)用前景，適用于處理凝聚性或呈不均勻的塊狀分布的空間數(shù)據(jù)，但不適用于連續(xù)表面或線狀地物。,缺點： 1）矢/柵正反變換還不理想。 2）建立四叉樹耗費機時很多。 3）修改費事。 4）未能直接表示物體間的拓?fù)潢P(guān)系。 5
18、）轉(zhuǎn)換的不穩(wěn)定性（滑動變異）。 6）無內(nèi)在相關(guān)性。,矢量、柵格數(shù)據(jù)結(jié)構(gòu)的選擇,應(yīng)根據(jù)應(yīng)用目的和應(yīng)用特點、可能獲得的數(shù)據(jù)精度以及軟件和硬件配置情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)。,柵格結(jié)構(gòu):大范圍小比例尺的自然資源、環(huán)境、農(nóng)林業(yè)等區(qū)域問題的研究。,矢量結(jié)構(gòu)：城市分區(qū)或詳細(xì)規(guī)劃、土地管理、公用事業(yè)管理等方面的應(yīng)用。,2.4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),2.4.1 以矢量的方式來組織柵格數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)： 線狀地物：記錄原始取樣點和路徑所通過的柵格。 面狀地物：記錄多邊形周邊以外及中間的面域柵格。 保留了矢量的全部性質(zhì)，也建立了柵格與地物的關(guān)系，即路徑上的任一點都直接與目標(biāo)建立了聯(lián)系。,將矢量面對目標(biāo)的方法和柵格元子充
19、填的方法結(jié)合。,a.點狀地物是地球表面上的點僅有空間位置，沒有形狀和面積，在計算機內(nèi)部僅有一個位置數(shù)據(jù)。,2.4.2 三個約定和細(xì)分格網(wǎng)法,b.線狀地物是地球表面的空間曲線，有形狀但沒有面積，在平面上的投影是一連續(xù)不間斷的直線或曲線，在計算機內(nèi)部需要用一組元子填滿整個路徑。,c.面狀地物是地球表面的空間曲面，具有形狀和面積，在平面上的投影是由邊界包圍的緊致空間和一組填滿路徑的元子表達(dá)的邊界組成。,為提高柵格表示精度，采用細(xì)分格網(wǎng)法： 將一對X,Y坐標(biāo)用兩個Morton碼代替： 前一M1表示該點（采樣點或附加的交叉點）所在基本格網(wǎng)的地址碼，后者M(jìn)2 表示該點對應(yīng)的細(xì)分格網(wǎng)的Morton碼，既顧全
20、整體定位，又保證精度。,2.4.3 一體化數(shù)據(jù)結(jié)構(gòu)設(shè)計,線性四叉樹(Morton)是基本數(shù)據(jù)格式，三個約定設(shè)計點、線、面數(shù)據(jù)結(jié)構(gòu)的基本依據(jù)，細(xì)分格網(wǎng)法保證足夠精度。,1）點狀地物和結(jié)點的數(shù)據(jù)結(jié)構(gòu)：點僅有位置、沒有形狀和面積，將點的坐標(biāo)轉(zhuǎn)化為地址碼M1和M2 , 便于點的插入和刪除和處理柵格內(nèi)含多個點狀目標(biāo)的情況。,2）線狀地物和結(jié)點的數(shù)據(jù)結(jié)構(gòu)：有形狀但沒有面積，沒有面積意味著只要用一串?dāng)?shù)據(jù)表達(dá)每個線狀地物的路徑即可，將該線狀地物經(jīng)過的所有柵格的地址全部記錄下來。仿照矢量數(shù)據(jù)組織的鏈狀雙重獨立式編碼，以弧段為記錄單位。,3）面狀地物的數(shù)據(jù)結(jié)構(gòu)：,弧段文件,邊界弧段--形狀,帶指針的二維行程碼 面
21、域,葉結(jié)點的屬性值改為指向該地物的下一個子塊的循環(huán)指針。,循環(huán)指針指向該地物下一個子塊的地址碼，并在最后指向該地物本身。,只要進(jìn)入第一塊就可以順著指針直接提取該地物的所有子塊，從而避免像柵格數(shù)據(jù)那樣為查詢某一個目標(biāo)需遍歷整個矩陣，大大提高了查詢速度。,4）復(fù)雜地物的數(shù)據(jù)結(jié)構(gòu)：,由幾個或幾種點、線、面狀簡單地物組成的地物稱為復(fù)雜地物。例如將一條公路上的中心線、交通燈、立交橋等組合為一個復(fù)雜地物，用一個標(biāo)識號表示。,矢量和柵格的轉(zhuǎn)換矢量柵格,點和線地物柵格 根據(jù)點或線的某個屬性對相應(yīng)柵格點進(jìn)行賦值。,多邊形 需要進(jìn)行填充，填充則要基于點和多邊形的空間關(guān)系判斷 掃描線算法（相切的情形需要區(qū)分）
22、,基于拓?fù)涠噙呅蔚倪吔绱鷶?shù)算法,柵格到矢量的轉(zhuǎn)換,將每個柵格點視為一個方形區(qū)域 因此，總是轉(zhuǎn)換得到多邊形地物 思路：區(qū)分不同的節(jié)點和邊界類型（及2*2柵格區(qū)域內(nèi)柵格數(shù)值的組合）,節(jié)點,邊界點,2.5 三維數(shù)據(jù)結(jié)構(gòu),目前計算機地圖制圖主要還停留在處理地球表面的數(shù)據(jù)，若數(shù)據(jù)是地表以下或以上，則先將它投影到地表，再進(jìn)行處理，其實質(zhì)是以二維的形式來模擬、處理任何數(shù)據(jù)，在有些領(lǐng)域可行，但涉及到三維問題的處理時，往往力不從心。 二維V=f(x,y)在不同的層V的含義不同，當(dāng)V表示的是高程時，就是DEM。,真三維模型V=f(x,y,z)，z是一自變量，不受x,y的影響。在數(shù)據(jù)采集，系統(tǒng)維護(hù)和界面設(shè)計等方面
23、比二維復(fù)雜得多，同樣，三維結(jié)構(gòu)存在柵格和矢量兩種形式。 柵格：將地理實體的三維空間分成細(xì)小單元---體元。普遍用八叉樹。 矢量：x,y,z，抽象為點、線、面、體，面構(gòu)成體。方法多種，常用三維邊界表示法。,2.5.2 八叉樹： 1）思想：四叉樹在三維空間的推廣。 將要表示的形體V放在一個充分大的正方體C內(nèi)，C的邊長為2n，不斷用兩個與XOY、XOZ的平面均分C為8個子體，并判斷屬性單一性。,2）存儲結(jié)構(gòu)：,規(guī)則八叉樹 與常規(guī)四叉樹類似，用10項字段來記錄每個結(jié)點（8個子結(jié)點指針， 1個父結(jié)點指針，1個結(jié)點屬性）。,線性八叉樹 用某一預(yù)先確定的次序?qū)瞬鏄滢D(zhuǎn)換成線性表，表中的每個元素與一個結(jié)點相
24、對應(yīng)。每個結(jié)點用固定的字節(jié)描述，其中某些位專門用來說明它是否為葉結(jié)點。,特點：節(jié)省存貯空間，便于某些運算，但喪失一定的靈活性，不便于其它遍歷方式對樹的結(jié)點進(jìn)行存取，應(yīng)用效果不佳。,一對八式八叉樹,每個結(jié)點均1分為8，并標(biāo)記為0，1，2，3，4，5，6，7。隱含地假定了這些子結(jié)點記錄存放的次序---便于檢索但浪費存儲，除非完全八叉樹，即所有葉結(jié)點均在同一層次出現(xiàn)，上層均為非葉結(jié)點。,2.5.3 三維邊界表示法,6、拓?fù)錂z查,數(shù)據(jù)存儲后，必須檢查數(shù)據(jù)的一致性、完全性。 (1)頂點表中每個頂點至少是兩條邊的端點； (2)每條邊至少是一個多邊形的邊； (3)每個多邊形是封閉的； (4)每個多邊形至少有
25、一條邊是和另一個多邊形共用的； (5)若邊表中包含了指向它所屬多邊形的指針，則指向該邊的指針必在相應(yīng)的多邊形中。,7、應(yīng)用,三維邊界法一般用于表示規(guī)則形體，對于自然界中的復(fù)雜形體，理論上可找到在誤差范圍內(nèi)逼近的適合多面體，但受多因素的制約。 對于不規(guī)則形體，可在形體的外表面測一組點p1,p2的坐標(biāo)再建這些點的關(guān)系，決定頂點連接的不同方式。同一組點可得到不同的平面多面體。需研究擁有了哪些特征才能更確切地逼近原來的三維形體。,這種逼近有兩種形式： 表面S0的逼近：以確定后的平面多面體的表面作為對原三維形體的表面S0的逼近，著眼于形體的邊界表示。 三維形體的逼近：給出一系列的四面體，這些四面體的集合就是對原三維形體的逼近。著眼于形體的分解表示。,作業(yè)：,1. 空間數(shù)據(jù)有那些基本特征？ 2.利用關(guān)系表來表達(dá)下圖的空間拓?fù)潢P(guān)系。,3. 比較矢量和柵格數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點？ 4.建立下面柵格矩陣的游程編碼結(jié)構(gòu)。,
計算機地圖制圖(中國礦業(yè)大學(xué)課件)2數(shù)據(jù)結(jié)構(gòu).ppt
