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

史蕾

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

1 引言

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

2 R樹空間索引

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

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

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

在圖1中a～i 為空間對象的MBR，R1-R3 為包含這些對象矩形的高層次的矩形范圍，R0 則是包含R1～R3 這些矩形的更高層次的矩形，其數據結構如圖2所示。

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

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

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

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

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

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

圖2：R 樹數據結構示意

圖3：某鋼廠dwg 格式圖形數據

根據R 樹索引結構進行空間查詢的過程可知，利用R 樹空間索引進行裁剪時，無需逐個對象進行分析，避免了大量不必要的判斷，能夠有效提高空間查詢的效率。

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

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

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

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

（1）索引加載：判斷是否為當前過程的首次裁剪，如果是則加載本地外部索引文件，讀取R 樹索引到計算機內存中，否則無需重復加載R 樹索引。

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

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

（4）結果輸出：將裁剪窗口內的裁剪結果對象輸出到指定位置。

表1：裁剪性能比較

4 應用實例

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

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

分別選擇不同大小的裁剪窗口進行裁剪實驗，其中窗口大小此處選用占原圖比例表示，裁剪性能結果如表1所示。

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

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

在實際工程應用的裁圖處理中，通常裁剪窗口都相對較小，在這種情況下采用本文的基于R 樹索引結構的裁圖方法能夠極大地提高裁圖處理的效率。

5 結語

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