基于R樹空間索引的AutoCAD圖形文件快速裁剪方法

史蕾

（1.中冶集團(tuán)武漢勘察研究院有限公司 湖北省武漢市 430080 2.中冶智誠（武漢）工程技術(shù)有限公司 湖北省武漢市 430073）

1 引言

在實(shí)際工程應(yīng)用中，AutoCAD 圖形文件(dwg 和dxf 文件)被設(shè)計(jì)行業(yè)廣泛使用。對(duì)AutoCAD 圖形文件的裁剪處理是一種常見的操作，通常利用相關(guān)的CAD (Computer Aided Design，計(jì)算機(jī)輔助設(shè)計(jì))軟件便可實(shí)現(xiàn)。然而對(duì)于圖形數(shù)量達(dá)百萬級(jí)的大型圖形文件，以及需要在裁剪過程中進(jìn)行其他處理（例如編輯修改、坐標(biāo)變換等）時(shí)，CAD 軟件的效率和功能無法滿足實(shí)際生產(chǎn)應(yīng)用需求。因此，針對(duì)大型圖形文件的裁剪處理問題，本文提出了基于R 樹空間索引的裁剪方法，能夠高效地進(jìn)行大型圖形文件的裁剪處理。

2 R樹空間索引

AutoCAD 圖形文件的對(duì)象存儲(chǔ)于塊表(BlockTable)中，對(duì)象由句柄ID(HandleID)進(jìn)行唯一標(biāo)識(shí)，因此從AutoCAD 圖形文件中獲取指定的對(duì)象需要根據(jù)句柄ID 進(jìn)行檢索。由于AutoCAD 圖形文件不存儲(chǔ)空間索引信息，因此從中獲取指定范圍內(nèi)的對(duì)象需要遍歷圖形文件內(nèi)的所有對(duì)象并進(jìn)行逐一判斷篩選。這種操作方式在處理對(duì)象個(gè)數(shù)不多時(shí)對(duì)實(shí)際應(yīng)用影響不大，但當(dāng)圖形對(duì)象個(gè)數(shù)達(dá)到幾十萬甚至百萬級(jí)以上時(shí)，遍歷篩選法則完全無法滿足實(shí)際工作需求。

在空間數(shù)據(jù)的組織管理中，為了提高空間對(duì)象的查詢效率，通常會(huì)建立各種空間索引結(jié)構(gòu)，例如網(wǎng)格索引[1]、KD 樹索引[2;3]、四叉樹/八叉樹索引[2;3]、B 樹[2;3]、R 樹[4;5]及其各種變種樹。空間索引作為一種輔助性的數(shù)據(jù)結(jié)構(gòu)，用于篩選和剔除與指定的空間操作無關(guān)的空間對(duì)象，是對(duì)空間對(duì)象進(jìn)行高效檢索的有效方法。

R 樹是當(dāng)前空間數(shù)據(jù)組織管理中最流行的動(dòng)態(tài)空間索引結(jié)構(gòu)之一，是B 樹索引在多維空間上的擴(kuò)展，是一種采用對(duì)象界定技術(shù)的高度平衡樹結(jié)構(gòu)[5]。其構(gòu)建思想是以對(duì)象的最小外包矩形MBR(Minimum Bounding Rectangle)為基本單元遞歸地對(duì)數(shù)據(jù)集空間進(jìn)行規(guī)則劃分[3]，如圖1所示。

在圖1中a～i 為空間對(duì)象的MBR，R1-R3 為包含這些對(duì)象矩形的高層次的矩形范圍，R0 則是包含R1～R3 這些矩形的更高層次的矩形，其數(shù)據(jù)結(jié)構(gòu)如圖2所示。

在對(duì)AutoCAD 圖形文件進(jìn)行裁剪處理時(shí)，裁剪窗口可能是矩形、多邊形、圓形等不同幾何形狀，但從R 樹結(jié)構(gòu)中檢索與裁剪窗口相交的對(duì)象時(shí)，是以裁剪窗口的MBR 進(jìn)行查詢從而實(shí)現(xiàn)初步篩選。在圖1中Rc 為裁剪窗口的MBR，查詢與Rc 相交的對(duì)象過程如下：

（1）判斷Rc 是否與R0 相交，如果不相交則退出。

（2）Rc 與R0 相交，判斷R0 中各元素的MBR 是否與Rc 相交，不相交的不再繼續(xù)處理。

（3）Rc 與R1、R2 相交，分別判斷R1 和R2 中各元素是否與Rc 相交，不相交則不再繼續(xù)處理。

（4）Rc 與對(duì)象c、d 相交，c、d 為最底層對(duì)象，無子元素，處理結(jié)束，返回查詢結(jié)果對(duì)象c、d。

圖1：R 樹索引的空間劃分

圖2：R 樹數(shù)據(jù)結(jié)構(gòu)示意

圖3：某鋼廠dwg 格式圖形數(shù)據(jù)

根據(jù)R 樹索引結(jié)構(gòu)進(jìn)行空間查詢的過程可知，利用R 樹空間索引進(jìn)行裁剪時(shí)，無需逐個(gè)對(duì)象進(jìn)行分析，避免了大量不必要的判斷，能夠有效提高空間查詢的效率。

3 基于R樹的圖形文件裁剪

由于AutoCAD 圖形文件自身不存儲(chǔ)空間索引，因此利用R 樹索引輔助裁剪時(shí)需要預(yù)先建立R 樹索引結(jié)構(gòu)，而建立索引結(jié)構(gòu)過程中需要遍歷圖形文件中所有對(duì)象，如果每次裁剪都遍歷圖形文件中所有對(duì)象的話，裁剪效率極低，R 樹也無法充分發(fā)揮作用。如果要進(jìn)行多次裁剪操作，只需在首次裁剪過程中遍歷全部圖形對(duì)象并建立R 樹索引，后續(xù)裁剪則無需重復(fù)建立，直接利用已建立的R 樹進(jìn)行空間查詢，能夠有效提高裁剪效率。

對(duì)于大型圖形文件，建立R 樹操作也比較耗時(shí)，為了進(jìn)一步提高圖形裁剪效率，本文提出建立外部R 樹索引文件以用于空間查詢。在圖形文件不改變的情況下，圖形對(duì)象的R 樹索引結(jié)構(gòu)也是固定不變的，因此可以預(yù)先遍歷整個(gè)圖形文件，將建立的R 樹索引結(jié)構(gòu)保存為本地文件存儲(chǔ)。在需要進(jìn)行裁剪時(shí)，直接加載讀取本地R 樹索引文件，而無需再遍歷整個(gè)圖形文件，再次提升了裁剪效率。如果圖形文件發(fā)生了改變，只需同步更新對(duì)應(yīng)的外部索引文件即可。

本文的基于R 樹空間索引的AutoCAD 圖形文件快速裁剪過程如下：

（1）索引加載：判斷是否為當(dāng)前過程的首次裁剪，如果是則加載本地外部索引文件，讀取R 樹索引到計(jì)算機(jī)內(nèi)存中，否則無需重復(fù)加載R 樹索引。

（2）初步篩選：獲取當(dāng)前裁剪窗口的MBR，從R 樹索引中查詢MBR 與該MBR 相交的所有對(duì)象。

（3）精確篩選：遍歷每個(gè)與裁剪窗口MBR 相交的對(duì)象，根據(jù)查詢對(duì)象的句柄ID 獲取該對(duì)象實(shí)際的幾何形狀，判斷該幾何要素與查詢窗口的幾何要素是否相交，如果相交則進(jìn)行裁剪處理，否則從結(jié)果集合中剔除該對(duì)象。

（4）結(jié)果輸出：將裁剪窗口內(nèi)的裁剪結(jié)果對(duì)象輸出到指定位置。

表1：裁剪性能比較

4 應(yīng)用實(shí)例

為了驗(yàn)證本文所提出的基于R 樹空間索引的AutoCAD 圖形文件裁剪方法的有效性，基于AutoCAD 軟件進(jìn)行二次開發(fā)實(shí)現(xiàn)了本文的裁剪算法。其中，AutoCAD 軟件版本為2018（64 位），開發(fā)平臺(tái)為Visual Studio 2015，編程語言為C#。實(shí)驗(yàn)計(jì)算機(jī)的配置為4核Intel Core i7 3.4 GHz CPU（算法操作為單線程，僅單核CPU 被使用），8 GB 內(nèi)存，Windows 10 (64 位)操作系統(tǒng)。本文的處理效率實(shí)驗(yàn)中，運(yùn)行時(shí)間均為運(yùn)行5 次的平均時(shí)間。

實(shí)驗(yàn)測試數(shù)據(jù)為某鋼廠總圖系統(tǒng)的勘測結(jié)果dwg 格式數(shù)據(jù)，如圖3所示，包含建筑、道路、電力線、燃?xì)夤芫€、給排水管線等多種類型對(duì)象，文件大小178.41 MB，對(duì)象個(gè)數(shù)140.13 萬個(gè)。遍歷鋼廠dwg 圖形的所有對(duì)象，獲取每個(gè)對(duì)象的MBR，根據(jù)R 樹構(gòu)建算法[4;5]創(chuàng)建R 樹索引結(jié)構(gòu)，索引創(chuàng)建耗時(shí)133.28 s，雖然創(chuàng)建索引耗時(shí)相對(duì)較長，但只需預(yù)先創(chuàng)建一次，裁剪過程中無需再次創(chuàng)建。按二進(jìn)制將該索引結(jié)構(gòu)序列化到本地磁盤存儲(chǔ)，本地索引文件大小31.94MB，序列化用時(shí)4.07 s。在裁剪操作中，本地索引文件只需要在首次裁剪時(shí)進(jìn)行反序列化讀取加載，反序列化耗時(shí)10.93 s。

分別選擇不同大小的裁剪窗口進(jìn)行裁剪實(shí)驗(yàn)，其中窗口大小此處選用占原圖比例表示，裁剪性能結(jié)果如表1所示。

從表1可以看出，在裁剪窗口大小為0.1%時(shí)，裁圖窗口很小，本文提出的基于R 樹的裁剪方法的處理時(shí)間僅需0.42 s，而常規(guī)的無索引遍歷裁剪方式的處理時(shí)間是142.79 s，是本文方法所需處理時(shí)間的339.98 倍，這主要是由于R 樹索引結(jié)構(gòu)檢索時(shí)避免了大量不必要的判斷，由此可見基于R 樹索引的裁圖方法極大地提升了處理效率。

在裁圖窗口比例較小時(shí)（≤30%），本文方法均能顯著地減少裁圖處理時(shí)間，而在裁圖窗口較大時(shí)（≥70%），由于窗口內(nèi)的待裁剪對(duì)象個(gè)數(shù)比較接近全圖對(duì)象個(gè)數(shù)，R 樹索引查詢所提升的效率有限，但仍比常規(guī)遍歷法的處理性能高。當(dāng)窗口大小達(dá)到100%時(shí)，二者性能相當(dāng)。

在實(shí)際工程應(yīng)用的裁圖處理中，通常裁剪窗口都相對(duì)較小，在這種情況下采用本文的基于R 樹索引結(jié)構(gòu)的裁圖方法能夠極大地提高裁圖處理的效率。

5 結(jié)語

針對(duì)實(shí)際工程應(yīng)用中大型AutoCAD 圖形文件裁剪效率低的問題，本文提出了基于R 樹空間索引的圖形文件裁剪方法。該方法在裁剪操作前預(yù)先建立外部索引文件，在裁圖處理中只需要首次加載索引文件即可，通過R 樹索引結(jié)構(gòu)能夠有效地避免不必要的空間分析判斷。通過對(duì)某鋼廠總圖系統(tǒng)的dwg 圖形文件進(jìn)行裁剪實(shí)驗(yàn)可以看出，本文提出的基于R 樹索引結(jié)構(gòu)的裁圖方法與常規(guī)的遍歷裁圖法相比，本文方法能夠高效地進(jìn)行圖形對(duì)象的檢索查詢，提高了圖形裁剪處理的工作效率。并且，除了應(yīng)用于裁圖過程，在進(jìn)行大型圖形文件的其他操作時(shí)，也可以利用R 樹空間索引來提高計(jì)算性能。