格網(wǎng)索引及四叉樹(shù)在CAD建庫(kù)軟件中的應(yīng)用

伍百發(fā)，何 潔

(湖南省第一測(cè)繪院，湖南衡陽(yáng)421001)

一、引 言

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

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

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

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

圖1

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

設(shè)數(shù)據(jù)集合為X，其算法的時(shí)間函數(shù)為T(mén)(C(X)n)，其中，n＞1;C(X)為X的規(guī)模函數(shù)。若集合X可分解成m個(gè)互不相交子集，即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í)間函數(shù)為T(mén)(mI)。

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

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

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

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

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

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

圖2

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

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

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

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

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

圖3

2.主要設(shè)計(jì)

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

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

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

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

如表1所示。

表1

續(xù)表1

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

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

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

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

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

2)四叉樹(shù)→層級(jí)格網(wǎng)

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

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

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

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

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

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

圖4

五、結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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