數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別

數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別PAGE1簡(jiǎn)單數(shù)據(jù)構(gòu)造和拓?fù)鋽?shù)據(jù)構(gòu)造我們的世界五彩繽紛，人類(lèi)的生活與這個(gè)環(huán)境密不可分，要利用和改造自然世界為人類(lèi)的生存、生活創(chuàng)造有利的條件，必須將所有關(guān)注的部分世界加以簡(jiǎn)化和抽象，人類(lèi)才能提醒出控制客觀事物的演變過(guò)程的根本規(guī)律，而實(shí)現(xiàn)這一目的的普遍手段是采用模型的方法，利用一個(gè)模型來(lái)描繪和表達(dá)這個(gè)世界，用空間數(shù)據(jù)構(gòu)造去表示我們所要理解的客觀事物?？臻g數(shù)據(jù)構(gòu)造就是指空間數(shù)據(jù)的編排方式和組織關(guān)系，空間數(shù)據(jù)構(gòu)造是空間數(shù)據(jù)在計(jì)算機(jī)中的詳細(xì)組織方式。目前尚無(wú)一種統(tǒng)一的數(shù)據(jù)構(gòu)造可以同時(shí)存儲(chǔ)上述各種類(lèi)型的數(shù)據(jù)，而是將不同類(lèi)型的空間數(shù)據(jù)以不同的數(shù)據(jù)構(gòu)造存儲(chǔ)。一般來(lái)說(shuō)，屬性數(shù)據(jù)與其他信息系統(tǒng)一樣常用二維關(guān)系表格形式存儲(chǔ)。元數(shù)據(jù)以特定的空間元數(shù)據(jù)格式存儲(chǔ)，而描繪地理位置及其空間關(guān)系的空間特征數(shù)據(jù)是地理信息系統(tǒng)所特有的數(shù)據(jù)類(lèi)型，主要以矢量數(shù)據(jù)構(gòu)造和柵格數(shù)據(jù)構(gòu)造兩種形式存儲(chǔ)。空間數(shù)據(jù)編碼是空間數(shù)據(jù)構(gòu)造的實(shí)現(xiàn)，目的是將不同的空間實(shí)體按一定的數(shù)據(jù)構(gòu)造轉(zhuǎn)換適用于計(jì)算機(jī)儲(chǔ)存和處理的過(guò)程。不同的實(shí)體對(duì)象，其空間數(shù)據(jù)構(gòu)造相差很大，即使是同一對(duì)象實(shí)體，也可以用許多種方式來(lái)組織數(shù)據(jù)，按不同數(shù)據(jù)構(gòu)造去處理，得到的結(jié)果內(nèi)容頁(yè)是截然不同的。而計(jì)算機(jī)存儲(chǔ)和處理數(shù)據(jù)的效率，在很大程度上是依賴于數(shù)據(jù)構(gòu)造的組織方式的優(yōu)劣。抽象是人們觀察和分析復(fù)雜事物和現(xiàn)象的常用手段之一。將地理系統(tǒng)中復(fù)雜的地理現(xiàn)象進(jìn)展抽象得到的地理對(duì)象稱(chēng)為地理實(shí)體或空間實(shí)體、空間目的，簡(jiǎn)稱(chēng)實(shí)體(Entity)。實(shí)表達(dá)實(shí)世界中客觀存在的，并可互相區(qū)別的事物。實(shí)體可以指?jìng)€(gè)體，也可以指總體，即個(gè)體的集合.抽象的程度與研究區(qū)域的大小、規(guī)模不同而有所不同，如在一張小比例尺的全國(guó)地圖中，武漢市被抽象為一個(gè)點(diǎn)狀實(shí)體，抽象程度很大；而在較大比例尺的武漢市地圖上，需要將武漢市的街道、房屋詳盡地表示出來(lái)，武漢市那么被抽象為一個(gè)由簡(jiǎn)單點(diǎn)、線、面實(shí)體組成的龐大復(fù)雜組合實(shí)體，其抽象程度較前者而言較小。所以說(shuō)，實(shí)體是一個(gè)詳細(xì)有概括性、復(fù)雜性、相對(duì)意義的概念。數(shù)據(jù)構(gòu)造在GIS中對(duì)于數(shù)據(jù)的采集、存儲(chǔ)、查詢、檢索和應(yīng)用分析等操作方式有著重要的影響，一種高效率的數(shù)據(jù)構(gòu)造應(yīng)該具備以下幾個(gè)要求：1、組織的數(shù)據(jù)可以表示要素之間的層次關(guān)系，便于不同數(shù)據(jù)聯(lián)絡(luò)于覆蓋；2、正確反映地理實(shí)體之間的空間排列方式和各實(shí)體之間的互相關(guān)系；3、便于存取與檢索；4、節(jié)省存儲(chǔ)空間，減少數(shù)據(jù)冗余；5、存取速度快，在運(yùn)算速度較慢的微機(jī)上要到達(dá)快速響應(yīng)；6、具有足夠的靈敏性，數(shù)據(jù)組織應(yīng)具有插入新的數(shù)據(jù)、刪除或修改部分?jǐn)?shù)據(jù)的根本功能。柵格數(shù)據(jù)構(gòu)造柵格構(gòu)造是以規(guī)那么的陣列來(lái)表示空間地物或現(xiàn)象分布的數(shù)據(jù)組織,組織中的每個(gè)數(shù)據(jù)表示地物或現(xiàn)象的非幾何屬性特征。柵格構(gòu)造的顯著特點(diǎn):屬性明顯,定位隱含,即數(shù)據(jù)直接記錄屬性的指針或數(shù)據(jù)本身,而所在位置那么根據(jù)行列號(hào)轉(zhuǎn)換為相應(yīng)的坐標(biāo)。柵格數(shù)據(jù)的編碼方法:直接?xùn)鸥窬幋a,就是將柵格數(shù)據(jù)看作一個(gè)數(shù)據(jù)矩陣,逐行〔或逐列〕逐個(gè)記錄代碼;壓縮編碼,包括鏈碼〔弗里曼鏈碼〕比擬合適存儲(chǔ)圖形數(shù)據(jù);游程長(zhǎng)度編碼通過(guò)記錄行或列上相鄰假設(shè)干屬性一樣點(diǎn)的代碼來(lái)實(shí)現(xiàn);塊碼是有成長(zhǎng)度編碼擴(kuò)展到二維的情況,采用方形區(qū)域?yàn)橛涗泦卧?四叉樹(shù)編碼是最有效的柵格數(shù)據(jù)壓縮編碼方法之一,還能進(jìn)步圖形操作效率,具有可變的分辨率。數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別全文共6頁(yè)，當(dāng)前為第1頁(yè)。數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別全文共6頁(yè)，當(dāng)前為第1頁(yè)。矢量數(shù)據(jù)構(gòu)造矢量數(shù)據(jù)構(gòu)造是通過(guò)記錄坐標(biāo)的方式盡可能準(zhǔn)確地表示點(diǎn)、線和多邊形等地理實(shí)體,坐標(biāo)空間設(shè)為連續(xù),允許任意位置、長(zhǎng)度和面積的準(zhǔn)確定義。矢量構(gòu)造的顯著特點(diǎn):定位明顯,屬性隱含。矢量數(shù)據(jù)的編碼方法:對(duì)于點(diǎn)實(shí)體和線實(shí)體,直接記錄空間信息和屬性信息;對(duì)于多邊形地物,有坐標(biāo)序列法、樹(shù)狀索引編碼法和拓?fù)錁?gòu)造編碼法。坐標(biāo)序列法是由多邊形邊界的x,y坐標(biāo)對(duì)集合及說(shuō)明信息組成,是最簡(jiǎn)單的一種多邊形矢量編碼法,文件構(gòu)造簡(jiǎn)單,但多邊形邊界被存儲(chǔ)兩次產(chǎn)生數(shù)據(jù)冗余,而且缺少鄰域信息;樹(shù)狀索引編碼法是將所有邊界點(diǎn)進(jìn)展數(shù)字化,順序存儲(chǔ)坐標(biāo)對(duì),由點(diǎn)索引與邊界限號(hào)相聯(lián)絡(luò),以線索引與各多邊形相聯(lián)絡(luò),形成樹(shù)狀索引構(gòu)造,消除了相鄰多邊形邊界數(shù)據(jù)冗余問(wèn)題;拓?fù)錁?gòu)造編碼法是通過(guò)建立一個(gè)完好的拓?fù)潢P(guān)系構(gòu)造,徹底解決鄰域和島狀信息處理問(wèn)題的方法,但增加了算法的復(fù)雜性和數(shù)據(jù)庫(kù)的大小。矢量柵格數(shù)據(jù)的比擬矢量數(shù)據(jù)的優(yōu)缺點(diǎn):優(yōu)點(diǎn)為數(shù)據(jù)構(gòu)造緊湊、冗余度低,有利于網(wǎng)絡(luò)和檢索分析,圖形顯示質(zhì)量好、精度高;缺點(diǎn)為數(shù)據(jù)構(gòu)造復(fù)雜,多邊形疊加分析比擬困難。柵格數(shù)據(jù)的優(yōu)缺點(diǎn):優(yōu)點(diǎn)為數(shù)據(jù)構(gòu)造簡(jiǎn)單,便于空間分析和地表模擬,現(xiàn)勢(shì)性較強(qiáng);缺點(diǎn)為數(shù)據(jù)量大,投影轉(zhuǎn)換比擬復(fù)雜。兩者比擬:柵格數(shù)據(jù)操作總的來(lái)說(shuō)容易實(shí)現(xiàn),矢量數(shù)據(jù)操作那么比擬復(fù)雜;柵格構(gòu)造是矢量構(gòu)造在某種程度上的一種近似,對(duì)于同一地物到達(dá)于矢量數(shù)據(jù)一樣的精度需要更大量的數(shù)據(jù);在坐標(biāo)位置搜索、計(jì)算多邊形形狀面積等方面柵格構(gòu)造更為有效,而且易于遙感相結(jié)合,易于信息共享;矢量構(gòu)造對(duì)于拓?fù)潢P(guān)系的搜索那么更為高效,網(wǎng)絡(luò)信息只有用矢量才能完全描繪,而且精度較高。對(duì)于地理信息系統(tǒng)軟件來(lái)說(shuō),兩者共存,各自發(fā)揮優(yōu)勢(shì)是非常有效的。矢量柵格互相轉(zhuǎn)換算法矢量轉(zhuǎn)柵格:內(nèi)部點(diǎn)擴(kuò)散法,即由多邊形內(nèi)部種子點(diǎn)向周?chē)忺c(diǎn)擴(kuò)散,直至到達(dá)各邊界為止;復(fù)數(shù)積分算法,即由待判別點(diǎn)對(duì)多邊形的封閉邊界計(jì)算復(fù)數(shù)積分,來(lái)判斷兩者關(guān)系;射線算法和掃描算法,即由圖外某點(diǎn)向待判點(diǎn)引射線,通過(guò)射線與多邊形邊界交點(diǎn)數(shù)來(lái)判斷內(nèi)外關(guān)系;邊界代數(shù)算法,是一種基于積分思想的矢量轉(zhuǎn)柵格算法,合適于記錄拓?fù)潢P(guān)系的多邊形矢量數(shù)據(jù)轉(zhuǎn)換,方法是由多邊形邊界上某點(diǎn)開(kāi)場(chǎng),順時(shí)針?biāo)阉鬟吔缦?上行時(shí)邊界左側(cè)具有一樣行坐標(biāo)的柵格減去某值,下行時(shí)邊界左側(cè)所有柵格點(diǎn)加上該值,邊界搜索完畢之后即完成多邊形的轉(zhuǎn)換。柵格轉(zhuǎn)矢量:即是提取具有一樣編號(hào)的柵格集合表示的多邊形區(qū)域的邊界和邊界的拓?fù)潢P(guān)系,并表示成矢量格式邊界限的過(guò)程。步驟包括:多邊形邊界提取,即使用高通濾波將柵格圖像二值化;邊界限追蹤,即對(duì)每個(gè)弧段由一個(gè)節(jié)點(diǎn)向另一個(gè)節(jié)點(diǎn)搜索;拓?fù)潢P(guān)系生成和去處多余點(diǎn)及曲線圓滑。拓?fù)涞母靖拍顢?shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別全文共6頁(yè)，當(dāng)前為第2頁(yè)。幾何信息和拓?fù)潢P(guān)系是地理信息系統(tǒng)中描繪地理要素的空間位置和空間關(guān)系的不可缺少的根本信息。其中幾何信息主要涉及幾何目的的坐標(biāo)位置、方向、角度、間隔和面積等信息，它通常用解析幾何的方法來(lái)分析。而空間關(guān)系信息主要涉及幾何關(guān)系的“相連〞、“相鄰〞、“數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別全文共6頁(yè)，當(dāng)前為第2頁(yè)。在矢量拓?fù)鋽?shù)據(jù)構(gòu)造中，空間數(shù)據(jù)不但要記錄空間實(shí)體的位置，而且要記錄空間實(shí)體間的拓?fù)潢P(guān)系，這是地理信息系統(tǒng)區(qū)別于其他數(shù)據(jù)庫(kù)管理系統(tǒng)的重要標(biāo)志。建立拓?fù)潢P(guān)系是一種對(duì)空間構(gòu)造關(guān)系進(jìn)展明確定義的數(shù)學(xué)方法。目前，空間數(shù)據(jù)的拓?fù)鋽?shù)據(jù)構(gòu)造的表示方式?jīng)]有固定的格式，也沒(méi)有形成標(biāo)準(zhǔn)，其根本原理是一樣的。因此，在矢量拓?fù)錁?gòu)造表示方法中，任何地理實(shí)體均可以用點(diǎn)、線、面來(lái)表示其特征，并且可根據(jù)各實(shí)體間的空間拓?fù)潢P(guān)系，解譯出更多的信息。對(duì)于二維空間數(shù)據(jù)而言，矢量數(shù)據(jù)可以抽象點(diǎn)、線、面三種要素，也稱(chēng)拓?fù)湟?。?duì)三維而言，還要加上體。其最根本的拓?fù)潢P(guān)系主要有拓?fù)溧徑?、拓?fù)潢P(guān)聯(lián)、拓?fù)浒葞追N。拓?fù)鋽?shù)據(jù)構(gòu)造中關(guān)鍵的就是對(duì)這些拓?fù)湟亻g的拓?fù)潢P(guān)系進(jìn)展表示，幾何數(shù)據(jù)的表示可參照矢量數(shù)據(jù)的簡(jiǎn)單數(shù)據(jù)。雖然目前GIS中根本的拓?fù)潢P(guān)系的表示方法不盡一樣，但只要能完好表達(dá)出拓?fù)湟亻g的根本拓?fù)潢P(guān)系就可以。拓?fù)鋽?shù)據(jù)構(gòu)造：拓?fù)鋽?shù)據(jù)構(gòu)造包括DIME(對(duì)偶獨(dú)立地圖編碼法)、POLYVRT(多邊形轉(zhuǎn)換器)、TIGER(地理編碼和參照系統(tǒng)的拓?fù)浼?等。它們共同的特點(diǎn)是:點(diǎn)是互相獨(dú)立的，點(diǎn)連成線，線構(gòu)成面。每條線始于起始結(jié)點(diǎn)(FN)，止于終止結(jié)點(diǎn)TN)，并與左右多邊形(LP和RP)相鄰接。構(gòu)成多邊形的線叉稱(chēng)為鏈段或弧段，兩條以上的弧段相交的點(diǎn)稱(chēng)為結(jié)點(diǎn)，由一條弧段組成的多邊形稱(chēng)為島，多邊形圖中不含島的多邊形稱(chēng)為簡(jiǎn)單多邊形，表示單連通區(qū)域;含島區(qū)的多邊形稱(chēng)為復(fù)合多邊形，表示復(fù)連通區(qū)域。在復(fù)連通區(qū)域中，包括有外邊界和內(nèi)邊界，島區(qū)多邊形看作是復(fù)連通區(qū)域的內(nèi)邊界，復(fù)連通區(qū)域的內(nèi)邊界多邊形對(duì)應(yīng)的區(qū)域含有平面上的無(wú)窮遠(yuǎn)慮。該數(shù)據(jù)構(gòu)造的根本元素如圖2-11所示。數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別全文共6頁(yè)，當(dāng)前為第3頁(yè)。在這種數(shù)據(jù)構(gòu)造中，弧段或鏈段是數(shù)據(jù)組織的根本對(duì)象?；《挝募苫《斡涗浗M成，每個(gè)弧段記錄包括弧段標(biāo)識(shí)碼、FN、TN、LP和RP。結(jié)點(diǎn)文件由結(jié)點(diǎn)記錄組成，包括每個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)號(hào)、結(jié)點(diǎn)坐標(biāo)及與該結(jié)點(diǎn)連數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別全文共6頁(yè)，當(dāng)前為第3頁(yè)。表2-5拓?fù)鋽?shù)據(jù)構(gòu)造的弧段文件構(gòu)成拓?fù)鋽?shù)據(jù)構(gòu)造最重要的技術(shù)特征和奉獻(xiàn)是具有拓?fù)渚庉嫻δ?。這種拓?fù)渚庉嫻δ埽坏ＷC數(shù)字化原始數(shù)據(jù)的自動(dòng)查錯(cuò)編輯，而且可以自動(dòng)形成封閉的多邊形邊界，為由各個(gè)單獨(dú)存儲(chǔ)的弧段組成所需要的各類(lèi)多邊形及建立空間數(shù)據(jù)庫(kù)奠定根底。拓?fù)渚庉嫻δ馨ǘ噙呅芜B接編輯和結(jié)點(diǎn)連接編輯，前者指順序連接組成封閉多邊形一組線段的編輯，后者指順序連接環(huán)繞某個(gè)結(jié)點(diǎn)所有多邊形的編輯。詳細(xì)的編輯算法如下:(1)多邊形連接編輯。例如，設(shè)需要對(duì)多邊形P1進(jìn)展編輯，其算法過(guò)程為:①?gòu)谋?-5所示的弧段文件中，檢出與當(dāng)前編輯的多邊形P1相關(guān)的所有記錄:②在檢出的記錄中，計(jì)算機(jī)檢查當(dāng)前編輯的多邊形P1所處的位置:假如P1位在左多邊形位置，將之與位于右多邊形位置的多邊形號(hào)相交換，同時(shí)也將該記錄的結(jié)點(diǎn)號(hào)位置作相應(yīng)的交換;反之，假如當(dāng)前編輯的多邊形P1位于右多邊形位置，那么該記錄的所有數(shù)據(jù)項(xiàng)順序不作改變。數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別全文共6頁(yè)，當(dāng)前為第4頁(yè)。按照上述規(guī)那么，檢出的記錄變?yōu)橐韵滦问?

數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別全文共6頁(yè)，當(dāng)前為第4頁(yè)。③從經(jīng)過(guò)代碼位置轉(zhuǎn)換的記錄中，任取一個(gè)起結(jié)點(diǎn)作為起點(diǎn)，順序連接各個(gè)結(jié)點(diǎn)，必要時(shí)可對(duì)記錄的前后順序作調(diào)整，使得連接的結(jié)點(diǎn)能自行封閉，如圖2-12所示。

假如按照上述順序連接的結(jié)點(diǎn)不能自行閉合，或者出現(xiàn)記錄缺損或記錄多余等情況，那么表示弧段文件有錯(cuò)，必須改正出錯(cuò)的記錄。直到所有多邊形都經(jīng)過(guò)編輯和改正，再轉(zhuǎn)入結(jié)點(diǎn)連接編輯。(2)結(jié)點(diǎn)連接編輯。例如，設(shè)需要對(duì)結(jié)點(diǎn)N2進(jìn)展編輯，其算法過(guò)程為:①?gòu)谋?-5所示的弧段文件中，檢出與當(dāng)前編輯的結(jié)點(diǎn)N2相關(guān)的所有記錄：

②在檢出的記錄中，計(jì)算機(jī)檢查當(dāng)前編輯的結(jié)點(diǎn)N2所處的位置:假如N2位在起結(jié)點(diǎn)位置，將之與位于終結(jié)點(diǎn)位置的結(jié)點(diǎn)號(hào)相交換，同時(shí)也符該記錄的多邊形號(hào)位置作相應(yīng)的交換;反之，假如當(dāng)前編輯的結(jié)點(diǎn)N2位于終結(jié)點(diǎn)位置，那么該記錄所有數(shù)據(jù)項(xiàng)順序不作改變。按照上述規(guī)那么，檢出的記錄變?yōu)橐韵滦问?

③從經(jīng)過(guò)代碼位置轉(zhuǎn)換的記錄中，任取一個(gè)左多邊形作為起點(diǎn)，順序連接各個(gè)多邊形，同樣，必要時(shí)可對(duì)記錄的前后順序作調(diào)整，使得連接的多邊形能首尾照應(yīng)，如圖2-13所示。

假如按照上述序連接的多邊形不能首尾照應(yīng)，或者出現(xiàn)記錄缺損或記錄多余等情況，同樣也表示弧段文件有錯(cuò)，必須改正出錯(cuò)的記錄。直到所有結(jié)點(diǎn)都經(jīng)過(guò)編輯和改正，才能將該弧段文件用于結(jié)點(diǎn)文件和多邊形文件的自動(dòng)生成以及數(shù)據(jù)庫(kù)的建立。這種拓?fù)鋽?shù)據(jù)構(gòu)造及其自動(dòng)編輯功能，已經(jīng)被許多商品化的GIS軟件所采用，例如美國(guó)的ARC/INFOGIS軟件等。拓?fù)鋽?shù)據(jù)構(gòu)造的構(gòu)造特點(diǎn)：數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別全文共6頁(yè)，當(dāng)前為第5頁(yè)。數(shù)據(jù)結(jié)構(gòu)與拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的區(qū)別全文共6頁(yè)，當(dāng)前為第5頁(yè)。2、便于分析查詢，尤其是點(diǎn)、線、面直線的相鄰關(guān)系查詢和分析。拓?fù)鋽?shù)據(jù)構(gòu)造的優(yōu)缺點(diǎn)：圖形的修改方便，可由軟件檢查數(shù)據(jù)輸入錯(cuò)誤，容易保證數(shù)據(jù)質(zhì)量；便于疊合分析、網(wǎng)絡(luò)分析等；數(shù)據(jù)構(gòu)造復(fù)雜，軟件復(fù)雜；建立拓?fù)潢P(guān)系需花計(jì)算時(shí)間，特別是當(dāng)?shù)貓D覆蓋范圍很大，數(shù)據(jù)量很大時(shí)。拓?fù)鋽?shù)據(jù)構(gòu)造的構(gòu)建實(shí)際上大大增加了數(shù)據(jù)編輯的難度和復(fù)雜性，以致于它成了引起廣泛爭(zhēng)議的問(wèn)題。顯然，拓?fù)潢P(guān)系的存在為數(shù)據(jù)錯(cuò)誤的查找和空間分析提供了必要的前提，但并不是所有的GIS應(yīng)用丟必須具備這種預(yù)先存儲(chǔ)的、消耗大量精力才能創(chuàng)立的數(shù)據(jù)構(gòu)造。許多GIS軟件只使用其中集中最根本的拓?fù)潢P(guān)系，就能滿足大多數(shù)空間分析的需要，但更復(fù)雜的空間分析，也許需要更多的拓?fù)潢P(guān)系。一般的，建