1、,空間數(shù)據(jù)結(jié)構(gòu),返回,返回,-1空間實(shí)體及其描述,GIS 數(shù)據(jù)結(jié)構(gòu),一、地理實(shí)體（空間實(shí)體）-GIS處理對象,1、定義： 指自然界現(xiàn)象和社會(huì)經(jīng)濟(jì)事件中不能再分割的單元，它是一個(gè)具體有概括性，復(fù)雜性，相對意義的概念。 2、理解： 地理實(shí)體類別及實(shí)體內(nèi)容的確定是從具體需要出發(fā)的，例如，在全國地圖上由于比例尺很小，武漢就是一個(gè)點(diǎn)，這個(gè)點(diǎn)不能再分割，可以把武漢定為一個(gè)空間實(shí)體，而在大比例尺的武漢市地圖上，武漢的許多房屋，街道都要表達(dá)出來，所以武漢必須再分割，不能作為一個(gè)空間實(shí)體，應(yīng)將房屋，街道等作為研究的地理實(shí)體，由此可見，GIS中的空間實(shí)體是一個(gè)概括，復(fù)雜，相對的概念。,返回,二、地理實(shí)體的描述空間

2、數(shù)據(jù),-1空間實(shí)體及其描述,GIS 數(shù)據(jù)結(jié)構(gòu),1、描述的內(nèi)容,反映了實(shí)體的三個(gè)特征,3、數(shù)據(jù)類型,4、數(shù)據(jù)結(jié)構(gòu),以什么形式存儲(chǔ)和處理,幾何數(shù)據(jù)（空間數(shù)據(jù)、圖形數(shù)據(jù)） 關(guān)系數(shù)據(jù)實(shí)體間的鄰接、關(guān)聯(lián)包含等相互關(guān)系 屬性數(shù)據(jù)各種屬性特征和時(shí)間 元數(shù)據(jù),矢量、柵格、TIN（專用于地表或特殊造型） RDBMS屬性表-采用MIS較成熟,同物理、化學(xué)等學(xué)科使用的數(shù)據(jù)類型相比，空間數(shù)據(jù)是一種較復(fù)雜的數(shù)據(jù)類型，涉及到空間特征、屬性特征及它們之間關(guān)系的描述,空間元數(shù)據(jù),返回,位置、形狀、尺寸 、 識(shí)別碼（名稱）實(shí)體的角色、功能、行為、實(shí)體的衍生信息 時(shí)間 測量方法、編碼方法、空間參考系等,空間特征：地理位置和空間關(guān)

3、系 屬性特征名稱、等級、類別等 時(shí)間特征,2、基本特征,2、空間數(shù)據(jù)基本特征,返回,3、空間數(shù)據(jù)類型,1）依據(jù)數(shù)據(jù)來源的不同分為： 地圖數(shù)據(jù) 地形數(shù)據(jù) 屬性數(shù)據(jù) 元數(shù)據(jù) 影象數(shù)據(jù),2）依據(jù)表示對象的不同分為：,3、空間數(shù)據(jù)類型（續(xù)）,返回,三、實(shí)體的空間特征,-1空間實(shí)體及其描述,GIS 數(shù)據(jù)結(jié)構(gòu),（一）空間維數(shù)：有0，1，2，3 維之分，點(diǎn)、線、面、體。,（二）空間特征類型,（三）實(shí)體類型組合,返回,在地圖上實(shí)體維數(shù)的表示可以改變 點(diǎn)-面 線（單線河）-面（雙線河），通過地圖綜合。,1、點(diǎn)狀實(shí)體,2、線狀實(shí)體,3、面狀實(shí)體,4、體狀實(shí)體,1、點(diǎn)狀實(shí)體,2-1空間實(shí)體及其描述,第二章 GIS

4、數(shù)據(jù)結(jié)構(gòu),點(diǎn)或節(jié)點(diǎn)、點(diǎn)狀實(shí)體。點(diǎn)：有特定位置，維數(shù)為0的物體。,4）角點(diǎn)、節(jié)點(diǎn)Vertex： 表示線段和弧段上的連接點(diǎn)。,1）實(shí)體點(diǎn)：用來代表一個(gè)實(shí)體。,2）注記點(diǎn)：用于定位注記。,3）內(nèi)點(diǎn)：用于負(fù)載多邊形的屬性，存在于多邊形內(nèi)。,返回,2、線狀實(shí)體,1）實(shí)體長度： 從起點(diǎn)到終點(diǎn)的總長 2）彎曲度： 用于表示像道路拐彎時(shí)彎曲的程度。 3）方向性： 如：水流方向，上游下游， 公路，單、雙向之分。,2-1空間實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),具有相同屬性的點(diǎn)的軌跡，線或折線，由一系列的有序坐標(biāo)表示，并有如下特性：,線狀實(shí)體包括： 線段，邊界、鏈、弧段、網(wǎng)絡(luò)等。,返回,3、面狀實(shí)體（多邊形）,

5、2-1空間實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),面狀實(shí)體的如下特征： 1）面積范圍 2）周長 3）獨(dú)立性或與其它地物相鄰 如中國及其周邊國家 4）內(nèi)島嶼或鋸齒狀外形： 如島嶼的海岸線封閉所圍成的區(qū)域。 5）重疊性與非重疊性： 如學(xué)校的分區(qū)，菜市場的服務(wù)范圍等都有可能出現(xiàn)交叉重疊現(xiàn)象，而一個(gè)城市的各個(gè)城區(qū)一般說來不會(huì)出現(xiàn)重疊。,是對湖泊、島嶼、地塊等一類現(xiàn)象的描述。 在數(shù)據(jù)庫中由一封閉曲線加內(nèi)點(diǎn)來表示。,返回,4、體、立體狀實(shí)體,2-1空間實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,立體狀實(shí)體用于描述三維空間中的現(xiàn)象與物體，它具有長度、寬度及高度等屬性，立體狀實(shí)體一般具有以下一些空間特征：

6、體積，如工程開控和填充的土方量。 每個(gè)二維平面的面積。 周長。 內(nèi)島。 含有弧立塊或相鄰塊。 斷面圖與剖面圖。,（三）實(shí)體類型組合,2-1空間實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,現(xiàn)實(shí)世界的各種現(xiàn)象比較復(fù)雜，往往由不同的空間單元組合而成，例如根據(jù)某些空間單元或幾種空間單元的組合將空間問題表達(dá)出來，復(fù)雜實(shí)體由簡單實(shí)體組合表達(dá)。 點(diǎn)、線、面兩兩之間組合表達(dá)復(fù)雜的空間問題： 如：線面 面-面,可見，用各要素之間的空間關(guān)系，可描述諸多空間問題?？臻g關(guān)系是GIS數(shù)據(jù)描述和表達(dá)的重要內(nèi)容，一方面它為GIS數(shù)據(jù)庫的有效建立，空間查詢，空間分析，輔助決策等提供了最基本的關(guān)系，另一方面有助于形成標(biāo)準(zhǔn)的S

7、QL空間查詢語言，便于空間特征的存儲(chǔ)，提取，查詢，更新等。,線面,2-1空間實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、區(qū)域包含線：計(jì)算區(qū)域內(nèi)線的密度，某省的水系分布情況。 2、線通過區(qū)域：公路上否通過某縣。 3、線環(huán)繞區(qū)域：區(qū)域邊界，搜索左右區(qū)域名稱，中國與哪些國家接壤。 4、線與區(qū)域分離：距離。,面面,2-1空間實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、 包含：島,某省的湖泊分布。 2、 相合：重疊，學(xué)校服務(wù)范圍與菜場服務(wù)范圍重疊區(qū)。 3、 相交：劃分子區(qū)。 4、 相鄰：計(jì)算相鄰邊界性質(zhì)和長度，公共連接邊界。 分離：計(jì)算距離。,返回,四、實(shí)體間空間關(guān)系,2-1空間實(shí)體及其描述,第二

8、章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,（一）空間關(guān)系類型,（二）拓?fù)潢P(guān)系,1、 拓?fù)淇臻g關(guān)系： 2、 順序空間關(guān)系： （方向空間關(guān)系） 用上下左右、前后、東南西北等方向性名稱來描述空間實(shí)體的順序關(guān)系，算法復(fù)雜，至今沒有很好的解決方法。 3、 度量空間關(guān)系，主要指實(shí)體間的距離關(guān)系，遠(yuǎn)近。 1）在地理空間中兩點(diǎn)間的距離有兩種度量方法。 a、沿真實(shí)的地球表面進(jìn)行,除與兩點(diǎn)的地理坐標(biāo)有關(guān)外，還與所通過路徑的地形起伏有關(guān)，復(fù)雜,引入第二種。 b、沿地球旋轉(zhuǎn)橢球體的距離量算。 2）距離類別： 歐氏距離（笛卡爾坐標(biāo)系）、曼哈頓（出租車）距離、時(shí)間距離（緯度差）、大地測量距離（大地線）（沿地球大圓經(jīng)過兩個(gè)城市中心的距離

9、）。,（二）拓?fù)潢P(guān)系,2-1空間實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、定義： 指圖形保持連續(xù)狀態(tài)下變形，但圖形關(guān)系不變的性質(zhì)。 將橡皮任意拉伸，壓縮，但不能扭轉(zhuǎn)或折疊。,1、定義 2、種類 3、拓?fù)潢P(guān)系的表達(dá) 4、意義,2、種類,2-1空間實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1）關(guān)聯(lián)性： （不同類要素之間）結(jié)點(diǎn)與弧段：如V9與L5,L6,L3 多邊形與弧段：P2與L3,L5,L2 2）鄰接性： (同類元素之間) 多邊形之間、結(jié)點(diǎn)之間。 鄰接矩陣 重疊：- 鄰接：1 不鄰接：0,3）連通性：與鄰接性相類似，指對弧段連接的判別，如用于網(wǎng)絡(luò)分析中確定路徑、 街道是否相通。,2-1空間

10、實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),連通矩陣： 重疊：- 連通：1 不連通：0,4）方向性,2-1空間實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),一條弧段的起點(diǎn)、終點(diǎn)確定了弧段的方向。用于表達(dá)現(xiàn)實(shí)中的有向弧段，如城市道路單向，河流的流向等。 5）包含性：指面狀實(shí)體包含了哪些線、點(diǎn)或面狀實(shí)體。 6）區(qū)域定義：多邊形由一組封閉的線來定義。 7）層次關(guān)系：相同元素之間的等級關(guān)系，武漢市有各個(gè)區(qū)組成。 主要的拓?fù)潢P(guān)系：拓?fù)溧徑?、拓?fù)潢P(guān)聯(lián)、拓?fù)浒?拓?fù)潢P(guān)系具體可由4個(gè)關(guān)系表來表示： （1） 面-鏈關(guān)系： 面 構(gòu)成面的弧段 （2） 鏈-結(jié)點(diǎn)關(guān)系： 鏈 鏈兩端的結(jié)點(diǎn) （3） 結(jié)點(diǎn)-鏈關(guān)系： 結(jié)點(diǎn) 通過該

11、結(jié)點(diǎn)的鏈 （4） 鏈面關(guān)系： 鏈 左面 右面,3、拓?fù)潢P(guān)系的表達(dá),對于數(shù)據(jù)處理和GIS空間分析具有重要的意義，因?yàn)椋?1）拓?fù)潢P(guān)系能清楚地反映實(shí)體之間的邏輯結(jié)構(gòu)關(guān)系，它比幾何關(guān)系具有更大的穩(wěn)定性，不隨地圖投影而變化。 2）有助于空間要素的查詢，利用拓?fù)潢P(guān)系可以解決許多實(shí)際問題。如某縣的鄰接縣，-面面相鄰問題。又如供水管網(wǎng)系統(tǒng)中某段水管破裂找關(guān)閉它的閥門，就需要查詢該線（管道）與哪些點(diǎn)（閥門）關(guān)聯(lián)。 3）根據(jù)拓?fù)潢P(guān)系可重建地理實(shí)體。,2-1空間實(shí)體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,4、拓?fù)潢P(guān)系的意義：,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,柵格結(jié)構(gòu)用密集正方形（或三角形，

12、多邊形）將地理區(qū)域劃分為網(wǎng)格陣列。 位置由行，列號(hào)定義，屬性為柵格單元的值。,一、圖形表示,點(diǎn)：由單個(gè)柵格表達(dá)。 線：由沿線走向有相同屬性取值的一組相鄰柵格表達(dá)。 面：由沿線走向有相同屬性取值的一片柵格表達(dá)。 柵格數(shù)據(jù)表示的是二維表面上的地理數(shù)據(jù)的離散化數(shù)值。在柵格數(shù)據(jù)中，地表被分割為相互鄰接、規(guī)則排列的地塊，每個(gè)地塊與一個(gè)象元相對應(yīng)。因此，柵格數(shù)據(jù)的比例尺就是柵格(象元)的大小與地表相應(yīng)單元的大小之比，當(dāng)象元所表示的面積較大時(shí)，對長度、面積等的量測有較大影響。每個(gè)象元的屬性是地表相應(yīng)區(qū)域內(nèi)地理數(shù)據(jù)的近似值，因而有可能產(chǎn)生屬性方面的偏差。,二、柵格數(shù)據(jù)組織,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS

13、 數(shù)據(jù)結(jié)構(gòu),返回,針對一個(gè)柵格單元對應(yīng)多個(gè)屬性值的多層?xùn)鸥裎募?組織方法,組織方法,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,方法c：以層為基礎(chǔ)，每層內(nèi)以多邊形為序記錄多邊形的屬性值和多邊形內(nèi)各象元的坐標(biāo)。節(jié)約用于存儲(chǔ)屬性的空間。將同一屬性的制圖單元的n個(gè)象元的屬性只記錄一次，便于地圖分析和制圖處理。,方法a：以象元為記錄序列，不同層上同一象元位置上的各屬性值表示為一個(gè)列數(shù)組。N層中只記錄一層的象元位置，節(jié)約大量存儲(chǔ)空間，柵格個(gè)數(shù)很多。,方法b：每層每個(gè)象元的位置、屬性一一記錄，結(jié)構(gòu)最簡單，但浪費(fèi)存儲(chǔ)。,三、柵格結(jié)構(gòu)的建立,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1

14、、 手工獲取，專題圖上劃分均勻網(wǎng)格，逐個(gè)決定其網(wǎng)格代碼。 2、掃描儀掃描專題圖的圖像數(shù)據(jù)行、列、顏色（灰度），定義顏色與屬性對應(yīng)表，用相應(yīng)屬性代替相應(yīng)顏色，得到（行、列、屬性）再進(jìn)行柵格編碼、存貯，即得該專題圖的柵格數(shù)據(jù)。 3、 由矢量數(shù)據(jù)轉(zhuǎn)換而來。 4、 遙感影像數(shù)據(jù)，對地面景象的輻射和反射能量的掃描抽樣，并按不同的光譜段量化后，以數(shù)字形式記錄下來的象素值序列。 5、 格網(wǎng)DEM數(shù)據(jù)，當(dāng)屬性值為地面高程，則為格網(wǎng)DEM，通過DEM內(nèi)插得到。,（一）建立途徑,（二）柵格系統(tǒng)的確定,(三)柵格代碼的確定,（二）柵格系統(tǒng)的確定,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、 柵格坐標(biāo)系的確定

15、 表示具有空間分布特征的地理要素，不論采用什么編碼系統(tǒng)，什么數(shù)據(jù)結(jié)構(gòu)(矢、柵)都應(yīng)在統(tǒng)一的坐標(biāo)系統(tǒng)下，而坐標(biāo)系的確定實(shí)質(zhì)是坐標(biāo)系原點(diǎn)和坐標(biāo)軸的確定。 由于柵格編碼一般用于區(qū)域性GIS，原點(diǎn)的選擇常具有局部性質(zhì)，但為了便于區(qū)域的拼接，柵格系統(tǒng)的起始坐標(biāo)應(yīng)與國家基本比例尺地形圖公里網(wǎng)的交點(diǎn)相一致，并分別采用公里網(wǎng)的縱橫坐標(biāo)軸作為柵格系統(tǒng)的坐標(biāo)軸。,2、 柵格單元的尺寸,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1）原則：應(yīng)能有效地逼近空間對象的分布特征，又減少數(shù)據(jù)的冗余度。 格網(wǎng)太大，忽略較小圖斑，信息丟失。 一般講實(shí)體特征愈復(fù)雜，柵格尺寸越小，分辨率愈高，然而柵格數(shù)據(jù)量愈大（按分辨率

16、的平方指數(shù)增加）計(jì)算機(jī)成本就越高，處理速度越慢。 2）方法：用保證最小多邊形的精度標(biāo)準(zhǔn)來確定尺寸經(jīng)驗(yàn)公式： h為柵格單元邊長 Ai為區(qū)域所有多邊形的面積。,(三)柵格代碼（屬性值）的確定,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,當(dāng)一個(gè)柵格單元內(nèi)有多個(gè)可選屬性值時(shí)，按一定方法來確定柵格屬性值。 1、中心點(diǎn)法：取位于柵格中心的屬性值為該柵格的屬性值。 2、面積占優(yōu)法：柵格單元屬性值為面積最大者，常用于分類較細(xì)，地理類別圖斑較小時(shí)。 3、 重要性法：定義屬性類型的重要級別，取重要的屬性值為柵格屬性值，常用于有重要意義而面積較小的要素，特別是點(diǎn)、線地理要素。 4、長度占優(yōu)法每個(gè)柵格單元的

17、值由該柵格中線段最長的實(shí)體的屬性來確定。,A,B,b,a,a,2,1,四、柵格數(shù)據(jù)編碼方法,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、直接?xùn)鸥窬幋a： 將柵格數(shù)據(jù)看作一個(gè)數(shù)據(jù)矩陣，逐行記錄代碼數(shù)據(jù)。 1）每行都從左到右記錄； AAAAABBBAABBAABB 2）奇數(shù)行從左到右，偶數(shù)行從右到左； 特點(diǎn)：最直觀、最基本的網(wǎng)格存貯結(jié)構(gòu)，沒有進(jìn)行任何壓縮數(shù)據(jù)處理。,A A A A A B B B A A B B A A B B,柵格數(shù)據(jù)量大，格網(wǎng)數(shù)多，由于地理數(shù)據(jù)往往有較強(qiáng)的相關(guān)性，即相鄰象元的值往往是相同的。所以，出現(xiàn)了各種柵格數(shù)據(jù)壓縮方法。 數(shù)據(jù)壓縮是將數(shù)據(jù)表示成更緊湊的格式以減少

18、存儲(chǔ)空間的一項(xiàng)技術(shù)。分為： 無損壓縮：在編碼過程中信息沒有丟失，經(jīng)過解碼可恢復(fù)原有的信息-信息 保持編碼。 有損壓縮：為最大限度壓縮數(shù)據(jù)，在編碼中損失一些認(rèn)為不太重要的信息，解碼后，這部分信息無法恢復(fù)。-信息不保持編碼。,2、行程編碼（變長編碼）：,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,將原圖表示的數(shù)據(jù)矩陣變?yōu)閿?shù)據(jù)對： 1）屬性碼，長度，行號(hào)（可不要） 長度：連續(xù)相同碼值的柵格個(gè)數(shù)。 2）屬性碼，點(diǎn)位,特點(diǎn)： 對于游程長度編碼，區(qū)域越大，數(shù)據(jù)的相關(guān)性越強(qiáng)，則壓縮越大，適用于類型區(qū)域面積較大的專題圖，而不適合于類型連續(xù)變化或類別區(qū)域分散的分類圖（壓縮比與圖的復(fù)雜程度成反比）。 這

19、種編碼在柵格加密時(shí)，數(shù)據(jù)量不會(huì)明顯增加，壓縮率高，并最大限度地保留原始柵格結(jié)構(gòu)，編碼解碼運(yùn)算簡單，且易于檢索，疊加，合并等操作，這種編碼應(yīng)用廣泛。,A A A A A B B B A A B B A A B B,3、塊碼 - 游程編碼向二維擴(kuò)展,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,采用方形區(qū)域作為記錄單元，每個(gè)記錄單元包括相鄰的若干柵格。,數(shù)據(jù)對組成：（初始行、列，半徑，屬性值）,特點(diǎn)： 具有可變分辨率，即當(dāng)屬性變化小時(shí)圖塊大，對于大塊圖斑記錄單元大，分辨率低，壓縮比高。 小塊圖斑記錄單元小，分辨率高，壓縮比低 所以，與行程編碼類似，隨圖形復(fù)雜程度的提高而降低分辯率。,依次掃

20、描，編過的不重復(fù)。,1 2 3 4 5 6 7 8 1 0 4 4 7 7 7 7 7 2 4 4 4 4 4 7 7 7 3 4 4 4 4 8 8 7 7 4 0 0 4 8 8 8 7 7 5 0 0 8 8 8 8 7 8 6 0 0 0 8 8 8 8 8 7 0 0 0 0 8 8 8 8 8 0 0 0 0 0 8 8 8,如：（1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),4、鏈?zhǔn)骄幋a、Freeman 鏈碼、邊界鏈碼,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1）首先定義一個(gè)3x3窗口，中間柵格的走向有8種可能，并將這8種可能07進(jìn)行

21、編碼。 2）記下地物屬性碼和起點(diǎn)行、列后，進(jìn)行追蹤，得到矢量鏈.,將柵格數(shù)據(jù)（線狀地物面域邊界）表示為矢量鏈的記錄,鏈?zhǔn)骄幋a表,a,a,a,a,a,a,b,優(yōu)點(diǎn)：鏈碼可有效地存貯壓縮柵格數(shù)據(jù)，便于面積、長度、轉(zhuǎn)折方向和邊界、線段凹凸度的計(jì)算。 缺點(diǎn)：不易做邊界合并，插入操作、編輯較困難（對局部修改將改變整體結(jié)構(gòu)）。區(qū)域空間分析困難，相鄰區(qū)域邊界被重復(fù)存儲(chǔ)。,5、四叉樹編碼,五、四叉樹編碼,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、 基本思想： 將2n2n象元組成的圖像(不足的用背景補(bǔ)上) 按四個(gè)象限進(jìn)行遞歸分割， 并判斷屬性是否單一， 單一：不分。 不單一：遞歸分割。 最后得到

22、一顆四分叉的倒向樹。 2、 四叉樹的樹形表示： 用一倒立樹表示這種分割和分割結(jié)果。 根：整個(gè)區(qū)域 高：深度、分幾級，幾次分割 葉：不能再分割的塊 樹叉：還需分割的塊 每個(gè)樹叉均有4個(gè)分叉，叫四叉樹。,（一）四叉樹概述： 一種可變分率的非均勻網(wǎng)格系統(tǒng)。是最有效的柵格數(shù)據(jù)壓縮編碼方法之一,3、 編碼方法,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1）常規(guī)四叉樹 記錄這棵樹的葉結(jié)點(diǎn)外，中間結(jié)點(diǎn)，結(jié)點(diǎn)之間的聯(lián)系用指針聯(lián)系， 每個(gè)結(jié)點(diǎn)需要6個(gè)變量： 父結(jié)點(diǎn)指針、四個(gè)子結(jié)點(diǎn)的指針和本結(jié)點(diǎn)的屬性值。,指針不僅增加了數(shù)據(jù)的存儲(chǔ)量，還增加了操作的復(fù)雜性：如層次數(shù)（分割次數(shù)）由從父結(jié)點(diǎn)移到根結(jié)點(diǎn)的次數(shù)

23、來確定，結(jié)點(diǎn)所代表的圖像塊的位置需要從根節(jié)點(diǎn)開始逐步推算下來。所以，常規(guī)四叉樹并不廣泛用于存儲(chǔ)數(shù)據(jù)，其價(jià)值在于建立索引文件，進(jìn)行數(shù)據(jù)檢索。,2）線性四叉樹,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,記錄葉結(jié)點(diǎn)的位置，深度（幾次分割）和屬性。 地址碼（定位碼、Morton碼） 四進(jìn)制、十進(jìn)制 優(yōu)點(diǎn)： 存貯量小，只對葉結(jié)點(diǎn)編碼，節(jié)省了大量中間結(jié)點(diǎn)的存儲(chǔ)，地址碼隱含著結(jié)點(diǎn)的分割路徑和分割次數(shù)。 線性四叉樹可直接尋址，通過其坐標(biāo)值直接計(jì)算其Morton碼，而不用建立四叉樹。 定位碼容易存儲(chǔ)和執(zhí)行實(shí)現(xiàn)集合相加等組合操作。,（二）四進(jìn)制的Morton碼,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)

24、據(jù)結(jié)構(gòu),返回,1、 方法1： 四叉樹從上而下（形成）（從整體開始） 由葉結(jié)點(diǎn)找Morton碼。 A、分割一次，增加一位數(shù)字，大分割在前，小分割在后。所以，碼的位數(shù)表示分割的次數(shù)。 B、每一個(gè)位均是不大于3的四進(jìn)制數(shù)，表達(dá)位置。 由Morton找出四叉樹葉結(jié)點(diǎn)的具體位置。,03,B,A,2、 方法2：四叉樹自下而上合并的方法,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1）計(jì)算每個(gè)柵格對應(yīng)的MQ MQ=2*Ib+Jb I,J化為二進(jìn)制Ib,Jb 看最大的I,J,不足在前補(bǔ)零。 其始行列號(hào)從0計(jì)。 2) 按碼的升序排成線性表，放在連續(xù)的內(nèi)存塊中。 3）依次檢查每四個(gè)相鄰的MQ對應(yīng)的屬性值

25、，相同合并（不同碼位去掉），不同則存盤,直到?jīng)]有能夠合并的子塊為止。,（三）十進(jìn)制的Morton碼-MD,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、一種按位操作的方法： 如行為2、列為3的柵格的MD 步驟： (1)行、列號(hào)為二進(jìn)制 Ib= 1 0 Jb= 1 1 (2)I行J列交叉 1 1 0 1 = 13 (3)再化為十進(jìn)制. 實(shí)質(zhì)上是按左上、右上、左下、右下的順序，從零開始對每個(gè)柵格進(jìn)行自然編碼。,四進(jìn)制Morton碼直觀上切合四叉樹分割，但許多語言不支持四進(jìn)制變量，需用十進(jìn)制表示Morton碼.,2、把一幅2n2n的圖像壓縮成線性四叉樹的過程,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章

26、 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、按Morton碼把圖象讀入一維數(shù)組。 2、相鄰的四個(gè)象元比較，一致的合并，只記錄第一個(gè)象元的Morton碼。循環(huán)比較所形成的大塊，相同的再合并，直到不能合并為止。 3、進(jìn)一步用游程長度編碼壓縮。壓縮時(shí)只記錄第一個(gè)象元的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 A B B B A A A A B B B B 2、四相鄰象元合并，只記錄第一個(gè)象元的Morton碼。 0 1 2 3 4 5 6 7 8 12 A A

27、 A B A A B B A B 3、由于不能進(jìn)一步合并，則用游程長度編碼壓縮。 0 3 4 6 8 12 A B A B A B,（四）四叉樹優(yōu)缺點(diǎn),2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),優(yōu)點(diǎn)： 1）對于團(tuán)塊圖像，四叉樹表示法占用空間比網(wǎng)絡(luò)法要少得多，四叉樹表示法基本上是一種非冗余表示法。 2）四叉樹具有可變率或多重分辯率的特點(diǎn)使得它有很好的應(yīng)用前景，適用于處理凝聚性或呈塊狀分布的空間數(shù)據(jù)，特別適用于處理分布不均勻的塊狀空間數(shù)據(jù)，但不適用于連續(xù)表面（如地形）或線狀地物。 此外，目前應(yīng)用四叉樹還存下列問題： 1) 矢/柵正反變換還不理想。 2) 建立四叉樹耗費(fèi)機(jī)時(shí)很多。 3) 四叉樹

28、雖可修改，但很費(fèi)事（具體的數(shù)據(jù)結(jié)構(gòu)中會(huì)提到）,4) 四叉樹未能直接表示物體間的拓?fù)潢P(guān)系。,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,5) 與非樹表示法比較，四叉樹表示法的缺點(diǎn)在于轉(zhuǎn)換的不穩(wěn)定性或叫滑動(dòng)變異 例如，兩個(gè)圖像的差異僅由于平移，就會(huì)構(gòu)成極為不同的四叉樹，因而很難根據(jù)四叉樹來判斷這兩個(gè)圖像是否全同，故不利于做形狀分析和模式識(shí)別，,6) 一個(gè)物體的圖像在構(gòu)成四叉樹時(shí)會(huì)被分割到若干個(gè)象限中，使它失去了內(nèi)在的相關(guān)性。,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),一、圖形表示,返回,摘自 張超,二、矢量數(shù)據(jù)的獲取方式,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1) 由外業(yè)

29、測量獲得 可利用測量儀器自動(dòng)記錄測量成果(常稱為電子手薄)，然后轉(zhuǎn)到地理數(shù)據(jù)庫中。 2)由柵格數(shù)據(jù)轉(zhuǎn)換獲得 利用柵格數(shù)據(jù)矢量化技術(shù)，把柵格數(shù)據(jù)轉(zhuǎn)換為矢量數(shù)據(jù)。 3)跟蹤數(shù)字化 用跟蹤數(shù)字化的方法，把地圖變成離散的矢量數(shù)據(jù)。,返回,三、矢量數(shù)據(jù)組織,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),矢量數(shù)據(jù)表示時(shí)應(yīng)考慮以下問題： 矢量數(shù)據(jù)自身的存貯和處理。 與屬性數(shù)據(jù)的聯(lián)系。 矢量數(shù)據(jù)之間的空間關(guān)系(拓?fù)潢P(guān)系)。,以點(diǎn)為例：,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),坐標(biāo) 識(shí)別符 若是簡單點(diǎn)要素如獨(dú)立樹、電線竿、三角點(diǎn)，符號(hào)、 有關(guān)屬性中包括 比例尺、方向 若是注記點(diǎn)，記錄有關(guān)字符的大小、方

30、向、字體、排列等 若是結(jié)點(diǎn)Vertex：符號(hào)：指針、與線相交的角度。 其它屬性 : 三角點(diǎn)設(shè)立年代、材料等,線（符號(hào)、方向）、面（符號(hào)）都有相應(yīng)的相關(guān)屬性，在此，看看矢量結(jié)構(gòu)中關(guān)于幾何位置坐標(biāo)的編碼方式,返回,四、矢量數(shù)據(jù)編碼方式,（spaghetti）- 面條模型:以實(shí)體為單位記錄其坐標(biāo),2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),缺點(diǎn)： 1、相鄰多邊形的公共邊界被數(shù)字化并存儲(chǔ)兩次，造成數(shù)據(jù)冗余和碎屑多邊形數(shù)據(jù)不一致，浪費(fèi)空間，導(dǎo)致雙重邊界不能精確匹配。 2、自成體系，缺少多邊形的鄰接信息，無拓?fù)潢P(guān)系，難以進(jìn)行鄰域處理，如消除多邊形公共邊界，合并多邊形。 3、島作為一個(gè)單個(gè)圖形，沒有與外

31、界多邊形聯(lián)系。不易檢查拓?fù)溴e(cuò)誤。 所以，這種結(jié)構(gòu)只用于簡單的制圖系統(tǒng)中，顯示圖形。,（一）實(shí)體式,優(yōu)點(diǎn)：結(jié)構(gòu)簡單、直觀、易實(shí)現(xiàn)以實(shí)體為單位的運(yùn)算和顯示。,返回,（二）索引式（樹狀）,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),對所有點(diǎn)的坐標(biāo)按順序建坐標(biāo)文件，再建點(diǎn)與邊（線）、線與多邊形的索引文件。,Map,1、點(diǎn)文件：,索引文件：,3、面文件：,2、弧段文件:,與實(shí)體式相比： 優(yōu)點(diǎn)：用建索引的方法消除多邊形數(shù)據(jù)的冗余和不一致，鄰接信息、島信息可在多邊形文件中通過是否公共弧段號(hào)的方式查詢。 缺點(diǎn)：表達(dá)拓?fù)潢P(guān)系較繁瑣，給相鄰運(yùn)算、消除無用邊、處理島信息、檢索拓?fù)潢P(guān)系等帶來困難，以人工方式建立編

32、碼表，工作量大，易出錯(cuò)。,返回,（三）雙重獨(dú)立式編碼,簡稱DIME(Dual Independent Map Encoding)，是美國人口統(tǒng)計(jì)系統(tǒng)采用的一種編碼方式，是一種拓?fù)渚幋a結(jié)構(gòu)。,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、點(diǎn)文件,2、線文件:線文件是以線段為記錄單位,3、面文件,關(guān)聯(lián),鄰接,關(guān)聯(lián),連通,拓?fù)潢P(guān)系明確,在DIME中做如下改進(jìn)： 將以線段為記錄單位改為以弧段為單位,鏈狀雙重獨(dú)立式編碼,返回,（四）鏈狀雙重獨(dú)立式編碼-拓?fù)鋽?shù)據(jù)結(jié)構(gòu),2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、弧段坐標(biāo)文件：,2、弧段文件：鏈面，鏈結(jié)點(diǎn)關(guān)系,3、面文件,4、點(diǎn)拓?fù)湮募?結(jié)點(diǎn)

33、鏈關(guān)系,在拓?fù)浣Y(jié)構(gòu)中，多邊形（面）的邊界被分割成一系列的線（弧、鏈、邊）和點(diǎn)（結(jié)點(diǎn)）等拓?fù)湟?，點(diǎn)、線、面之間的拓?fù)潢P(guān)系在屬性表中定義，多邊形邊界不重復(fù)。,返回,鏈狀雙重獨(dú)立式編碼 特點(diǎn),拓?fù)潢P(guān)系明確，也能表達(dá)島信息，而且以弧段為記錄單位，滿足實(shí)際應(yīng)用需要。因?yàn)橐话銛?shù)字化一條街道時(shí)，必然有許多中間點(diǎn)，但我們在做空間分析是卻沒有必要以這些中間點(diǎn)所組成的折線為研究對象，而應(yīng)以整條弧段（某條街道）為研究對象. 被一些成熟的商品化軟件采用，如ARC/INFO軟件。 例：ARC文件：二進(jìn)制文件: 弧段號(hào) 點(diǎn)數(shù) 坐標(biāo)串 在GIS數(shù)據(jù)輸入中，建拓?fù)涫侵附o圖形數(shù)據(jù)（點(diǎn)、線、面）增加拓?fù)浣Y(jié)構(gòu)，如ARC/INFO

34、中，在ARCEDIT中輸入圖形后，需用BUILD 建圖形拓?fù)?，具體生成許多文件，如AAT，PAT等. INFO：屬性表 如AAT（Arc Attribute Table）,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),用戶標(biāo)識(shí)碼，表明地物類型 當(dāng)圖形數(shù)據(jù)修改、刪除、增加點(diǎn)、線、面要素后，其拓?fù)潢P(guān)系也發(fā)生改變，所以，需重新建拓?fù)洹?返回,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),一、矢、柵優(yōu)缺點(diǎn)：,矢量、柵格數(shù)據(jù)結(jié)構(gòu)的選擇,柵格結(jié)構(gòu):大范圍小比例尺的自然資源、環(huán)境、農(nóng)林業(yè)等區(qū)域問題的研究。,矢量結(jié)構(gòu)：城市分區(qū)或詳細(xì)規(guī)劃、土地管理、公用事業(yè)管理等方面的應(yīng)用。,在GIS建立過程中，應(yīng)根

35、據(jù)應(yīng)用目的和應(yīng)用特點(diǎn)、可能獲得的數(shù)據(jù)精度以及地理信息系統(tǒng)軟件和硬件配置情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)。,返回,二、矢柵一體化概念,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),將矢量面對目標(biāo)的方法和柵格元子充填的方法結(jié)合起來，具體采用填滿線狀目標(biāo)路徑和充填面狀目標(biāo)空間的方法作為一體化數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。 線狀地物：除記錄原始取樣點(diǎn)外，還記錄路徑所通過的柵格。 面狀地物：除記錄它的多邊形周邊以外，還包括中間的面域柵格。 一方面，它保留了矢量的全部性質(zhì)，以目標(biāo)為單元直接聚集所有的位置信息，并能建立拓?fù)潢P(guān)系； 另一方面，它建立了柵格與地物的關(guān)系，即路徑上的任一點(diǎn)都直接與目標(biāo)建立了聯(lián)系。,從原理上說，這

36、是一種以矢量的方式來組織柵格數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。,返回,三、三個(gè)約定和細(xì)分格網(wǎng)法,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),為便于組織數(shù)據(jù)，首先作如下約定： a. 地面上的點(diǎn)狀地物是地球表面上的點(diǎn)，它僅有空間位置，沒有形狀和面積，在計(jì)算機(jī)內(nèi)部僅有一個(gè)位置數(shù)據(jù)。,為提高柵格表示精度，采用細(xì)分格網(wǎng)法： 將一對X,Y坐標(biāo)用兩個(gè)Morton碼代替： 前一M1表示該點(diǎn)（采樣點(diǎn)或附加的交叉點(diǎn)）所在基本格網(wǎng)的地址碼，后者M(jìn)2 表示該點(diǎn)對應(yīng)的細(xì)分格網(wǎng)的Morton碼，既顧全整體定位，又保證精度。,b. 地面上的線狀地物是地球表面的空間曲線，它有形狀但沒有面積，它在平面上的投影是一連續(xù)不間斷的直線或曲線

37、，在計(jì)算機(jī)內(nèi)部需要用一組元子填滿整個(gè)路徑。,c. 地面上的面狀地物是地球表面的空間曲面，并具有形狀和面積，它在平面上的投影是由邊界包圍的緊致空間和一組填滿路徑的元子表達(dá)的邊界組成。,x,y,M1 M2,返回,四、一體化數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì),2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),線性四叉樹(Morton)是基本數(shù)據(jù)格式，三個(gè)約定設(shè)計(jì)點(diǎn)、線、面數(shù)據(jù)結(jié)構(gòu)的基本依據(jù)，細(xì)分格網(wǎng)法保證足夠精度。,約定1，點(diǎn)僅有位置、沒有形狀和面積，只要將點(diǎn)的坐標(biāo)轉(zhuǎn)化為地址碼M1 和M2 ,結(jié)構(gòu)簡單靈活，便于點(diǎn)的插入和刪除，還能處理一個(gè)柵格內(nèi)包含多個(gè)點(diǎn)狀目標(biāo)的情況。,1、點(diǎn)狀地物和結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu),返回,2、線狀地物

38、的數(shù)據(jù)結(jié)構(gòu),2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),約定（2），線狀地物有形狀但沒有面積，沒有面積意味著只要用一串?dāng)?shù)據(jù)表達(dá)每個(gè)線狀地物的路徑即可，將該線狀地物經(jīng)過的所有柵格的地址全部記錄下來。仿照矢量數(shù)據(jù)組織的鏈狀雙重獨(dú)立式編碼，以弧段為記錄單位。,弧段的數(shù)據(jù)結(jié)構(gòu):,線狀地物的數(shù)據(jù)結(jié)構(gòu):,返回,3、面狀地物的數(shù)據(jù)結(jié)構(gòu),2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1) 弧段文件,2）帶指針的二維行程碼,葉結(jié)點(diǎn)的屬性值,改為指向該地物的下一個(gè)子塊的循環(huán)指針,邊界弧段-形狀,面域,循環(huán)指針指向該地物下一個(gè)子塊的地址碼，并在最后指向該地物本身,返回,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),

39、第二章 GIS 數(shù)據(jù)結(jié)構(gòu),用循環(huán)指針將同屬于一個(gè)目標(biāo)的葉結(jié)點(diǎn)鏈接起來,只要進(jìn)入第一塊就可以順著指針直接提取該地物的所有子塊，從而避免像柵格數(shù)據(jù)那樣為查詢某一個(gè)目標(biāo)需遍歷整個(gè)矩陣，大大提高了查詢速度。,返回,0,8,32,40,46,3）面文件,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),這種數(shù)據(jù)結(jié)構(gòu)是面向地物的，具有矢量的特點(diǎn)。通過面狀地物的標(biāo)識(shí)號(hào)可以找到它的邊界弧段并順著指針提取所有的中間面塊。同時(shí)它又具有柵格的全部特性，二維行程本身就是面向位置的結(jié)構(gòu)，帶指針的二維行程碼中的Morton碼表達(dá)了位置的相互關(guān)系，前后M碼之差隱含了該子塊的大小。給出任意一點(diǎn)的位置都可順著指針找到面狀地

40、物的標(biāo)識(shí)號(hào)確定是哪一個(gè)地物。,返回,4、復(fù)雜地物的數(shù)據(jù)結(jié)構(gòu),2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),由幾個(gè)或幾種點(diǎn)、線、面狀簡單地物組成的地物稱為復(fù)雜地物。例如將一條公路上的中心線、交通燈、立交橋等組合為一個(gè)復(fù)雜地物，用一個(gè)標(biāo)識(shí)號(hào)表示。復(fù)雜地物的數(shù)據(jù)結(jié)構(gòu)如表7所示。,返回,2-5 三維數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),目前GIS主要還停留在處理地球表面的數(shù)據(jù)，若數(shù)據(jù)是地表以下或以上，則先將它投影到地表，再進(jìn)行處理，其實(shí)質(zhì)是以二維的形式來模擬、處理任何數(shù)據(jù)，在有些領(lǐng)域可行，但涉及到三維問題的處理時(shí)，往往力不從心。 二維V=f(x,y)，在不同的層V的含義不同，當(dāng)V表示的是高程時(shí)，

41、就是DEM。由于地形三維視圖的原因，人們常把DEM誤認(rèn)為是三維模型。但從本質(zhì)上講，DEM是二維的，因?yàn)樗荒鼙硎镜乇淼男畔?，不能對地表?nèi)部進(jìn)行有效的表示。目前，人們常把DEM稱為2.5維的數(shù)據(jù)模型。 真三維模型V=f(x,y,z)，z是一自變量，不受x,y的影響。三維GIS的要求與二維GIS相似，但在數(shù)據(jù)采集，系統(tǒng)維護(hù)和界面設(shè)計(jì)等方面比二維GIS復(fù)雜得多，如三維數(shù)據(jù)的組織與重建，三維變換、查詢、運(yùn)算、分析、維護(hù)等方面。下面主要介紹三維數(shù)據(jù)結(jié)構(gòu)。同樣，三維結(jié)構(gòu)存在柵格和矢量兩種形式。 柵格：將地理實(shí)體的三維空間分成細(xì)小單元-體元。普遍用八叉樹 矢量：x,y,z，抽象為點(diǎn)、線、面、體，面構(gòu)成體。方法多種，常用三維邊界表示法。,返回,一、概述,二、八叉樹結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、思想： 四叉樹在三維空間的推廣。 將要表示的形體V放在一個(gè)充分大的正方體C內(nèi)，C的邊長為2n，不斷用兩個(gè)與XOY、XOZ的平面均