CIF四叉樹

CIF(Caltech Intermediate Form)四叉樹。CIF 四叉樹是針對表示 VLSI (Very LargeScale Integration)套用中的小矩形而提出的,它可以用於索引空間矩形及其它形體。採用 CIF 四叉樹索引結構時,資料空間被遞歸地細分直至產生的子象限不再包含任何矩形。在分解的過程中,所有與任一划分線相交的矩形與該劃分線對應的象限相關聯,屬於一個象限的矩形不能屬於任何祖先象限,也就是說,矩形只屬於完全包圍它的最小象限。下圖 是一顆傳統四叉樹和 CIF 四叉樹的例子。
在CIF四叉樹中待分區域被遞歸的分成最小區域不再包含任何空間對象,而且空間對象只屬於完全包含它的一個最小區域,沒有數據的冗餘現象。在具體的算法實現過程中當空間對象與任何一個切割線相交,這個空間對象就屬於包含這條切割線的區域,空間對象被存儲在區域對應的四叉樹結點中。這點也是CIF四叉樹和傳統的
CIF四叉樹
CIF四叉樹
四叉樹最明顯的一個區別,CIF四叉樹解決了傳統四叉樹結構索引空間複雜形體數據冗餘的不足。圖4-6是CIF四叉樹的結構示意圖。
CIF四叉樹插入一個空間對象時從根結點開始搜尋,若空間對象與根結點對應的切割線相交就直接把空間對象存儲在根結點上,如果不相交就檢查完全包含空間對象的子區域,直到空間對象與某一切割線相交,如此遞歸循環下去。若搜尋到了葉子結點也沒有任何一切割與空間對象相交,就把葉子結點對應的子區域重新切割,重新遞歸上述過程直到空間對象與某一條切割線相交。
CIF刪除一個空間對象,需要查詢存儲待刪除空間對象的結點,直接從該結點中刪除空間對象的信息。如果刪除空間對象後導致該結點為空,需要一起刪除該結點。在刪除子結點的操作完成後,如果它的父結點同樣不再存儲任何空間對象則需要刪除該父結點。上述過程可以看成插入對象的逆過程。在CIF四叉樹上進行空間相交查詢同樣從根結點開始搜尋,查詢存儲在根結點所有空間對象,看是否滿足要求。然後再搜尋與查詢區域相交的子結點空間,如此循環下去,遇到葉子節點時搜尋停止。
相比其他幾種四叉樹,CIF四叉樹可以索引空間折線,空間面等複雜的空間形體,不需要進行近似技術。因此CIF四叉樹在區域查詢的效率比其他的四叉樹索引都要高。但是當CIF四叉樹面對海量的空間數據時,空間索引量非常大使得CIF四叉樹空間索引的外存I/O開銷很高。
詳細介紹請參考
《基於改進四叉樹空間索引的最佳化研究與套用》
《基於四叉樹的線狀實體拓撲規則檢查演算法》

相關詞條

熱門詞條

聯絡我們