空間數(shù)據(jù)的結(jié)構(gòu)與編碼

空間數(shù)據(jù)的結(jié)構(gòu)與編碼第1頁(yè)，共48頁(yè)，2023年，2月20日，星期一3.1空間數(shù)據(jù)及其編碼

1、數(shù)據(jù)空間性的內(nèi)含從數(shù)據(jù)編碼看1）數(shù)據(jù)的空間地理分布特征；

2）非結(jié)構(gòu)化數(shù)據(jù)的特征；3）空間數(shù)據(jù)之間存在著拓?fù)潢P(guān)系；4）空間數(shù)據(jù)是海量數(shù)據(jù)。第2頁(yè)，共48頁(yè)，2023年，2月20日，星期一2、空間數(shù)據(jù)的編碼

第3頁(yè)，共48頁(yè)，2023年，2月20日，星期一3、數(shù)據(jù)編碼的過(guò)程

第4頁(yè)，共48頁(yè)，2023年，2月20日，星期一4、空間物體的幾何類型

（1）點(diǎn)狀分布特征如城鎮(zhèn)、企事業(yè)單位、基地、氣象站、山峰、火山口等。（2）線狀分布特征河流、海岸線、鐵路、公路、地下管線，行政邊界等。（3）面狀分布特征如土壤、森林、草原、沙漠、湖泊等，通常稱多邊形。（4）體狀分布特征如高層建筑、水體、云體、山體、礦體等?？傊臻g現(xiàn)象十分復(fù)雜，為此將其抽象到空間對(duì)象（目標(biāo)）來(lái)表達(dá)空間實(shí)體。第5頁(yè)，共48頁(yè)，2023年，2月20日，星期一3.2空間數(shù)據(jù)的拓?fù)潢P(guān)系

1、描述地理要素空間性的信息：幾何信息、拓?fù)湫畔缀涡畔ⅲɡ碚摶A(chǔ)是幾何學(xué)geometry)用空間坐標(biāo)的位置、方向、角度、距離、面積等信息描述物體的幾何形狀和數(shù)量特征；拓?fù)湫畔ⅲɡ碚摶A(chǔ)是拓?fù)鋵W(xué)topology)用幾何關(guān)系的相連、相鄰、包含等信息描述物體元素之間的關(guān)系；第6頁(yè)，共48頁(yè)，2023年，2月20日，星期一2、拓?fù)鋵W(xué)中空間元素拓?fù)鋵W(xué)是幾何學(xué)的一個(gè)分支，其基本元素：結(jié)點(diǎn)（NOD）：弧段的交點(diǎn)。島結(jié)點(diǎn)是特殊結(jié)點(diǎn)?；《危ˋRC）：相鄰兩結(jié)點(diǎn)之間的坐標(biāo)鏈。島邊界弧段是特殊弧段。多邊形（polygon）（圖斑或面）：有限弧段組成的封閉區(qū)。關(guān)系的性質(zhì)可分為：相鄰、相連、相交、相離、相重、包含等。第7頁(yè)，共48頁(yè)，2023年，2月20日，星期一從拓?fù)浣嵌瓤矗瑤缀涡螤畈煌氖挛锲渫負(fù)潢P(guān)系可能相同

點(diǎn)之間拓?fù)潢P(guān)系（鄰接性）的描述面之間拓?fù)潢P(guān)系（鄰接性）的描述第8頁(yè)，共48頁(yè)，2023年，2月20日，星期一3、空間數(shù)據(jù)的拓?fù)潢P(guān)系

1）拓?fù)涞年P(guān)聯(lián)性

表示不同類型元素（結(jié)點(diǎn)、弧段、多邊形）之間的關(guān)系

多邊形弧段號(hào)弧段號(hào)起點(diǎn)終點(diǎn)結(jié)點(diǎn)弧段

p1a1a5a6a1N2N1N1a1a3a5P2a2a4a6a2N2N3N2a1a2a6P3a3a4a5a3N3N1N3a2a3a4p4a7a4N3N4N4a4a5a6a5N1N4N5a7a6N4N2a7N5N5

a3N1a1a5p3N4p1N3a4P4a6N5a7p2a2N2第9頁(yè)，共48頁(yè)，2023年，2月20日，星期一2）拓?fù)涞泥徑有院瓦B通性

表示同類型元素（結(jié)點(diǎn)、弧段、多邊形）之間的關(guān)系多邊形之間的鄰接性；弧段之間的鄰接性；結(jié)點(diǎn)之間的連通性p1p2p3p4a1a2a3a4a5a6a7N1N2N3N4N5

P1\110a1\110110N1\1110p21\11a21\11010N21\110p311\0a311\1100N311\10p4010\a4011\110N4111\0a51011\10N50000\a611011\0a7000000\多邊形鄰接矩陣弧段鄰接矩陣結(jié)點(diǎn)連通矩陣第10頁(yè)，共48頁(yè)，2023年，2月20日，星期一3）拓?fù)涞陌?/p>

P1p2p2p1p3p1p3p2面的簡(jiǎn)單包含面的多層包含面的等價(jià)包含面包含點(diǎn)面包含線線包含點(diǎn)第11頁(yè)，共48頁(yè)，2023年，2月20日，星期一

4）拓?fù)潢P(guān)系表（拓?fù)潢P(guān)系以關(guān)連表達(dá)最為重要）

關(guān)聯(lián)性相鄰（連）性相離性相交性包含性重合性點(diǎn)與點(diǎn)線與線面與面點(diǎn)與線點(diǎn)與面線與面第12頁(yè)，共48頁(yè)，2023年，2月20日，星期一3.3矢量數(shù)據(jù)結(jié)構(gòu)及其編碼

基于矢量模型的數(shù)據(jù)結(jié)構(gòu)稱矢量數(shù)據(jù)結(jié)構(gòu)1、矢量數(shù)據(jù)的特點(diǎn)

2、矢量數(shù)據(jù)的獲取第13頁(yè)，共48頁(yè)，2023年，2月20日，星期一3、無(wú)拓?fù)潢P(guān)系的矢量模型

無(wú)拓?fù)潢P(guān)系的矢量模型實(shí)質(zhì)上是面向?qū)嶓w的一種數(shù)據(jù)模型。它以單個(gè)的空間實(shí)體為數(shù)據(jù)組織和存儲(chǔ)的基本單位。它采用面向?qū)ο蟮能浖_發(fā)方式，每個(gè)對(duì)象有自己的特性、自己的行為。只記錄空間目標(biāo)的位置坐標(biāo)和屬性信息，不記錄空間拓?fù)潢P(guān)系。如采用坐標(biāo)系列編碼。點(diǎn)目標(biāo)（x,y)線目標(biāo)(x1y1,x2y2,…….xnyn)面目標(biāo)(x1y1,x2y2,…….xnyn,x1y1)具體實(shí)現(xiàn)形式可將點(diǎn)，線，面直接用空間坐標(biāo)點(diǎn)數(shù)據(jù)表示；也可將坐標(biāo)點(diǎn)組成文件，每個(gè)點(diǎn)給予一個(gè)點(diǎn)號(hào)，而點(diǎn)，線，面用點(diǎn)號(hào)數(shù)據(jù)表示。第14頁(yè)，共48頁(yè)，2023年，2月20日，星期一

無(wú)拓?fù)潢P(guān)系的矢量模型優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：（1）數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，直觀，便于用戶接受；（2）便于系統(tǒng)的維護(hù)和更新。缺點(diǎn)：（1）數(shù)據(jù)余度大，如多邊形公共邊重復(fù)存儲(chǔ)，但沒(méi)有存儲(chǔ)多邊形之間的關(guān)系。相鄰多邊形易產(chǎn)生偽多邊形。解決的辦法是建立多邊形邊界表；（2）缺乏拓?fù)湫畔ⅲ玎徲蛐畔⒌?，不便于拓?fù)浞治觯ㄅR時(shí)建立拓?fù)潢P(guān)系）；（3）對(duì)島處理能力差，無(wú)法建立外多邊形的關(guān)系。第15頁(yè)，共48頁(yè)，2023年，2月20日，星期一

1）GIS中建立拓?fù)潢P(guān)系的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：（1）數(shù)據(jù)結(jié)構(gòu)緊密、拓?fù)潢P(guān)系明確，便于空間數(shù)據(jù)的拓?fù)洳樵兒屯負(fù)浞治鋈缇W(wǎng)絡(luò)分析；（2）便于系統(tǒng)內(nèi)數(shù)據(jù)共享；缺點(diǎn)：（1）數(shù)據(jù)結(jié)構(gòu)復(fù)雜，不便于系統(tǒng)的維護(hù)和更新，如局部實(shí)體的變化要重建拓?fù)潢P(guān)系；（2）對(duì)單個(gè)實(shí)體的操作效率不高，如增加、刪除、修改一個(gè)實(shí)體時(shí)涉及一系列的文件和數(shù)據(jù)庫(kù)表格；（3）難以表達(dá)復(fù)雜的地理實(shí)體。4、拓?fù)潢P(guān)系的矢量模型第16頁(yè)，共48頁(yè)，2023年，2月20日，星期一2）拓?fù)潢P(guān)系的關(guān)聯(lián)表達(dá)

顯式表示

(a)多邊形、弧段、結(jié)點(diǎn)（自上到下）

多邊形弧段弧段結(jié)點(diǎn)

P1a4a5a6a1N1N2P2a1a8a5a2N2N4P3a3a6a7a3N4N5P4a2a7a8a4N1N5a5N1N3a6N3N5a7N3N4a8N2N3（b）結(jié)點(diǎn)、弧段、多邊形結(jié)點(diǎn)弧段N1a1a4a5N2a1a2a8N3a5a6a7a8N4a2a3a7N5a3a4a6

弧段左多邊形右多邊形

a10P2a20p4a30p3a4p10a5p2p1a6p3p1a7p4p3a8p4p2第17頁(yè)，共48頁(yè)，2023年，2月20日，星期一半顯式表示

弧段起結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形坐標(biāo)

a1N1N20P2a2N2N40p4a3N4N50p3a4N1N5p10a5N1N3p2p1a6N3N6p3p1a7N3N4p4p3a8N2N3p4p2。

第18頁(yè)，共48頁(yè)，2023年，2月20日，星期一5、具有拓?fù)潢P(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)模型例

1）點(diǎn)狀數(shù)據(jù)結(jié)構(gòu)點(diǎn)狀地物數(shù)據(jù)結(jié)構(gòu)較簡(jiǎn)單。也可建立索引等。標(biāo)識(shí)符坐標(biāo)點(diǎn)屬性編碼注釋

第19頁(yè)，共48頁(yè)，2023年，2月20日，星期一

點(diǎn)實(shí)體標(biāo)識(shí)符類型（簡(jiǎn)單點(diǎn)、結(jié)點(diǎn)、文字說(shuō)明）序列號(hào)坐標(biāo)點(diǎn)（X，Y）相關(guān)屬性符號(hào)簡(jiǎn)單點(diǎn)比例尺方向指針結(jié)點(diǎn)符號(hào)排列文字說(shuō)明字體方向字符大小其它屬性第20頁(yè)，共48頁(yè)，2023年，2月20日，星期一2）線狀數(shù)據(jù)結(jié)構(gòu)

線狀地物坐標(biāo)點(diǎn)數(shù)據(jù)表

線標(biāo)識(shí)符序號(hào)坐標(biāo)系列點(diǎn)屬性編碼注釋線狀地物坐標(biāo)索引表線標(biāo)識(shí)符序號(hào)起點(diǎn)序號(hào)終點(diǎn)序號(hào)XminXmaxYminYmax第21頁(yè)，共48頁(yè)，2023年，2月20日，星期一

3)鏈狀雙重獨(dú)立面狀數(shù)據(jù)結(jié)構(gòu)

(1）多邊形文件多邊形號(hào)弧段號(hào)周長(zhǎng)面積

p1a4a5a6p2...（2）弧段索引文件弧段起結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形XminXmaxYminYmax

a1N1N20P2a2N2N40p4a3N4N50p3a4N1N5p10a5N1N3p2p1a6N3N6p3p1a7N3N4p4p3a8N2N3p4p2(3）弧段坐標(biāo)文件弧段號(hào)坐標(biāo)點(diǎn)

a1x1y1,x2y2,….…….

第22頁(yè)，共48頁(yè)，2023年，2月20日，星期一6、拓?fù)潢P(guān)系的自動(dòng)生成1）歐拉定理----用于檢驗(yàn)拓?fù)潢P(guān)系歐拉定理認(rèn)為a,n,P之間存在如下關(guān)系：

c=n-a+P；其中c為常數(shù)是多邊形圖的一個(gè)特征。C值為2;例1右圖實(shí)線部分n=2，a=3，p=3C=n-a+P=2–3+3=2例2加虛線上部分n=3，a=5，P=4，

C=3-5+4=2歐拉定理主要用于檢查點(diǎn)、線、面中是否存在多余或漏掉的圖形元素。第23頁(yè)，共48頁(yè)，2023年，2月20日，星期一

2）拓?fù)潢P(guān)系的自動(dòng)生成（1）點(diǎn)、線拓?fù)潢P(guān)系的生成在圖形采集和編輯中同時(shí)生成點(diǎn)、線拓?fù)潢P(guān)系弧段起結(jié)點(diǎn)終結(jié)點(diǎn)結(jié)點(diǎn)弧段

a1N1N2N1a1a2N2N3N2a1a2a3N2N4N3a2

弧段起結(jié)點(diǎn)終結(jié)點(diǎn)結(jié)點(diǎn)弧段

a1N1N2N1a1a2N2N3N2a1a2a3a3N2N4N3a2N4a3

a1a2a1a3a2N1N2N3N1N2N3N4第24頁(yè)，共48頁(yè)，2023年，2月20日，星期一（2）坐標(biāo)鏈（弧段）的求交的方法弧段的包絡(luò)矩形：弧段坐標(biāo)鏈中最大最小值XminYminXmaxYmax組成的矩形稱該弧段的包絡(luò)矩形；多邊形的包絡(luò)矩形：組成多邊形的所有坐標(biāo)鏈中最大最小值組成的矩形稱該多邊形的包絡(luò)矩形；XminYminXmaxYmaxXmaxYmaxXminYmin第25頁(yè)，共48頁(yè)，2023年，2月20日，星期一

（3）多邊形拓?fù)潢P(guān)系的生成多邊形通常分為獨(dú)立多邊形、帶島的多邊形、公共邊界多邊形及復(fù)合多邊形。其中最基礎(chǔ)的是具有公共邊界的多邊形。在建立多邊形拓?fù)潢P(guān)系之前，首先已建立了點(diǎn)、線拓?fù)潢P(guān)系。多邊形拓?fù)潢P(guān)系的生成的核心是自動(dòng)生成每個(gè)多邊形有那些弧段組成，同時(shí)填入弧段的左右多邊形號(hào)，并生成如下兩個(gè)文件。多邊形弧段弧段左多邊形右多邊形

第26頁(yè)，共48頁(yè)，2023年，2月20日，星期一以結(jié)點(diǎn)為中心生成拓?fù)潢P(guān)系

以當(dāng)前弧段結(jié)點(diǎn)為軸，按順時(shí)針（或逆時(shí)針）旋轉(zhuǎn)，遇到第一個(gè)弧段即為當(dāng)前弧段的后續(xù)弧段。連續(xù)以弧段的結(jié)點(diǎn)按順時(shí)針（或逆時(shí)針）搜索，可得到一閉合多邊形。經(jīng)拓?fù)鋵W(xué)證明：如上搜索，當(dāng)?shù)玫介]合多邊形的各弧段按順時(shí)針（或逆時(shí)針）排列時(shí)，此邊界為得到內(nèi)邊界（如島邊界）；當(dāng)?shù)玫介]合多邊形的各弧段按逆時(shí)針（或順時(shí)針）排列時(shí)，此邊界為外邊界。內(nèi)邊界是指該邊界圍成的區(qū)域其外圍是連通區(qū)域；外邊界是指該邊界圍成的區(qū)域其外圍是不連通區(qū)域。實(shí)際上島邊界數(shù)據(jù)的特殊性很易找出。第27頁(yè)，共48頁(yè)，2023年，2月20日，星期一（3）島的歸屬的判斷島的歸屬的判斷原則：（a）外邊界多邊形的包絡(luò)矩形必定包容內(nèi)邊界多邊形的包絡(luò)矩形，這是出現(xiàn)連通域的必要條件，但不是充分條件。（b）一個(gè)內(nèi)邊界多邊形只能對(duì)應(yīng)一個(gè)連通域的外邊界多邊形。（c）閉合多邊形A對(duì)閉合多邊形B是包容性的判斷只要在B多邊形邊界上取一點(diǎn)，檢查該點(diǎn)是否在閉合多邊形A內(nèi)。AB第28頁(yè)，共48頁(yè)，2023年，2月20日，星期一(4）多邊形屬性的賦給前面已得到了組成各個(gè)多邊形的相應(yīng)的弧段及其排列，為完成拓?fù)潢P(guān)系生成的全部工作，還要確定下面兩個(gè)問(wèn)題。(a)多邊形內(nèi)點(diǎn)及屬性的賦給(b)左右多邊形的確定連續(xù)以弧段的結(jié)點(diǎn)按順時(shí)針（或逆時(shí)針）搜索，得到外邊界的閉合多邊形弧段以逆時(shí)針排列；內(nèi)邊界的閉合多邊形弧段以順時(shí)針排列,實(shí)際輸入弧段的方向可能同排列方向一致，也可能不一致；如兩者一致：該弧段所包含的多邊形內(nèi)點(diǎn)及屬性為左多邊形；如如兩者不一致：該弧段所包含的多邊形內(nèi)點(diǎn)及屬性為右多邊形。在此基礎(chǔ)上生成數(shù)據(jù)文件。順時(shí)針走包含右多邊形逆時(shí)針走包含左多邊形左多變形右多變形第29頁(yè)，共48頁(yè)，2023年，2月20日，星期一

7、拓?fù)渚庉嬐負(fù)渚庉嬘脕?lái)檢查生成拓?fù)潢P(guān)系的正確性，并進(jìn)行編輯處理，主要問(wèn)題有：1）重復(fù)輸入線的檢查出現(xiàn)很多小的偽多邊形。2）漏線段的檢查。出現(xiàn)懸線，多邊形不封閉。3）圖與屬性不一致檢查圖與屬性匹配檢查，并輸出不匹配處。4）邏輯關(guān)系的檢查歐拉定理檢查DIME檢查，以多邊形為例第30頁(yè)，共48頁(yè)，2023年，2月20日，星期一3.4柵格數(shù)據(jù)結(jié)構(gòu)及其編碼一、柵格數(shù)據(jù)的特點(diǎn)第31頁(yè)，共48頁(yè)，2023年，2月20日，星期一二、柵格數(shù)據(jù)的獲取第32頁(yè)，共48頁(yè)，2023年，2月20日，星期一三、柵格數(shù)據(jù)的組織

數(shù)據(jù)的組織的目的是在計(jì)算機(jī)內(nèi)組織好數(shù)據(jù)，使達(dá)到最優(yōu)的數(shù)據(jù)存取，最少的存儲(chǔ)空間，最短的處理時(shí)間。柵格數(shù)據(jù)的結(jié)構(gòu)實(shí)質(zhì)是組織矩陣，使用行列號(hào)位置表示每個(gè)象元，位置值表示屬性或編碼值。其組織存儲(chǔ)通常有三種方法：。以象元為記錄序列。用數(shù)組來(lái)存不同圖層上同位置象元的屬性值。省空間。以層為單位，每層以象元為序記錄坐標(biāo)及屬性值。簡(jiǎn)單，量大、。以層為單位，每層以目標(biāo)為序記錄坐標(biāo)及屬性值。

象元1象元2..坐標(biāo)x坐標(biāo)y層1屬性值層2屬性值。。層1

象元1

坐標(biāo)x

坐標(biāo)y

屬性值象元2

。。層2.層1

目標(biāo)1

屬性值象元1坐標(biāo)象元2坐標(biāo)

..

目標(biāo)2

。。層2.可隱含地址值第33頁(yè)，共48頁(yè)，2023年，2月20日，星期一

四、柵格數(shù)據(jù)的壓縮編碼

1、鏈?zhǔn)骄幋a-----線狀地物編碼第34頁(yè)，共48頁(yè)，2023年，2月20日，星期一

110030770000101222234443344466220042700122443456第35頁(yè)，共48頁(yè)，2023年，2月20日，星期一2、游程編碼

對(duì)塊狀地物的柵格數(shù)據(jù)進(jìn)行壓縮編碼

方式（gk,lk)游程終止編碼中g(shù)k柵格元素的屬性值lk游程的終止列號(hào)(0,1)(4,3)(7,8)(4,5)(7,8)(4,4)(8,6)(7,8)(0,2)(4,3)(8,6)(7,8)(0,2)(8,6)(7,7)(8,8)(0,3)(8,8)(0,4)(8,8)(0,5)(8,8)游程長(zhǎng)度編碼中g(shù)k柵格元素的屬性值lk游程的連續(xù)長(zhǎng)度。（0,1)(4,2)(7,5)(4,5)(7,3)(4,4)(8,2)(7,2)(0,2)(4,1)(8,3)(7,2)(0,2)(8,4)(7,1)(8,1)(0,3)(8,5)(0,4)(8,4)(0,5)(8,3)第36頁(yè)，共48頁(yè)，2023年，2月20日，星期一3、四叉樹編碼1）樹數(shù)據(jù)結(jié)構(gòu)線性表結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)隊(duì)列結(jié)構(gòu)棧結(jié)構(gòu)邏輯結(jié)構(gòu)樹結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu)圖結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）非順序存儲(chǔ)結(jié)構(gòu)（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）在數(shù)據(jù)結(jié)構(gòu)中樹屬于非線性數(shù)據(jù)結(jié)構(gòu)。她是有一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T1，T2，T3TN，其中有一個(gè)是根結(jié)點(diǎn)，余下的被分成N個(gè)互不相交的集合，這些集合的每一個(gè)又都是樹，T1，T2，T3TN被稱為根的子樹。第37頁(yè)，共48頁(yè)，2023年，2月20日，星期一結(jié)點(diǎn)的度指每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)；樹的度指所有結(jié)點(diǎn)度的最大值；結(jié)點(diǎn)的層次樹既具有遞歸結(jié)構(gòu)，又的具有層次結(jié)構(gòu)，即結(jié)點(diǎn)的層次數(shù)樹的深度（或高度）指所有結(jié)點(diǎn)層次的最大值一第38頁(yè)，共48頁(yè)，2023年，2月20日，星期一2）常規(guī)四叉樹四叉樹是指樹中的每個(gè)結(jié)點(diǎn)最多只有四棵子樹，即樹中任一結(jié)點(diǎn)的度數(shù)不的大于4。

主要用在數(shù)據(jù)索引，圖幅索引等。

第39頁(yè)，共48頁(yè)，2023年，2月20日，星期一常規(guī)四叉樹的其特點(diǎn)

（1）遞歸分割，可從上到下；

（2）除了記錄葉結(jié)點(diǎn)外，還要記錄中間結(jié)點(diǎn)。通常以指針來(lái)聯(lián)系結(jié)點(diǎn)之間的關(guān)系，包括前趨結(jié)點(diǎn)、后續(xù)結(jié)點(diǎn)（最多4個(gè)）、及本結(jié)點(diǎn)的屬性值。（3）常規(guī)四叉樹不僅要記錄每個(gè)結(jié)點(diǎn)，還要記錄結(jié)點(diǎn)的前趨結(jié)點(diǎn)和后續(xù)結(jié)點(diǎn)，以反映結(jié)點(diǎn)之間的聯(lián)系，存儲(chǔ)空間大，操作復(fù)雜（因?yàn)閷?duì)結(jié)點(diǎn)進(jìn)行運(yùn)算時(shí)，首先要作對(duì)樹的遍歷運(yùn)算。在GIS和圖象處理中不用常規(guī)四叉樹，而用線性四叉樹。

第40頁(yè)，共48頁(yè)，2023年，2月20日，星期一

A

NW0NE1SW2SE3四叉樹的分解過(guò)程四叉樹的分解過(guò)程是將一幅圖等分成四部分，檢查其格網(wǎng)值，如格網(wǎng)子區(qū)的值相同就不再分割，否則遞歸分割，直到每個(gè)子塊含有相同值為止。第41頁(yè)，共48頁(yè)，2023年，2月20日，星期一3）線性四叉樹的特點(diǎn)

首先線性四叉樹具有四叉樹的形式。一幅2nx

2n柵格陣列的圖用四叉樹分割時(shí)，具有的最大深度為n，即可分為0,1,2,3…n層第0層，邊長(zhǎng)上的最大柵格數(shù)為2n第1層，邊長(zhǎng)上的最大柵格數(shù)為2n-1第2層，邊長(zhǎng)上的最大柵格數(shù)為2n-2第n層，邊長(zhǎng)上的最大柵格數(shù)為