空間數(shù)據(jù)管理課件

空間數(shù)據(jù)管理

1．空間數(shù)據(jù)庫地理信息系統(tǒng)的內(nèi)容及其功能與一般管理信息系統(tǒng)的區(qū)別，是數(shù)據(jù)具有空間分布的性質(zhì)。對地理信息系統(tǒng)來講，不僅數(shù)據(jù)本身具有空間屬性，系統(tǒng)的分析和應(yīng)用也無不與地理環(huán)境直接關(guān)聯(lián)。系統(tǒng)的這一基本特征，深刻地影響著數(shù)據(jù)的結(jié)構(gòu)、數(shù)據(jù)庫的設(shè)計、分析算法和軟件，以及系統(tǒng)的輸入和輸出。1．1地理信息系統(tǒng)與一般信息系統(tǒng)的比較1．1．1兩者的區(qū)別1）在硬件上，為了處理圖形和圖像數(shù)據(jù)，系統(tǒng)需要配置專門的輸入和輸出設(shè)備，如數(shù)字化儀、繪圖機(jī)、圖形圖像的顯示設(shè)備等。2）在軟件上，則要求研制專門的圖形和圖像數(shù)據(jù)的分析算法和處理軟件，這些算法和軟件又直接和數(shù)據(jù)的結(jié)構(gòu)及數(shù)據(jù)庫的管理方法有關(guān)。1．空間數(shù)據(jù)庫3）在信息處理的內(nèi)容和采用目的方面，一般的管理信息系統(tǒng)，主要是查詢檢索和統(tǒng)計分析，處理的結(jié)果，大多是制成某種規(guī)定格式的表格數(shù)據(jù)，而地理信息系統(tǒng)，除了基本的信息檢索和統(tǒng)計分析外，主要用于分析研究資源的合理開發(fā)利用，制定區(qū)域發(fā)展規(guī)劃，地區(qū)的綜合治理方案，對環(huán)境進(jìn)行動態(tài)的監(jiān)視和預(yù)測預(yù)報，為國民經(jīng)濟(jì)建設(shè)中的決策提供科學(xué)依據(jù)，為生產(chǎn)實踐提供信息和指導(dǎo)。1．空間數(shù)據(jù)庫1．1．2兩者共同之處兩者都是以計算機(jī)為核心的信息處理系統(tǒng)，都具有數(shù)據(jù)量大和數(shù)據(jù)之間關(guān)系復(fù)雜的特點，也都隨著數(shù)據(jù)庫技術(shù)的發(fā)展在不斷的改進(jìn)和完善。1．空間數(shù)據(jù)庫1．2空間數(shù)據(jù)庫1．2．1數(shù)據(jù)庫的概念數(shù)據(jù)庫就是為一定目的服務(wù)，以特定的數(shù)據(jù)存儲的相關(guān)聯(lián)的數(shù)據(jù)集合，它是數(shù)據(jù)管理的高級階段，是從文件管理系統(tǒng)發(fā)展而來的。為了直觀地理解數(shù)據(jù)庫，可以把數(shù)據(jù)庫作如下比較：

表7-1：數(shù)據(jù)庫與圖書館比較1．空間數(shù)據(jù)庫1．2．2空間數(shù)據(jù)庫特點1）數(shù)據(jù)量特別大2）不僅有屬性數(shù)據(jù)，還有大量的空間數(shù)據(jù)3）數(shù)據(jù)應(yīng)用廣泛1．空間數(shù)據(jù)庫1．2．3數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)是在文件處理系統(tǒng)的基礎(chǔ)上進(jìn)一步發(fā)展的系統(tǒng)。DBMS在用戶應(yīng)用程序和數(shù)據(jù)文件之間起到了橋梁作用。DBMS的最大優(yōu)點是提供了兩者之間的數(shù)據(jù)獨立性，即應(yīng)用程序訪問數(shù)據(jù)文件時，不必知道數(shù)據(jù)文件的物理存儲結(jié)構(gòu)。當(dāng)數(shù)據(jù)文件的存儲結(jié)構(gòu)改變時，不必改變應(yīng)用程序。1．空間數(shù)據(jù)庫2）GIS數(shù)據(jù)管理方法主要4種類型（2．1）對不同的應(yīng)用模型開發(fā)獨立的數(shù)據(jù)管理服務(wù)，這是一種基于文件管理的處理方法。（2．2）在商業(yè)化的DBMS基礎(chǔ)上開發(fā)附加系統(tǒng)。開發(fā)一個附加軟件用于存儲和管理空間數(shù)據(jù)和空間分析，使用DBMS管理屬性數(shù)據(jù)。1．空間數(shù)據(jù)庫（2．3）使用現(xiàn)有的DBMS，通常是以DBMS為核心，對系統(tǒng)的功能進(jìn)行必要擴(kuò)充，空間數(shù)據(jù)和屬性數(shù)據(jù)在同一個DBMS管理之下。需要增加足夠數(shù)量的軟件和功能來提供空間功能和圖形顯示功能。（2．4）重新設(shè)計一個具有空間數(shù)據(jù)和屬性數(shù)據(jù)管理和分析功能的數(shù)據(jù)庫系統(tǒng)。

1．空間數(shù)據(jù)庫1．3數(shù)據(jù)與文件組織數(shù)據(jù)是現(xiàn)實世界中信息的載體，是信息的具體表達(dá)形式，為了表達(dá)有意義的信息內(nèi)容，數(shù)據(jù)必須按照一定的方式進(jìn)行組織和存儲。1．3．1數(shù)據(jù)組織的分級數(shù)據(jù)庫中的數(shù)據(jù)組織一般可以分為四級：數(shù)據(jù)項、記錄、文件和數(shù)據(jù)庫。1．空間數(shù)據(jù)庫1．3．2數(shù)據(jù)間的邏輯聯(lián)系數(shù)據(jù)間的邏輯聯(lián)系主要是指記錄與記錄之間的聯(lián)系。記錄是表示現(xiàn)實世界中的實體的。實體之間存在著一種或多種聯(lián)系，這樣的聯(lián)系必然要反映到記錄之間的聯(lián)系上來。數(shù)據(jù)之間的邏輯聯(lián)系主要有三種：一對一的聯(lián)系；一對多的聯(lián)系；多對多的聯(lián)系。1．空間數(shù)據(jù)庫1．3．3常用數(shù)據(jù)文件圖7-1：非順序文件操作系統(tǒng)實現(xiàn)的文件組織方式，可以分為順序文件、索引文件、直接文件和倒排文件。1．空間數(shù)據(jù)庫1）順序文件順序文件（圖7-2）是最簡單的文件組織形式，對記錄按照主關(guān)鍵字的順序進(jìn)行組織。

圖7-2：順序文件1．空間數(shù)據(jù)庫2）索引文件索引文件除了存儲記錄本身（主文件）以外，還建立了若干索引表，這種帶有索引表的文件叫索引文件。索引表中列出記錄關(guān)鍵字和記錄在文件中的位置（地址）。讀取記錄時，只要提供記錄的關(guān)鍵字值，系統(tǒng)通過查找索引表獲得記錄的位置，然后取出該記錄。1．空間數(shù)據(jù)庫3）直接文件直接文件又稱隨機(jī)文件，其存儲是根據(jù)記錄關(guān)鍵字的值，通過某種轉(zhuǎn)換方法得到一個物理存儲位置，然后把記錄存儲在該位置上。查找時，通過同樣的轉(zhuǎn)換方法，可以直接得到所需要的記錄。4）倒排文件倒排文件是帶有輔索引的文件，其中輔索引是按照一些輔關(guān)鍵字來組織索引的（注意：索引文件是按照記錄的主關(guān)鍵字來構(gòu)造索引的，也叫主索引）。倒排文件是一種多關(guān)鍵字的索引文件，其中的索引不能唯一標(biāo)識記錄，往往同一索引指向若干記錄。1．空間數(shù)據(jù)庫1．4GIS的內(nèi)部數(shù)據(jù)結(jié)構(gòu)內(nèi)部數(shù)據(jù)結(jié)構(gòu)基本上可分為兩大類：矢量結(jié)構(gòu)和柵格結(jié)構(gòu)（也可以稱為矢量模型和柵格模型）（圖7-3）。兩類結(jié)構(gòu)都可用來描述地理實體的點、線、面三種基本類型。1．空間數(shù)據(jù)庫在地理信息系統(tǒng)的空間數(shù)據(jù)結(jié)構(gòu)中，柵格結(jié)構(gòu)的編碼方式主要有直接?xùn)鸥窬幋a、鏈碼、游程長度編碼、塊碼、四叉樹碼等；矢量結(jié)構(gòu)主要有坐標(biāo)序列編碼、樹狀索引編碼和二元拓?fù)渚幋a等編碼方法。1．空間數(shù)據(jù)庫

圖7-3：矢量結(jié)構(gòu)和柵格結(jié)構(gòu)1．空間數(shù)據(jù)庫1．4．1矢量模型在矢量模型中，現(xiàn)實世界的要素位置和范圍可以采用點、線或面表達(dá)，與它們在地圖上表示相似，每一個實體的位置是用它們在坐標(biāo)參考系統(tǒng)中的空間位置（坐標(biāo)）定義。點、線和多邊形用于表達(dá)不規(guī)則的地理實體在現(xiàn)實世界的狀態(tài)。矢量模型中的空間實體與要表達(dá)的現(xiàn)實世界中的空間實體具有一定的對應(yīng)關(guān)系。1．空間數(shù)據(jù)庫1．4．2柵格模型在柵格模型中，地理實體的位置和狀態(tài)是用它們占據(jù)的柵格的行、列來定義的。每個柵格的大小代表了定義的空間分辨率。由于位置是由柵格行列號定義的，所以特定的位置由距它最近的柵格記錄決定。柵格的值表達(dá)了這個位置上物體的類型或狀態(tài)。采用柵格方法，空間被劃分成大量規(guī)則格網(wǎng)，而且每個柵格取值可能不一樣?？臻g單元是柵格，每一個柵格對應(yīng)于一個特定的空間位置，如地表的一個區(qū)域，柵格的值表達(dá)了這個位置的狀態(tài)。1．空間數(shù)據(jù)庫2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2．1柵格數(shù)據(jù)結(jié)構(gòu)2．1．1定義柵格結(jié)構(gòu)是最簡單最直接的空間數(shù)據(jù)結(jié)構(gòu)，是指將地球表面劃分為大小均勻緊密相鄰的網(wǎng)格陣列，每個網(wǎng)格作為一個象元或象素由行、列定義，并包含一個代碼表示該象素的屬性類型或量值，或僅僅包括指向其屬性記錄的指針。因此，柵格結(jié)構(gòu)是以規(guī)則的陣列來表示空間地物或現(xiàn)象分布的數(shù)據(jù)組織，組織中的每個數(shù)據(jù)表示地物或現(xiàn)象的非幾何屬性特征。（a）點（b）線（c）面

圖7-4：點、線、區(qū)域的格網(wǎng)2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2．1．2特點柵格結(jié)構(gòu)的顯著特點是：屬性明顯，定位隱含，即數(shù)據(jù)直接記錄屬性的指針或?qū)傩员旧恚谖恢脛t根據(jù)行列號轉(zhuǎn)換為相應(yīng)的坐標(biāo)，也就是說定位是根據(jù)數(shù)據(jù)在數(shù)據(jù)集中的位置得到的。這種結(jié)構(gòu)容易實現(xiàn)，算法簡單，且易于擴(kuò)充、修改，也很直觀，特別是易于同遙感影像的結(jié)合處理，給地理空間數(shù)據(jù)處理帶來了極大的方便。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2．2決定柵格單元代碼的方式在決定柵格代碼時盡量保持地表的真實性，保證最大的信息容量。圖7-5所示的一塊矩形地表區(qū)域，內(nèi)部含有A、B、C三種地物類型，O點為中心點，將這個矩形區(qū)域近似地表示為柵格結(jié)構(gòu)中的一個柵格單元時，可根據(jù)需要，采取如下的方式之一來決定柵格單元的代碼。圖7-5：柵格單元代碼的確定2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2．2．1中心點法用處于柵格中心處的地物類型或現(xiàn)象特性決定柵格代碼，在圖7-5所示的矩形區(qū)域中，中心點O落在代碼為C的地物范圍內(nèi)，按中心點法的規(guī)則，該矩形區(qū)域相應(yīng)的柵格單元代碼為C，中心點法常用于具有連續(xù)分布特性的地理要素，如降雨量分布、人口密度圖等。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2．2．2面積占優(yōu)法以占矩形區(qū)域面積最大的地物類型或現(xiàn)象特性決定柵格單元的代碼，在圖7-5所示的例子中，顯見B類地物所占面積最大，故相應(yīng)柵格代碼定為B。面積占優(yōu)法常用于分類較細(xì)，地物類別斑塊較小的情況。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2．2．3重要性法根據(jù)柵格內(nèi)不同地物的重要性，選取最重要的地物類型決定相應(yīng)的柵格單元代碼，假設(shè)圖7-5中A類最重要的地物類型，即A比B和C類更為重要，則柵格單元的代碼應(yīng)為A。重要性法常用于具有特殊意義而面積較小的地理要素，特別是點、線狀地理要素，如城鎮(zhèn)、交通樞紐、交通線、河流水系等，在柵格中代碼應(yīng)盡量表示這些重要地物。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2．2．4百分比法根據(jù)矩形區(qū)域內(nèi)各地理要素所占面積的百分比數(shù)確定柵格單元的代碼，如可記面積最大的兩類BA，也可以根據(jù)B類和A類所占面積百分比數(shù)在代碼中加入數(shù)字。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2．3編碼方法2．3．1直接?xùn)鸥窬幋a直接編碼就是將柵格數(shù)據(jù)看作一個數(shù)據(jù)矩陣，逐行（或逐列）逐個記錄代碼，可以每行都從左到右逐個象元記錄，也可以奇數(shù)行地從左到右而偶數(shù)行地從右向左記錄，為了特定目的還可采用其他特殊的順序（圖7-6）。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼

圖7-6：一些常用的柵格排列順序2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2．3．2壓縮編碼方法目前有一系列柵格數(shù)據(jù)壓縮編碼方法，如鍵碼、游程長度編碼、塊碼和四叉樹編碼等。其目的，就是用盡可能少的數(shù)據(jù)量記錄盡可能多的信息，其類型又有信息無損編碼和信息有損編碼之分。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼1）鏈碼（ChainCodes）鏈碼又稱為弗里曼鏈碼[Freeman]或邊界鏈碼，優(yōu)點，鏈碼可以有效地壓縮柵格數(shù)據(jù)，而且對于估算面積、長度、轉(zhuǎn)折方向的凹凸度等運算十分方便，比較適合于存儲圖形數(shù)據(jù)。缺點是對邊界進(jìn)行合并和插入等修改編輯工作比較困難，對局部的修改將改變整體結(jié)構(gòu)，效率較低，而且由于鏈碼以每個區(qū)域為單位存儲邊界，相鄰區(qū)域的邊界將被重復(fù)存儲而產(chǎn)生冗余。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼2）游程長度編碼游程長度編碼是柵格數(shù)據(jù)壓縮的重要編碼方法，它的基本思路是：對于一幅柵格圖像，常常有行（或列）方向上相鄰的若干點具有相同的屬性代碼，因而可采取某種方法壓縮那些重復(fù)的記錄內(nèi)容。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼3）塊碼塊碼是游程長度編碼擴(kuò)展到二維的情況，采用方形區(qū)域作為記錄單元，每個記錄單元包括相鄰的若干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置（行、列號）和半徑，再加上記錄單位的代碼組成。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼4）四叉樹四叉樹又稱四元樹或四分樹，是最有效的柵格數(shù)據(jù)壓縮編碼方法之一，絕大部分圖形操作和運算都可以直接在四叉樹結(jié)構(gòu)上實現(xiàn)，因此四叉樹編碼既壓縮了數(shù)據(jù)量，又可大大提高圖形操作的效率。四叉樹將整個圖像區(qū)逐步分解為一系列被單一類型區(qū)域內(nèi)含的方形區(qū)域，最小的方形區(qū)域為一個柵格象元，分割的原則是，將圖像區(qū)域劃分為四個大小相同的象限，而每個象限又可根據(jù)一定規(guī)則判斷是否繼續(xù)等分為次一層的四個象限，其終止判據(jù)是，不管是哪一層上的象限，只要劃分到僅代表一種地物或符合既定要求的少數(shù)幾種地物時，則不再繼續(xù)劃分，否則一直劃分到單個柵格象元為止。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼（a）塊碼分割（b）四叉樹分割2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼

（c）b的四叉樹編碼

圖7-7：四叉樹編碼2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼四叉樹編碼具有可變的分辨率，并且有區(qū)域性質(zhì)，壓縮數(shù)據(jù)靈活，許多運算可以在編碼數(shù)據(jù)上直接實現(xiàn)，大大地提高了運算效率，是優(yōu)秀的柵格壓縮編碼之一。2．柵格數(shù)據(jù)結(jié)構(gòu)及其編碼3．矢量數(shù)據(jù)結(jié)構(gòu)及其編碼3．1矢量數(shù)據(jù)結(jié)構(gòu)3．1．1定義矢量結(jié)構(gòu)，即通過記錄坐標(biāo)的方式盡可能精確地表示點、線、多邊形等地理實體，坐標(biāo)空間設(shè)為連續(xù)，允許任意位置、長度和面積的精確定義。3．1．2特點矢量結(jié)構(gòu)的特點是：定位明顯、屬性隱含，其定位是根據(jù)坐標(biāo)直接存儲的，而屬性則一般存于文件頭或數(shù)據(jù)結(jié)構(gòu)中某些特定的位置上。3．矢量數(shù)據(jù)結(jié)構(gòu)及其編碼這種特點使得其圖形運算的算法總體上比柵格數(shù)據(jù)結(jié)構(gòu)復(fù)雜的多，有些甚至難以實現(xiàn)，當(dāng)然有些地方也有所便利和獨到之處，在計算長度、面積、形狀和圖形編輯、幾何變換操作中，矢量結(jié)構(gòu)有很高的效率和精度，而在疊加運算、鄰域搜索等操作時則比較困難。3．矢量數(shù)據(jù)結(jié)構(gòu)及其編碼3．2編碼方法3．2．1點實體3．2．2線實體

圖7-8：（a）點實體的編碼，（b）線實體的編碼3．矢量數(shù)據(jù)結(jié)構(gòu)及其編碼3．2．3多邊形1）坐標(biāo)序列法（Spaghetti方式）圖7-9：坐標(biāo)序列法表示的多邊形3．矢量數(shù)據(jù)結(jié)構(gòu)及其編碼坐標(biāo)序列法文件結(jié)構(gòu)簡單，易于實現(xiàn)以多邊形為單位的運算和顯示。這種方法的缺點是：（1．1）多邊形之間的公共邊界被數(shù)字化和存儲兩次，由此產(chǎn)生冗余和碎屑多邊形；（1．2）每個多邊形自成體系而缺少鄰域信息，難以進(jìn)行鄰域處理，如消除某兩個多邊形之間的共同邊界；（1．3）島只作為一個單個的圖形建造，沒有與外包多邊形的聯(lián)系；（1．4）不易檢查拓?fù)溴e誤。這種方法可用于簡單的粗精度制圖系統(tǒng)中。3．矢量數(shù)據(jù)結(jié)構(gòu)及其編碼2）樹狀索引編碼法該法采用樹狀索引以減少數(shù)據(jù)冗余并間接增加鄰域信息，方法是對所有邊界點進(jìn)行數(shù)字化，將坐標(biāo)對以順序方式存儲，由點索引與邊界線號相聯(lián)系，以線索引與各多邊形相聯(lián)系，形成樹狀索引結(jié)構(gòu)。

圖7-10：線與多邊形之間的樹狀索引3．矢量數(shù)據(jù)結(jié)構(gòu)及其編碼

圖7-11：點與邊界線之間的樹狀索引3．矢量數(shù)據(jù)結(jié)構(gòu)及其編碼3）拓?fù)浣Y(jié)構(gòu)編碼法要徹底解決鄰域和島狀信息處理問題必須建立一個完整的拓?fù)潢P(guān)系結(jié)構(gòu)，這種結(jié)構(gòu)應(yīng)包括以下內(nèi)容：唯一標(biāo)識，多邊形標(biāo)識，外包多邊形指針，鄰接多邊形指針，邊界鏈接，范圍（最大和最小x、y坐標(biāo)值）。采用拓?fù)浣Y(jié)構(gòu)編碼可以較好地解決空間關(guān)系查詢等問題，但增加了算法的復(fù)雜性和數(shù)據(jù)庫的大小。3．矢量數(shù)據(jù)結(jié)構(gòu)及其編碼矢量編碼最重要的是信息的完整性和運算的靈活性，這是由矢量結(jié)構(gòu)自身的特點所決定的，目前并無統(tǒng)一的最佳的矢量結(jié)構(gòu)編碼方法，在具體工作中應(yīng)根據(jù)數(shù)據(jù)的特點和任務(wù)的要求而靈活設(shè)計。3．矢量數(shù)據(jù)結(jié)構(gòu)及其編碼4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法4．1柵格結(jié)構(gòu)與矢量結(jié)構(gòu)的比較柵格結(jié)構(gòu)與矢量結(jié)構(gòu)似乎是兩種截然不同的空間數(shù)據(jù)結(jié)構(gòu)，柵格結(jié)構(gòu)“屬性明顯、位置隱含”，而矢量結(jié)構(gòu)“位置明顯、屬性隱含”，柵格數(shù)據(jù)操作總的來說比較容易實現(xiàn)，尤其是作為斑塊圖件的表示更易于為人們接受；而矢量數(shù)據(jù)操作則比較復(fù)雜，許多分析操作（如兩張地圖的覆蓋操作，點或線狀地物的鄰域搜索等）用矢量結(jié)構(gòu)實現(xiàn)十分困難，矢量結(jié)構(gòu)表達(dá)線狀地物是比較直觀的，而面狀地物則是通過對邊界的描述而表達(dá)。4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法無論哪種結(jié)構(gòu)，數(shù)據(jù)精度和數(shù)據(jù)量都是一對矛盾，要提高精度，柵格結(jié)構(gòu)需要更多的柵格單元，而矢量結(jié)構(gòu)則需記錄更多的線段結(jié)點。一般來說，柵格結(jié)構(gòu)只是矢量結(jié)構(gòu)在某種程度上的一種近似，如果要使柵格結(jié)構(gòu)描述的圖件取得與矢量結(jié)構(gòu)同樣的精度，甚至僅僅在量值上接近，則數(shù)據(jù)也要比后者大得多。

表7-2：矢量格式與柵格格式的比較4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法4．2相互轉(zhuǎn)換算法矢量結(jié)構(gòu)與網(wǎng)格結(jié)構(gòu)的相互轉(zhuǎn)換，是地理信息系統(tǒng)的基本功能之一，目前已經(jīng)發(fā)展了許多高效的轉(zhuǎn)換算法；但是，從柵格數(shù)據(jù)到矢量數(shù)據(jù)的轉(zhuǎn)換，特別是掃描圖像的自動識別，仍然是目前研究的重點。4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法點狀實體，每個實體僅由一個坐標(biāo)對表示，其矢量結(jié)構(gòu)和柵格結(jié)構(gòu)的相互轉(zhuǎn)換基本上只是坐標(biāo)精度變換問題，不存在太大的技術(shù)問題。線實體的矢量結(jié)構(gòu)由一系列坐標(biāo)對表示，在變?yōu)闁鸥窠Y(jié)構(gòu)時，除把序列中坐標(biāo)對變?yōu)闁鸥裥辛凶鴺?biāo)外，還需根據(jù)柵格精度要求，在坐標(biāo)點之間插滿一系列柵格點，這也容易由兩點式直線方程得到。線實體由柵格結(jié)構(gòu)變?yōu)槭噶拷Y(jié)構(gòu)與將多邊形邊界表示為矢量結(jié)構(gòu)相似，因此以下重點討論多邊形（面實體）的矢量結(jié)構(gòu)與柵格結(jié)構(gòu)相互轉(zhuǎn)換。4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法4．2．1矢量格式向柵格格式的轉(zhuǎn)換矢量格式向柵格格式轉(zhuǎn)換又稱為多邊形填充，就是在矢量表示的多邊形邊界內(nèi)部的所有柵格點上賦以相應(yīng)的多邊形編碼，從而形成類似圖7-4的柵格數(shù)據(jù)陣列。幾種主要的算法描述如下：4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法1）內(nèi)部點擴(kuò)散算法該算法由每個多邊形一個內(nèi)部點（種子點）開始，向其八個方向的鄰點擴(kuò)散，判斷各個新加入點是否在多邊形邊界上，如果是邊界上，則該新加入點不作為種子點，否則把非邊界點的鄰點作為新的種子點與原有種子點一起進(jìn)行新的擴(kuò)散運算，并將該種子點賦以該多邊形的編號。重復(fù)上述過程直到所有種子點填滿該多邊形并遇到邊界停止為止。擴(kuò)散算法程序設(shè)計比較復(fù)雜，并且在一定的柵格精度上，如果復(fù)雜圖形的同一多邊形的兩條邊界落在同一個或相鄰的兩個柵格內(nèi)，會造成多邊形不連通，這樣一個種子點不能完成整個多邊形的填充。4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法2）復(fù)數(shù)積分算法對全部柵格陣列逐個柵格單元地判斷該柵格歸屬的多邊形編碼，判別方法是由待判點對每個多邊形的封閉邊界計算復(fù)數(shù)積分，對某個多邊形，如果積分值為2

r，則該待判點屬于此多邊形，賦以多邊形編號，否則在此多邊形外部，不屬于該多邊形。4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法3）射線算法和掃描算法射線算法可逐點判斷數(shù)據(jù)柵格點在某多邊形之外或在多邊形內(nèi)，由待判點向圖外某點引射線，判斷該射線與某多邊形所有邊界相交的總次數(shù)，如相交偶數(shù)次，則待判點在該多邊形外部，如為奇數(shù)次，則待判點在該多邊形內(nèi)部（圖7-12）。采用射線算法，要注意的是：射線與多邊形邊界相交時，有一些特殊情況會影響交點的個數(shù)，必須予以排除（圖7-13）。4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法掃描算法是射線算法的改進(jìn)，將射線改為沿柵格陣列列或行方向掃描線，判斷與射線算法相似。掃描算法省去了計算射線與多邊形邊界交點的大量運算，大大提高了效率。

圖7-12：射線算法4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法

圖7-13：射線算法的特殊情況4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法4）邊界代數(shù)算法邊界代數(shù)多邊形填充算法是一種基于積分思想的矢量格式向柵格格式轉(zhuǎn)換算法，它適合于記錄拓?fù)潢P(guān)系的多邊形矢量數(shù)據(jù)轉(zhuǎn)換為柵格結(jié)構(gòu)。圖7-15表示轉(zhuǎn)換單個多邊形的情況，多邊形編號為a，模仿積分求多邊形區(qū)域面積的過程，初始化的柵格陣列各柵格值為零，以柵格行列為參考坐標(biāo)軸，由多邊形邊界上某點開始順時針?biāo)阉鬟吔缇€，當(dāng)邊界上行時（圖7-15-a），位于該邊界左側(cè)的具有相同行坐標(biāo)的所有柵格被減去a；當(dāng)邊界下行時（圖7-15-b），該邊界左邊（前進(jìn)方向看為右側(cè)）所有柵格點加一個值a，邊界搜索完畢則完成了多邊形的轉(zhuǎn)換。4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法

圖7-15：單個多邊形的轉(zhuǎn)換4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法

圖7-16：多個多邊形的轉(zhuǎn)換4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法邊界代數(shù)法與前述其他算法的不同之處，在于它不是逐點判斷與邊界的關(guān)系完成轉(zhuǎn)換，而是根據(jù)邊界的拓?fù)湫畔?，通過簡單的加減代數(shù)運算將邊界位置信息動態(tài)地賦給各柵格點，實現(xiàn)了矢量格式到柵格格式的高速轉(zhuǎn)換，而不需要考慮邊界與搜索軌跡之間的關(guān)系，因此算法簡單、可靠性好，各邊界弧段只被搜索一次，避免了重復(fù)計算。4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法4．2．2柵格格式向矢量格式的轉(zhuǎn)換多邊形柵格格式向矢量格式轉(zhuǎn)換就是提取以相同的編號的柵格集合表示的多邊形區(qū)域的邊界和邊界的拓?fù)潢P(guān)系，并表示由多個小直線段組成的矢量格式邊界線的過程。4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法1）轉(zhuǎn)換步驟柵格格式向矢量格式轉(zhuǎn)換包括以下四個步驟：（1．1）多邊形邊界提?。?．2）邊界線追蹤（1．3）拓?fù)潢P(guān)系生成（1．4）去除多余點及曲線圓滑4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法2）多邊形柵格轉(zhuǎn)矢量的雙邊界搜索算法算法的基本思想是通過邊界提取，將左右多邊形信息保存在邊界點上，每條邊界弧段由兩個并行的邊界鏈組成，分別記錄該邊界弧段的左右多邊形編號。邊界線搜索采用2*2柵格窗口，在每個窗口內(nèi)的四個柵格數(shù)據(jù)的模式，可以唯一地確定下一個窗口的搜索方向和該弧段的拓?fù)潢P(guān)系，極大地加快了搜索速度，拓?fù)潢P(guān)系也很容易建立。4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法具體步驟如下：（2．1）邊界點和結(jié)點提?。?．2）邊界線搜索與左右多邊形信息記錄（2．3）多余點去除4．矢柵結(jié)構(gòu)的比較及轉(zhuǎn)換算法5．空間索引機(jī)制5．1索引概念空間索引就是指依據(jù)空間對象的位置和形狀或空間對象之間的某種空間關(guān)系按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包含空間對象的概要信息，如對象的標(biāo)識、外接矩形及指向空間對象實體的指針。5．2索引類型5．2．1格網(wǎng)型空間索引格網(wǎng)型空間索引思路比較簡單了，容易理解和實現(xiàn)。其基本思想是將研究區(qū)域用橫豎線條劃分大小相等和不等的格網(wǎng)，記錄每一個格網(wǎng)所包含的空間實體。當(dāng)用戶進(jìn)行空間查詢時，首先計算出用戶查詢對象所在格網(wǎng)，然后再在該網(wǎng)格中快速查詢所選空間實體，這樣一來就大大地加速了空間索引的查詢速度。5．空間索引機(jī)制5．2．2BSP樹空間索引BSP樹是一種二叉樹，它將空間逐級進(jìn)行一分為二的劃分（圖7-19）。BSP樹能很好地與空間數(shù)據(jù)庫中空間對象的分布情況相適應(yīng)，但對一般情況而言，BSP樹深度較大，對各種操作均有不利影響。5．空間索引機(jī)制

圖7-19：BSP樹5．空間索引機(jī)制5．2．3KDB樹空間索引KDB樹是B樹向多維空間的一種發(fā)展。它對于多維空間中的點進(jìn)行索引具有較好的動態(tài)特性，刪除和增加空間點對象也可以很方便地實現(xiàn)；其缺點是不直接支持占據(jù)一定空間范圍的地物要素，如二維空間中的線和面。5．空間索引機(jī)制5．2．4R樹和R+樹R樹根據(jù)地物的最小外包矩形建立（圖7-20），可以直接對空間中占據(jù)一定范圍的空間對象進(jìn)行索引。R樹的每一個結(jié)點N都對應(yīng)著磁盤頁D（N）和區(qū)域I（N），如果結(jié)點不是葉結(jié)點，則該結(jié)點的所有子結(jié)點的區(qū)域都在區(qū)域I（N）的范圍之內(nèi)，而且存儲在磁盤頁D（N）中；如果結(jié)點是葉結(jié)點，那么磁盤頁D（N）中存儲的將是區(qū)域