基于四叉樹的空間索引.doc

《基于四叉樹的空間索引.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、基于四叉樹的空間索引四叉樹是建立在對E域循環(huán)分解原則上的一種層次數(shù)據(jù)結(jié)構(gòu)，在計算機圖形處理、圖像處理及地理信息系統(tǒng)中有著廣泛的應用，它也可以應用于對空間點的表示于索引。分為點四叉樹，區(qū)域四叉樹,CIF四叉樹等。1、點四叉樹主要針對空間點的存儲表達和索引，對于k維數(shù)據(jù)空間，點四叉樹的每個結(jié)點存儲了一個空間點得信息及2^k個孩子節(jié)點的指針，且隱式地與一索引空間相對應。以該空間點為劃分點，將其對應索引空間分為兩兩不相交的2^k個子空間，依次與它的2^k個孩子結(jié)點相對應。對于某一個子空間的點，則分配給對應的子樹。如圖1是二維空間的一棵點四叉樹的例子。其點四叉

2、樹的構(gòu)造過程如下。（1）輸入空間點A,由于四叉樹為空，因此A作為四叉樹的根節(jié)點，其隱式對應的索引空間是整個數(shù)據(jù)空間，以A為劃分原點，將對應的索引空間劃分成四個子空間，NE,NW,EW,SE依次為其孩子結(jié)點隱式對應的子空間。（2）輸入空間點B,B落入A的NW象限且A的NW孩子結(jié)點為空，因此B作為A的NW孩子結(jié)點；同樣，C作為F,C,E分別作為A的NE,SW,SE孩子結(jié)點。（3）輸入空間D,D落入A的NW象限，繼續(xù)往下查找，D落入B的NE象限且B的NE孩子結(jié)點為空，因此D作為B的NE孩子結(jié)點優(yōu)點：結(jié)構(gòu)簡單，對于精確匹配的點查找性能較高。缺點：樹的動態(tài)性差

3、，刪除結(jié)點處理復雜；樹的結(jié)構(gòu)由點的插入順序決定，難以保證樹深度的平衡；區(qū)域查找性能較差；對于非點狀空間目標，必須采用目標近似與空間映射技術(shù)，效率低；不利于樹的外部存儲設備存儲與頁面調(diào)度。2、區(qū)域四叉樹采用區(qū)域四叉樹索引多維空間的點，常用方法有MX四叉樹PR四叉樹，避免了點四叉樹動態(tài)性差，結(jié)構(gòu)完全由點得插入順序決定等缺點2.1、MX四叉樹MX四叉樹將每個空間點看成區(qū)域四叉樹中得一個黑像素，或當做一方陣中的非零元素。它與區(qū)域四叉樹的組織方式很相似，區(qū)別是葉結(jié)點為黑結(jié)點或空結(jié)點，且分別表示數(shù)據(jù)空間某一個位置空間點得存在與否。如圖2是二維空間的一棵MX四叉樹

4、的例子。優(yōu)點：所有的點都位于葉節(jié)點，樹的深度是平衡的；空間劃分是等分，劃分成的每個象限具有相同大??；可以采用線性四叉樹的存儲結(jié)構(gòu)，避免指針域的存儲，提高空間利用率。缺點：插入（刪除）一個點可能導致樹的深度增加（減少）一層或多層，所有葉結(jié)點必須重新定位；樹的深度往往很大，影響查找效率。2.2、PR四叉樹PR四叉樹葉節(jié)點或者為空，或者包含一個數(shù)據(jù)點。與MX四叉樹構(gòu)造過程類似，區(qū)別在于當分解到一個象限只包含一個點時，不需要繼續(xù)分解使該點位于某一個子象限的最左下角。特點：插入或刪除一個點不會影響其他分支，操作簡單；葉結(jié)點樹及樹的深度都小于MX四叉樹，檢索效率

5、較高。如圖3是二維空間的一棵RP四叉樹的例子。2、CIF四叉樹CIF四叉樹是針對表示大規(guī)模集成應用中的小矩形而提出的，用于索引空間矩形及其他形體。數(shù)據(jù)空間被遞歸地細分直到產(chǎn)生的子象限不再包含任何矩形。在分解過程中，與任一劃分線相交的矩形與該劃分線對應的象限相關(guān)聯(lián)，矩形只屬于完全包圍它的最小象限。如圖4是二維空間的一棵CIF四叉樹的例子。相交查詢，從根結(jié)點開始，首先檢查與其關(guān)聯(lián)的所有矩形是否為查找結(jié)點，接下來檢查象限空間與查詢區(qū)域相交的孩子結(jié)點……直到葉結(jié)點。插入一個矩形，首先檢查根結(jié)點，如果不在根結(jié)點的劃分對應的桶鏈表中，就接著檢查包含該矩形的子象限

6、所對應的孩子象限；如果該矩形依舊沒有插入到對應位置，再對該象限劃分，直到為該矩形找到對應的子象限。刪除一個矩形，首先找到該矩形所在的結(jié)點，然后從其數(shù)據(jù)桶中刪除該矩形，如果鏈表為空，且該結(jié)點沒有孩子結(jié)點，則該結(jié)點可以同時刪除。點刪除可能導致父結(jié)點也被刪除。優(yōu)點：與MX四叉樹、PR四叉樹相比，CIF四叉樹可以用于索引矩形及任何其他形體的空間目標而不需要經(jīng)過目標近似與空間目標映射，對于區(qū)域查詢，效率較高。缺點：區(qū)域查詢往往需要訪問多個結(jié)點對應的存儲桶，當索引量增大、大區(qū)域結(jié)點包含較多數(shù)據(jù)矩形，外部存儲設備I/O開銷很大。