基于R树空间索引的AutoCAD图形文件快速裁剪方法

史蕾

（1.中冶集团武汉勘察研究院有限公司 湖北省武汉市 430080 2.中冶智诚（武汉）工程技术有限公司 湖北省武汉市 430073）

1 引言

在实际工程应用中，AutoCAD 图形文件(dwg 和dxf 文件)被设计行业广泛使用。对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 树是当前空间数据组织管理中最流行的动态空间索引结构之一，是B 树索引在多维空间上的扩展，是一种采用对象界定技术的高度平衡树结构[5]。其构建思想是以对象的最小外包矩形MBR(Minimum Bounding Rectangle)为基本单元递归地对数据集空间进行规则划分[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 相交，不相交的不再继续处理。

（3）Rc 与R1、R2 相交，分别判断R1 和R2 中各元素是否与Rc 相交，不相交则不再继续处理。

（4）Rc 与对象c、d 相交，c、d 为最底层对象，无子元素，处理结束，返回查询结果对象c、d。

图1：R 树索引的空间划分

图2：R 树数据结构示意

图3：某钢厂dwg 格式图形数据

根据R 树索引结构进行空间查询的过程可知，利用R 树空间索引进行裁剪时，无需逐个对象进行分析，避免了大量不必要的判断，能够有效提高空间查询的效率。

3 基于R树的图形文件裁剪

由于AutoCAD 图形文件自身不存储空间索引，因此利用R 树索引辅助裁剪时需要预先建立R 树索引结构，而建立索引结构过程中需要遍历图形文件中所有对象，如果每次裁剪都遍历图形文件中所有对象的话，裁剪效率极低，R 树也无法充分发挥作用。如果要进行多次裁剪操作，只需在首次裁剪过程中遍历全部图形对象并建立R 树索引，后续裁剪则无需重复建立，直接利用已建立的R 树进行空间查询，能够有效提高裁剪效率。

对于大型图形文件，建立R 树操作也比较耗时，为了进一步提高图形裁剪效率，本文提出建立外部R 树索引文件以用于空间查询。在图形文件不改变的情况下，图形对象的R 树索引结构也是固定不变的，因此可以预先遍历整个图形文件，将建立的R 树索引结构保存为本地文件存储。在需要进行裁剪时，直接加载读取本地R 树索引文件，而无需再遍历整个图形文件，再次提升了裁剪效率。如果图形文件发生了改变，只需同步更新对应的外部索引文件即可。

本文的基于R 树空间索引的AutoCAD 图形文件快速裁剪过程如下：

（1）索引加载：判断是否为当前过程的首次裁剪，如果是则加载本地外部索引文件，读取R 树索引到计算机内存中，否则无需重复加载R 树索引。

（2）初步筛选：获取当前裁剪窗口的MBR，从R 树索引中查询MBR 与该MBR 相交的所有对象。

（3）精确筛选：遍历每个与裁剪窗口MBR 相交的对象，根据查询对象的句柄ID 获取该对象实际的几何形状，判断该几何要素与查询窗口的几何要素是否相交，如果相交则进行裁剪处理，否则从结果集合中剔除该对象。

（4）结果输出：将裁剪窗口内的裁剪结果对象输出到指定位置。

表1：裁剪性能比较

4 应用实例

为了验证本文所提出的基于R 树空间索引的AutoCAD 图形文件裁剪方法的有效性，基于AutoCAD 软件进行二次开发实现了本文的裁剪算法。其中，AutoCAD 软件版本为2018（64 位），开发平台为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]创建R 树索引结构，索引创建耗时133.28 s，虽然创建索引耗时相对较长，但只需预先创建一次，裁剪过程中无需再次创建。按二进制将该索引结构序列化到本地磁盘存储，本地索引文件大小31.94MB，序列化用时4.07 s。在裁剪操作中，本地索引文件只需要在首次裁剪时进行反序列化读取加载，反序列化耗时10.93 s。

分别选择不同大小的裁剪窗口进行裁剪实验，其中窗口大小此处选用占原图比例表示，裁剪性能结果如表1所示。

从表1可以看出，在裁剪窗口大小为0.1%时，裁图窗口很小，本文提出的基于R 树的裁剪方法的处理时间仅需0.42 s，而常规的无索引遍历裁剪方式的处理时间是142.79 s，是本文方法所需处理时间的339.98 倍，这主要是由于R 树索引结构检索时避免了大量不必要的判断，由此可见基于R 树索引的裁图方法极大地提升了处理效率。

在裁图窗口比例较小时（≤30%），本文方法均能显著地减少裁图处理时间，而在裁图窗口较大时（≥70%），由于窗口内的待裁剪对象个数比较接近全图对象个数，R 树索引查询所提升的效率有限，但仍比常规遍历法的处理性能高。当窗口大小达到100%时，二者性能相当。

在实际工程应用的裁图处理中，通常裁剪窗口都相对较小，在这种情况下采用本文的基于R 树索引结构的裁图方法能够极大地提高裁图处理的效率。

5 结语

针对实际工程应用中大型AutoCAD 图形文件裁剪效率低的问题，本文提出了基于R 树空间索引的图形文件裁剪方法。该方法在裁剪操作前预先建立外部索引文件，在裁图处理中只需要首次加载索引文件即可，通过R 树索引结构能够有效地避免不必要的空间分析判断。通过对某钢厂总图系统的dwg 图形文件进行裁剪实验可以看出，本文提出的基于R 树索引结构的裁图方法与常规的遍历裁图法相比，本文方法能够高效地进行图形对象的检索查询，提高了图形裁剪处理的工作效率。并且，除了应用于裁图过程，在进行大型图形文件的其他操作时，也可以利用R 树空间索引来提高计算性能。