伍百發(fā)，何 潔

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

一、引 言

由于歷史和現(xiàn)實的因素，當(dāng)前許多GIS矢量數(shù)據(jù)的前端采集和加工仍是在CAD環(huán)境下進(jìn)行，但CAD軟件通常對于空間數(shù)據(jù)的表示不能有效地建立空間索引機(jī)制，從而導(dǎo)致數(shù)據(jù)的空間拓?fù)潢P(guān)系無法在數(shù)據(jù)結(jié)構(gòu)層次中得到描述，這對地理數(shù)據(jù)的拓?fù)錂z查和處理帶來了極大困難，主要反應(yīng)在算法效率上?；诖耍P者通過引入格網(wǎng)空間索引配合四叉樹，針對CAD數(shù)據(jù)建立空間索引，配合相應(yīng)的算法得以解決此類問題。

二、格網(wǎng)索引及四叉樹結(jié)構(gòu)分析與優(yōu)化

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

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

圖1

1.格網(wǎng)索引的數(shù)學(xué)原理

設(shè)數(shù)據(jù)集合為X，其算法的時間函數(shù)為T(C(X)n)，其中，n＞1;C(X)為X的規(guī)模函數(shù)。若集合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，其規(guī)模函數(shù)C(X0)=I，In=I則 C(X1)n+C(X2)n+ … +C(Xm)n=mC(X0)n=mIn=mI，則時間函數(shù)為T(mI)。

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

2.數(shù)據(jù)劃分的空間代價

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

為了解決這對矛盾，一方面需要在二者之間找到好的平衡點，根據(jù)經(jīng)驗值可取空間對象內(nèi)所有對象平均外包矩形的3倍作為格網(wǎng)大小［2］。另一方面通過優(yōu)化數(shù)據(jù)結(jié)構(gòu)，建立數(shù)據(jù)索引分級儲存、訪問機(jī)制及壓縮算法來提高數(shù)據(jù)的存儲效率。

3.引入四叉樹結(jié)構(gòu)優(yōu)化空間存儲

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

圖2

對于四叉樹結(jié)構(gòu)，可將其視為行列數(shù)量相等，且冪為2的格網(wǎng)。在實現(xiàn)過程中很容易建立格網(wǎng)編號與四叉樹節(jié)點之間的關(guān)系。使用該型空間索引可快速查詢指定空間內(nèi)的對象，也可快速查詢對象所在空間，以此展開的應(yīng)用算法都將具有良好的時間性能。

三、軟件結(jié)構(gòu)和設(shè)計

基于前面的分析，格網(wǎng)索引在時間效率方面的優(yōu)勢，可以彌補(bǔ)CAD數(shù)據(jù)生產(chǎn)平臺空間索引能力的欠缺。由于格網(wǎng)索引與空間對象是一種映射關(guān)系，由此可以采用CAD軟件提供的二次開發(fā)語言構(gòu)建空間索引作為原數(shù)據(jù)結(jié)構(gòu)的一種補(bǔ)充。一旦索引構(gòu)建好，便可圍繞其擴(kuò)充多種空間查詢、搜索、分析及拓?fù)涮幚砉δ?。以此作為依?jù)，筆者在《1∶10 000萬DLG入庫軟件》中進(jìn)行了成功的嘗試，驗證了上述方法的可行性。

1.軟件基本結(jié)構(gòu)模式

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

圖3

2.主要設(shè)計

接口層主要負(fù)責(zé)將CAD平臺數(shù)據(jù)提取轉(zhuǎn)換為空間運(yùn)算層需要的數(shù)據(jù)結(jié)構(gòu)，并向該層發(fā)送控制信號建立空間索引或各種運(yùn)算指令。當(dāng)運(yùn)算層計算完成后會將結(jié)果轉(zhuǎn)給接口層，接口層再將結(jié)果轉(zhuǎn)換為CAD平臺可以識別的數(shù)據(jù)。接口層采用各類CAD平臺的二次開發(fā)語言進(jìn)行，本次目標(biāo)平臺為AutoCAD，采用AutoCAD內(nèi)置的VBA提供人機(jī)接口，負(fù)責(zé)向空間運(yùn)算層發(fā)送控制命令，并由Object-ARX開發(fā)數(shù)據(jù)流接口，負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)換和信號協(xié)調(diào)(將來或可以實現(xiàn)多進(jìn)/線程并行能力)［5］。

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

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

(1)基本數(shù)據(jù)結(jié)構(gòu)

如表1所示。

表1

續(xù)表1

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

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

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

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

1)平面格網(wǎng)→四叉樹

2)四叉樹→層級格網(wǎng)

四、數(shù)據(jù)測試及分析

現(xiàn)將主要幾種常見操作的傳統(tǒng)算法編寫的程序和采用基于格網(wǎng)索引的算法編寫的程序進(jìn)行比較，如表2～表3所示。

表2 傳統(tǒng)未添加空間索引算法(AutoCAD 2004環(huán)境)

表3 采用基于格網(wǎng)、四叉樹索引算法(AutoCAD 2004環(huán)境)

由表2～表3可知，基于格網(wǎng)、四叉樹索引算法在時間效率方面有著極大的優(yōu)勢，而且用于建立索引的時間開支也很少。當(dāng)數(shù)據(jù)規(guī)模不斷增大時更是如此，基于格網(wǎng)索引算法的線段求交的時間效率曲線如圖4所示。

由圖4可看出，此算法的時間效率曲線基本為線性，說明算法的時間復(fù)雜度為O(n)。此算法的實現(xiàn)驗證了本文前段關(guān)于格網(wǎng)索引算法的分析。

圖4

五、結(jié)束語

格網(wǎng)索引作為一種成熟的技術(shù)已經(jīng)用于許多GIS平臺，但其在基于CAD的入庫軟件中應(yīng)用還不多。筆者通過將此技術(shù)引入CAD軟件，將其改造成為具備一定空間索引和計算能力的軟件，不但發(fā)揮了CAD軟件的強(qiáng)大編輯能力，同時兼顧高效，其生產(chǎn)的數(shù)據(jù)也將更符合GIS平臺的需求，并能產(chǎn)生良好的經(jīng)濟(jì)效益和社會效益。

［1］孟妮娜，周校東.固定格網(wǎng)劃分的空間索引的實現(xiàn)技術(shù)［J］.北京測繪，2003(1)：7-11.

［2］吳信才.地理信息系統(tǒng)原理［M］.2版.北京：電子工業(yè)出版社，2009.

［3］李志猛，高有行.四叉樹在Virtual GIS系統(tǒng)中的應(yīng)用［J］.太原理工大學(xué)學(xué)報，2003，34(1)：90-92.

［4］王曉慶.曾文英.王明文.丁暉.設(shè)計模式中的面向?qū)ο笤瓌t及其子模式［J］.計算機(jī)工程，2003，29(9)：192-194.

［5］李長勛.AutoCAD ObjectARX程序開發(fā)技術(shù)［M］.北京：國防工業(yè)出版社，2005.

［6］張戈.CAD系統(tǒng)開發(fā)軟件工程管理方法探索［J］.微型電腦應(yīng)用，2000(6)：26-27.

［7］殷超.算用算法時間復(fù)雜度的計算方法［J］.科技信息，2011(29)：87.

［8］謝露蓉.地圖圖形數(shù)據(jù)拓?fù)潢P(guān)系的建立［J］.測繪科技動態(tài)，1999(2)：25-29.

［9］邵曉艷.劉寧 基于GIS海量數(shù)據(jù)的網(wǎng)格空間索引技術(shù)［J］.科技風(fēng)，2009(22)：266-268.

［10］王欣.程耀東.孟凡相.ObjectARX二次開發(fā)運(yùn)行機(jī)制及應(yīng)用研究［J］.測繪科學(xué)，2009(S2)：184-187.

［11］KROENKE D M.數(shù)據(jù)庫原理［M］.馮飛，譯.北京：清華大學(xué)出版社，2009.