格網索引及四叉樹在CAD建庫軟件中的應用

2012-12-11 07:27:34伍百發

測繪通報 2012年1期

伍百發，何潔

(湖南省第一測繪院，湖南衡陽421001)

一、引言

由于歷史和現實的因素，當前許多GIS矢量數據的前端采集和加工仍是在CAD環境下進行，但CAD軟件通常對于空間數據的表示不能有效地建立空間索引機制，從而導致數據的空間拓撲關系無法在數據結構層次中得到描述，這對地理數據的拓撲檢查和處理帶來了極大困難，主要反應在算法效率上。基于此，筆者通過引入格網空間索引配合四叉樹，針對CAD數據建立空間索引，配合相應的算法得以解決此類問題。

二、格網索引及四叉樹結構分析與優化

為了快速檢索大量矢量數據，可將空間劃分成一定間距的網格［1］，建立起矢量數據與網格之間的相對關系，并以網格作為數據空間關系的承載體。這樣便可快速檢索特定區域內的矢量數據，反之亦可快速計算特定空間要素所處的區域及確定該區域內矢量數據之間的關系。

如圖1所示，將數據的空間位置映射到空間網格中，建立空間索引。若想在海量數據中獲得所示對象的交點等操作，只需要在有陰影內的網格內查找即可，而無須關注其他區域內的數據和對象，從而使得數據集的規模大幅減少。

圖1

1.格網索引的數學原理

設數據集合為X，其算法的時間函數為T(C(X)n)，其中，n＞1;C(X)為X的規模函數。若集合X可分解成m個互不相交子集，即X=X1∪X2∪… ∪Xm，Xi∩Xj=φ {i，j∈(1，2，…，m)，i≠j}，則C(X)n＞ C(X1)n+C(X2)+… +C(Xm)n，其中，n＞1。

若 Xi，i∈(1，…，m)均為原子集 Xo，其規模函數C(X0)=I，In=I則 C(X1)n+C(X2)n+ … +C(Xm)n=mC(X0)n=mIn=mI，則時間函數為T(mI)。

在上述情況下，通過數據細分可將數據集X的時間函數降低為線性級。若將空間對象劃分成每個格網中一個原子集，其規模函數值為1，1n=1，則時間的復雜度為O(m)，m為格網的數量。

2.數據劃分的空間代價

假設空間數據集X在空間上均勻分布，數據集的規模為C，空間的劃分粒度為L，子集的數量為m，則有C=L×m。假設將空間數據集按照一定規則進行劃分成若干空間子集，可通過增加m來減小時間復雜度，但對于線和面類型夭量數據必然由于粒度過細導致大量存儲冗余，導致性能下降。

為了解決這對矛盾，一方面需要在二者之間找到好的平衡點，根據經驗值可取空間對象內所有對象平均外包矩形的3倍作為格網大?。?］。另一方面通過優化數據結構，建立數據索引分級儲存、訪問機制及壓縮算法來提高數據的存儲效率。

3.引入四叉樹結構優化空間存儲

可通過規則的空間劃分按照不同粒度分級建立格網，如采用四叉樹形，如圖2所示，將空間區域劃分為4個象限［3］，然后各區域再按相同規則進行劃分，直到達到滿足要求的粒度為止，這樣既可解決空間對象分布不均的問題也可節約存儲空間。在最細粒度(四叉樹的葉子)上以鏈表形式記錄下相關空間對象的索引號(句柄)。同時，為每一個空間對象添加一個索引集，記錄與之相關的格網索引集，該索引集以數組或鏈表形式存儲。

圖2

對于四叉樹結構，可將其視為行列數量相等，且冪為2的格網。在實現過程中很容易建立格網編號與四叉樹節點之間的關系。使用該型空間索引可快速查詢指定空間內的對象，也可快速查詢對象所在空間，以此展開的應用算法都將具有良好的時間性能。

三、軟件結構和設計

基于前面的分析，格網索引在時間效率方面的優勢，可以彌補CAD數據生產平臺空間索引能力的欠缺。由于格網索引與空間對象是一種映射關系，由此可以采用CAD軟件提供的二次開發語言構建空間索引作為原數據結構的一種補充。一旦索引構建好，便可圍繞其擴充多種空間查詢、搜索、分析及拓撲處理功能。以此作為依據，筆者在《1∶10 000萬DLG入庫軟件》中進行了成功的嘗試，驗證了上述方法的可行性。

1.軟件基本結構模式

軟件采用適配器模式進行設計，在CAD與空間運算模塊之間設立一個接口層作為適配器以便應用于不同CAD平臺［4］。如圖3所示。

圖3

2.主要設計

接口層主要負責將CAD平臺數據提取轉換為空間運算層需要的數據結構，并向該層發送控制信號建立空間索引或各種運算指令。當運算層計算完成后會將結果轉給接口層，接口層再將結果轉換為CAD平臺可以識別的數據。接口層采用各類CAD平臺的二次開發語言進行，本次目標平臺為AutoCAD，采用AutoCAD內置的VBA提供人機接口，負責向空間運算層發送控制命令，并由Object-ARX開發數據流接口，負責數據轉換和信號協調(將來或可以實現多進/線程并行能力)［5］。

空間運算層是軟件的底層和核心，是軟件運行的關鍵。其中，空間索引更是軟件的基石，各類運算都依賴于空間索引的方式。出于效率考慮，二者之間的實現上采用緊耦合方式設計。在功能上，空間索引模塊負責數據的空間索引建立，并向運算庫提供其必須的運算數據;擴展運算庫為基于空間索引的各類空間運算，直接由接口模塊調用與數據交互。

基本運算庫由各類不依賴于空間索引的空間運算函數和對象組成，為擴展運算庫提供原子運算功能。

(1)基本數據結構

如表1所示。

表1

續表1

為了發揮格網的Hash快速檢索能力和四叉樹能夠節約存儲空間的能力，格網行列數量都被劃分為2的冪，行列數相等，以使得格網和四叉樹數量上可以“對齊”。

(2)數據索引建立與存取

將空間數據通過接口模塊轉換為內部數據結構后可以求得其在格網中的編號，然后可通過格網上的平面編號快速地求出其在四叉樹上的位置，并將該對象的ID添加至四叉樹的對象鏈表中，以此來迅速生成具有合適深度的四叉樹。最后遍歷四叉樹將葉子樹較少的節點往上級合并，葉子較多的節點可進一步分解深化，以優化四叉樹。同時建立“對象－葉子映射”Hash表，以加快對象索引。

由于采用緊耦合設計，空間運算與索引在同一地址空間，可直接遍歷建立的四叉樹，配合“對象－葉子映射”表進行單元的各類運算，并將運算結果與四叉樹的編號或格網層級編號合成，然后匯總傳給接口模塊，經處理后反饋到CAD軟件［6］。以下為幾種索引的映射算法。

1)平面格網→四叉樹