3D GIS空間索引技術(shù)

1、3D GIS空間索引技術(shù)3DGIS是新一代GIS技術(shù)的重要分支，是進(jìn)行全方位、多層次、多要素時(shí)空分析的基礎(chǔ), 開發(fā)結(jié)構(gòu)簡單、功能完善的真3DGIS軟件是當(dāng)前GIS研究人員的重要目標(biāo)。3DGIS需要管理 大量的三維空間對象，且常常需要根據(jù)空間位置對這些對象進(jìn)行查詢、檢索和顯示操作。 為了處理這類空間操作，傳統(tǒng)的關(guān)系數(shù)據(jù)庫搜索方法需要花費(fèi)大量的磁盤訪問時(shí)間和空間 運(yùn)算時(shí)間。為了提高檢索效率，傳統(tǒng)的關(guān)系數(shù)據(jù)庫一般都建立一系列的索引機(jī)制，如B+樹 等。目前常用的索引機(jī)制多是一維索引，無法有效處理3DGIS空間數(shù)據(jù)庫中的三維空間地 理實(shí)體。因此，必須為3DGIS空間數(shù)據(jù)庫建立專門的索引機(jī)制空間索引?？臻g

2、索引是指根據(jù)空間要素的地理位置、形狀或空間對象之間的某種空間關(guān)系，按照 一定規(guī)律排列的數(shù)據(jù)結(jié)構(gòu)，它介于空間操作算法和空間對象之間，篩選、排除與特定的空 間操作無關(guān)的空間對象。空間索引機(jī)制是快速、高效地查詢、檢索和顯示地理空間數(shù)據(jù)的 基礎(chǔ)，其性能優(yōu)劣直接影響GIS空間數(shù)據(jù)庫的性能，關(guān)系到3DGIS軟件系統(tǒng)的整體運(yùn)行狀 況。一、三維空間索引簡介3DGIS是2DGIS在三維空間內(nèi)的延展，是布滿整個(gè)三維空間內(nèi)的GIS，它與2DGIS的差 異主要體現(xiàn)在空間位置的確定、空間拓?fù)潢P(guān)系的描述與空間分析的延展方向上。3DGIS將三 維空間坐標(biāo)（x，y，z）作為獨(dú)立的參數(shù)來構(gòu)建空間實(shí)體對象模型，能夠?qū)崿F(xiàn)空間實(shí)體的

3、真 三維可視化，以立體造型來展現(xiàn)空間地理現(xiàn)象，它不僅能夠表達(dá)空間實(shí)體之間的平面關(guān)系， 還能夠表達(dá)其垂向關(guān)系，在此基礎(chǔ)上進(jìn)行復(fù)雜的三維空間分析與操作。在GIS由二維擴(kuò)充到三維后，其處理的空間對象也由二維空間中的“點(diǎn)、線、面”擴(kuò) 充到三維空間中的“點(diǎn)、線、面、體”。2DGIS對平面空間的“有限-互斥-完整”剖分是基 于面的劃分，而3DGIS對三維空間的“有限-互斥-完整”剖分則是基于體的劃分。在3DGIS 空間數(shù)據(jù)庫中，空間實(shí)體的表達(dá)形式復(fù)雜，各種空間操作不僅計(jì)算量大，而且多具有面向 鄰域的特點(diǎn)。因此，在3DGIS中，由于空間維數(shù)的增加和空間實(shí)體關(guān)系復(fù)雜度的提高而導(dǎo) 致三維空間數(shù)據(jù)的海量性。海量數(shù)

4、據(jù)的存儲與管理需要更加高效的空間數(shù)據(jù)結(jié)構(gòu)和空間索 引機(jī)制。目前成熟的空間索引算法多集中在二維空間索引上，如網(wǎng)格索引、四叉樹索引等, 而對3DGIS的空間索引問題研究較少。對低維空間數(shù)據(jù)而言，二維空間索引的索引效率較 高，并且多數(shù)可以進(jìn)行擴(kuò)展以支持高維數(shù)據(jù)集。但應(yīng)用實(shí)踐顯示，僅僅簡單地將二維空間 索引維數(shù)增加到三維，其效率并不高，且很多索引結(jié)構(gòu)都是針對特定空間查詢操作而設(shè)計(jì) 的，不具有通用性。因此，需要研究3DGIS所使用的空間索引技術(shù)。設(shè)計(jì)3DGIS空間索引面臨的主要困難是：三維空間實(shí)體的空間關(guān)系比較復(fù)雜，有時(shí)甚 至呈一種相對無序的狀態(tài)。從本質(zhì)上看，3DGIS對空間索引的要求與2DGIS基本類

5、似，但在 數(shù)據(jù)采集、數(shù)據(jù)庫維護(hù)、數(shù)據(jù)操作、界面設(shè)計(jì)等方面要比2DGIS復(fù)雜得多。目前的三維空 間索引大多是從二維空間索引的基礎(chǔ)上發(fā)展而來的。與二維空間索引相似，三維空間索引 方法也是基于空間數(shù)據(jù)的層次化聚類原則，結(jié)構(gòu)上類似于早期用于數(shù)據(jù)檢索的B+樹：數(shù)據(jù) 矢量存儲在數(shù)據(jù)節(jié)點(diǎn)，空間位置鄰近的矢量盡可能存儲于同一節(jié)點(diǎn)。數(shù)據(jù)節(jié)點(diǎn)之間以層次 化目錄結(jié)構(gòu)來組織，每一個(gè)目錄節(jié)點(diǎn)都指向下一級的一個(gè)子樹。目前，索引結(jié)構(gòu)大都采用平衡樹的概念，即從根節(jié)點(diǎn)到所有數(shù)據(jù)節(jié)點(diǎn)的訪問長度（索 引高度）相同（但在插入和刪除操作后可能會有改變），在樹的形狀上表現(xiàn)為高度一致性。 從任意節(jié)點(diǎn)到數(shù)據(jù)節(jié)點(diǎn)的訪問長度稱為節(jié)點(diǎn)的級，數(shù)據(jù)節(jié)

6、點(diǎn)對應(yīng)第0級。二、空間索引結(jié)構(gòu)分類根據(jù)空間索引結(jié)構(gòu)的演化過程，空間索引方法可分為4大類，即基于二叉樹的索引技 術(shù)、基于B樹的索引技術(shù)、基于Hashing的格網(wǎng)技術(shù)和空間目標(biāo)排序法。空間索引的基本方法是將整個(gè)空間分割成不同的搜索區(qū)域，以一定的順序在這些區(qū)域 中查找空間實(shí)體。針對3DGIS應(yīng)用的實(shí)際，按照搜索分割對象不同，可將空間索引分為3 類，即基于點(diǎn)區(qū)域劃分的索引方法、基于面區(qū)域劃分的索引方法和基于三維體區(qū)域劃分的 索引方法。常見的基于點(diǎn)區(qū)域劃分的索引結(jié)構(gòu)有KD樹、B樹、KDB樹和點(diǎn)四叉樹等；基于 面區(qū)域劃分的索引結(jié)構(gòu)有區(qū)域四叉樹、R樹系列和格網(wǎng)索引機(jī)制等；基于三維體區(qū)域劃分的 索引結(jié)構(gòu)有Mo

7、r ton編碼、無邊界Qu編碼、球面QTM編碼以及球面HSDS編碼等。按照空間分割方法將空間分割分為規(guī)則分割法和對象分割法。規(guī)則分割法是將地理空 間按照某種規(guī)則或半規(guī)則的方式進(jìn)行分割，分割單元間接地與空間要素相關(guān)聯(lián)，空間要素 的幾何形狀可能被分割到幾個(gè)相鄰的單元中，這時(shí)空間要素的描述保持完整，而空間索引 單元只存儲空間要素地址的參考信息。在對象分割法中，索引空間的分割直接由空間要素 確定，索引單元包括空間要素地址的參考信息和空間要素的外包絡(luò)矩形。規(guī)則分割法包括 規(guī)則網(wǎng)格、BSP樹、八叉樹、KD樹、KDB樹和R樹系列等，對象分割法一般通過層次包圍體 （bounding volume hierar

8、chy）實(shí)現(xiàn)。下文按照分割方法對常見的空間索引結(jié)構(gòu)進(jìn)行詳細(xì) 討論。三、常見的三維空間索引結(jié)構(gòu)（一）對象分割法對象分割法一般由層次包圍體實(shí)現(xiàn)。層次包圍體是一種簡單的樹結(jié)構(gòu)，它用一些特定 的方法對空間實(shí)體對象進(jìn)行分割，最終將樹的每一個(gè)節(jié)點(diǎn)保存為所在層次的包圍體信息， 葉子節(jié)點(diǎn)則存儲基本對象。如當(dāng)對兩個(gè)物體做碰撞檢測時(shí)，首先檢測兩者的包圍體是否有 交，若不相交，則說明兩個(gè)物體未相交，否則再進(jìn)一步對兩個(gè)物體進(jìn)行檢測。求包圍體的 交比求物體的交要簡單得多，以便快速排除很多不相交的物體，從而加速檢索算法。常見 的包圍體有5種：包圍球（Spheres ）。包圍球是一種最簡單的包圍體，易于計(jì)算，非常易于做重疊

9、測 試和節(jié)點(diǎn)修改，但缺點(diǎn)是與物體的逼近程度較差。軸向包圍盒（Axisaligned Bounding Box，ABB）。軸向包圍盒是一種長方體的包圍 體，其各軸的方向與坐標(biāo)軸的方向一致，它也是一種易于做重疊測試的包圍體，但與物體 的逼近程度也較差。方向包圍盒（Oriented Bounding Box，OBB）:方向包圍盒是一個(gè)任意方向的長方體 包圍體，與前二者相比，它可提供非常緊湊的逼近效果，而且更新計(jì)算的效率較高。4離散方向多面體（Discre te Orien tat ion Poly topes， DOP）:離散方向多面體是一 個(gè)凸多面體，它的面由一些半空間所確定，這些半空間的外法向是

10、從k個(gè)固定的方向中選 取的。與包圍球和軸向包圍盒相比，離散方向多面體對物體的逼近程度相對較好，與方向 包圍盒和凸包相比，它的重疊測試和節(jié)點(diǎn)修改耗費(fèi)相對較低。5.凸包Convex Hull）。凸包是一種極端情況，它提供了物體最緊湊的凸包圍體，但它 的重疊測試和節(jié)點(diǎn)修改的耗費(fèi)都相當(dāng)高。層次包圍體的基本算法包括包圍體的計(jì)算、分割和相交判斷等。一般以上幾種包圍體 （包圍盒）的緊湊程度依次增大，但相應(yīng)地計(jì)算復(fù)雜度也越來越高。（二）規(guī)則分割法規(guī)則分割法將空間按照某些規(guī)則分割成均勻的單元，然后將空間中每個(gè)實(shí)體對應(yīng)到一 個(gè)或多個(gè)單元中，這一方法很適于實(shí)體在空間中均勻分布的稀疏環(huán)境。但對于更為一般的 環(huán)境，則很

11、難選擇一個(gè)最優(yōu)的剖分尺寸，若選擇不當(dāng)，會導(dǎo)致空間耗費(fèi)大，計(jì)算效率低。 常用的空間剖分法有規(guī)則網(wǎng)格、KD樹、KDB樹、BSP樹、八叉樹和R樹系列等（圖1）。規(guī)則格網(wǎng)空間索引的思路簡單，容易理解和實(shí)現(xiàn)，其基本思想是將研究區(qū)域用橫豎線 劃分為大小相等或不等的網(wǎng)格，記錄每一個(gè)網(wǎng)格所包含的地理對象。為了建立空間索引的 線性表，可將空間格網(wǎng)按Mor ton碼編碼，建立Mor ton碼與空間對象的關(guān)系。當(dāng)用戶進(jìn)行 空間查詢時(shí)，首先計(jì)算出用戶查詢對象所在的網(wǎng)格，然后通過該網(wǎng)格快速查詢所選地理對象。規(guī)則格網(wǎng)空間索引的查詢速度快，但數(shù)據(jù)量大，數(shù)據(jù)維護(hù)較為困難。KD樹（K維搜索二叉樹）是將二叉樹推廣到多維數(shù)據(jù)的一種

12、主存數(shù)據(jù)結(jié)構(gòu)，它是一個(gè)K 維空間中的二叉樹。在每個(gè)內(nèi)部節(jié)點(diǎn)中，用一個(gè)K-1維的超平面（如二維空間中的線）將 節(jié)點(diǎn)所表示的K維空間分成兩部分，這些超平面在K個(gè)可能的方向上交替出現(xiàn)，而且在每 一個(gè)超平面中至少包括一個(gè)點(diǎn)數(shù)據(jù)。在二維坐標(biāo)下，根據(jù)插入點(diǎn)的縱橫坐標(biāo)將空間進(jìn)行交 叉分裂，把空間數(shù)據(jù)遞歸地劃分為一個(gè)二叉樹。為了將KD樹存儲組織到外存，將其與B樹 結(jié)合，形成KDB樹。八叉樹是對二維GIS中四叉樹索引進(jìn)行擴(kuò)展的一種三維空間數(shù)據(jù)結(jié)構(gòu)，其基本思想是 將三維區(qū)域劃分成三維柵格，每一個(gè)小正方體（稱為一個(gè)體元）有一個(gè)或多個(gè)屬性數(shù)據(jù)。 屬性相同的區(qū)域用大塊表示，而復(fù)雜區(qū)域則用小塊表示，以一大塊分為八小塊進(jìn)行

13、規(guī)則劃 分。建立八叉樹索引的難點(diǎn)一是空間分割時(shí)應(yīng)遵循的原則，這可通過規(guī)定一個(gè)閾值k （表示 空間對象的個(gè)數(shù)）來解決，即只有當(dāng)區(qū)域中空間對象的個(gè)數(shù)多于k個(gè)時(shí)，該區(qū)域才需要進(jìn) 一步劃分；二是分辨率問題（即空間分割時(shí)允許達(dá)到的最小子區(qū)是多大），這可以通過規(guī)定 一個(gè)不再需要分割的體元大小來解決。BSP （Binary Space Par tition）樹采用二叉空間分割，其基本思想是：任何平面都可 以將空間分割成兩個(gè)互不相交的半空間，所有位于這個(gè)平面一側(cè)的點(diǎn)定義了一個(gè)半空間， 位于另一側(cè)的點(diǎn)定義了另一個(gè)半空間。此外，如果在任何半空間中有一個(gè)平面，它會進(jìn)一 步將此半空間分割為更小的兩個(gè)子空間?？梢允褂枚?/p>

14、邊形列表將這一過程進(jìn)行下去，當(dāng)子 空間中僅存在單個(gè)平面時(shí)，即可構(gòu)造出一個(gè)描述三維實(shí)體對象層次結(jié)構(gòu)的二叉樹（BSP樹）。 在這個(gè)樹中，一個(gè)進(jìn)行分割的多邊形被存儲在樹的節(jié)點(diǎn)，所有位于子空間中的多邊形都在 相應(yīng)的子樹上。這一規(guī)則也適用于樹中的每一個(gè)節(jié)點(diǎn)。構(gòu)造BSP樹的關(guān)鍵是如何在三維空 間中快速確定分割平面，以使生成的BSP樹盡量趨于平衡。R樹是近年應(yīng)用最廣泛的空間索引方法之一，可擴(kuò)展為支持更高維的數(shù)據(jù)集。R樹采用 最小約束矩形來遞歸分解索引空間，其存儲效率相對較高。但R樹的區(qū)域之間經(jīng)常產(chǎn)生重 疊（這種重疊通常會隨數(shù)據(jù)量或空間維數(shù)的增加而劇增），因此區(qū)域搜索可能需要沿多條路 徑進(jìn)行，從而降低了搜索效

15、率。在3DGIS中，通常需采用啟發(fā)式算法來降低三維R樹節(jié)點(diǎn) 的空白區(qū)域、各分支的重疊區(qū)域以及外包范圍的體積，從而減少各分支的重疊區(qū)域，提高 節(jié)點(diǎn)利用率，改進(jìn)R樹的性能。如可采用球形或規(guī)則多面體作為三維空間對象的外包圍， 從而避免使用正六面體作為外包圍分解三維空間所造成的大量重疊區(qū)域和空白區(qū)域。國內(nèi) 外學(xué)者對R樹提出了許多不同的擴(kuò)展，包括R+樹、R*樹等。R+樹雖然避免了區(qū)域的重疊，但 它可能需要在不同的節(jié)點(diǎn)中存儲同一個(gè)區(qū)域的標(biāo)識，從而降低其存儲效率。R*樹則盡量減小 節(jié)點(diǎn)間的重疊面積，它對上溢節(jié)點(diǎn)進(jìn)行刪除，并強(qiáng)制重插入該節(jié)點(diǎn)中的所有對象。圖1常見的規(guī)則分割法oTP r-11 11 1(e) R

16、樹（三）組合索引技術(shù)從空間索引結(jié)構(gòu)的演化進(jìn)程看，空間索引技術(shù)的發(fā)展實(shí)際上就是針對不斷出現(xiàn)的新需 求，不斷將各種索引技術(shù)重組、改進(jìn)索引方法的過程。例如，為了能索引復(fù)雜的空間目標(biāo), 提出了適合索引二維空間目標(biāo)的基于實(shí)體標(biāo)志重復(fù)存儲技術(shù)的MKD樹；為了將KD樹存儲組 織到外存，將其與B樹結(jié)合，提出了 KDB樹；為了減少空間目標(biāo)的重復(fù)存儲和空間映射， 提出SKI）樹；為了減少查詢中對外存的訪問次數(shù)，提出了 Cell樹；為了解決R*樹適合高維數(shù)據(jù)集的問題，提出X樹等。在3DGIS的實(shí)際應(yīng)用中，往往只有結(jié)合多種技術(shù)才能將空間索引的功能充分發(fā)揮出來。 例如，針對三維城市模型逼真可視化的需要，引入了一種基于R

17、*樹的多尺度空間數(shù)據(jù)庫索 引LOD-OR樹。LOD-OR樹利用八叉樹索引限制了 R*樹表示的空間，減輕了 R*樹插入、刪除的 開銷，并在查找性能上比R*樹有顯著的提高，且索引數(shù)據(jù)量越大，效果越明顯；它還采用 細(xì)節(jié)層次索引方法，在記錄的對象中加入三維實(shí)體的LOD信息，可以對各種尺度的對象根 據(jù)其大小以及與視點(diǎn)的距離、角度的不同，顯示不同的細(xì)節(jié)。這不但保證了實(shí)時(shí)快速地產(chǎn) 生真實(shí)感三維場景，同時(shí)由于綜合利用了數(shù)據(jù)庫管理技術(shù)，也兼顧了不同尺度的空間查詢 和分析等操作。在城鎮(zhèn)管網(wǎng)信息系統(tǒng)UPNIS中，采用了一種基于固定三維網(wǎng)格空間劃分和 面向類對象的二級查詢技術(shù)的八叉樹空間索引機(jī)制，有效解決了管網(wǎng)系統(tǒng)中

18、三維空間實(shí)體 的空間查詢，能夠縮小空間查詢范圍，提高查詢效率，進(jìn)而提高系統(tǒng)的整體性能。另外， 將對象分割與規(guī)則分割結(jié)合，用層次包圍體表示三維實(shí)體的邊界層次，然后建立三維空間 索引（如BSP索引或八叉樹索引），可以加速三維空間檢索，這種混合索引技術(shù)現(xiàn)在已廣泛 應(yīng)用于三維場景實(shí)時(shí)繪制（包括可見性判斷、碰撞檢測、光線追蹤和輻射度計(jì)算等）。四、3DGIS空間索引方法比較每一種空間索引方法都有其優(yōu)越性、使用范圍和適用對象。選取何種索引機(jī)制作為 3DOIS空間數(shù)據(jù)庫的空間索引，要根據(jù)實(shí)際情況和應(yīng)用需要來確定。目前，多數(shù)GIS軟件采 用多種索引機(jī)制并存、取長補(bǔ)短的策略。表1是在對各種類型索引研究的基礎(chǔ)上歸納出來 的索引綜合性能對照表，對實(shí)際應(yīng)用具有參考意義。表1 3D GIS空間索引方法對比索引名稱劃分區(qū)域方法適合對象優(yōu)點(diǎn)缺點(diǎn)規(guī)則網(wǎng)格面域等