格网索引及四叉树在CAD建库软件中的应用

伍百发，何 洁

(湖南省第一测绘院，湖南衡阳421001)

一、引 言

由于历史和现实的因素，当前许多GIS矢量数据的前端采集和加工仍是在CAD环境下进行，但CAD软件通常对于空间数据的表示不能有效地建立空间索引机制，从而导致数据的空间拓扑关系无法在数据结构层次中得到描述，这对地理数据的拓扑检查和处理带来了极大困难，主要反应在算法效率上。基于此，笔者通过引入格网空间索引配合四叉树，针对CAD数据建立空间索引，配合相应的算法得以解决此类问题。

二、格网索引及四叉树结构分析与优化

为了快速检索大量矢量数据，可将空间划分成一定间距的网格［1］，建立起矢量数据与网格之间的相对关系，并以网格作为数据空间关系的承载体。这样便可快速检索特定区域内的矢量数据，反之亦可快速计算特定空间要素所处的区域及确定该区域内矢量数据之间的关系。

如图1所示，将数据的空间位置映射到空间网格中，建立空间索引。若想在海量数据中获得所示对象的交点等操作，只需要在有阴影内的网格内查找即可，而无须关注其他区域内的数据和对象，从而使得数据集的规模大幅减少。

图1

1.格网索引的数学原理

设数据集合为X，其算法的时间函数为T(C(X)n)，其中，n＞1;C(X)为X的规模函数。若集合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，其规模函数C(X0)=I，In=I则 C(X1)n+C(X2)n+ … +C(Xm)n=mC(X0)n=mIn=mI，则时间函数为T(mI)。

在上述情况下，通过数据细分可将数据集X的时间函数降低为线性级。若将空间对象划分成每个格网中一个原子集，其规模函数值为1，1n=1，则时间的复杂度为O(m)，m为格网的数量。

2.数据划分的空间代价

假设空间数据集X在空间上均匀分布，数据集的规模为C，空间的划分粒度为L，子集的数量为m，则有C=L×m。假设将空间数据集按照一定规则进行划分成若干空间子集，可通过增加m来减小时间复杂度，但对于线和面类型夭量数据必然由于粒度过细导致大量存储冗余，导致性能下降。

为了解决这对矛盾，一方面需要在二者之间找到好的平衡点，根据经验值可取空间对象内所有对象平均外包矩形的3倍作为格网大小［2］。另一方面通过优化数据结构，建立数据索引分级储存、访问机制及压缩算法来提高数据的存储效率。

3.引入四叉树结构优化空间存储

可通过规则的空间划分按照不同粒度分级建立格网，如采用四叉树形，如图2所示，将空间区域划分为4个象限［3］，然后各区域再按相同规则进行划分，直到达到满足要求的粒度为止，这样既可解决空间对象分布不均的问题也可节约存储空间。在最细粒度(四叉树的叶子)上以链表形式记录下相关空间对象的索引号(句柄)。同时，为每一个空间对象添加一个索引集，记录与之相关的格网索引集，该索引集以数组或链表形式存储。

图2

对于四叉树结构，可将其视为行列数量相等，且幂为2的格网。在实现过程中很容易建立格网编号与四叉树节点之间的关系。使用该型空间索引可快速查询指定空间内的对象，也可快速查询对象所在空间，以此展开的应用算法都将具有良好的时间性能。

三、软件结构和设计

基于前面的分析，格网索引在时间效率方面的优势，可以弥补CAD数据生产平台空间索引能力的欠缺。由于格网索引与空间对象是一种映射关系，由此可以采用CAD软件提供的二次开发语言构建空间索引作为原数据结构的一种补充。一旦索引构建好，便可围绕其扩充多种空间查询、搜索、分析及拓扑处理功能。以此作为依据，笔者在《1∶10 000万DLG入库软件》中进行了成功的尝试，验证了上述方法的可行性。

1.软件基本结构模式

软件采用适配器模式进行设计，在CAD与空间运算模块之间设立一个接口层作为适配器以便应用于不同CAD平台［4］。如图3所示。

图3

2.主要设计

接口层主要负责将CAD平台数据提取转换为空间运算层需要的数据结构，并向该层发送控制信号建立空间索引或各种运算指令。当运算层计算完成后会将结果转给接口层，接口层再将结果转换为CAD平台可以识别的数据。接口层采用各类CAD平台的二次开发语言进行，本次目标平台为AutoCAD，采用AutoCAD内置的VBA提供人机接口，负责向空间运算层发送控制命令，并由Object-ARX开发数据流接口，负责数据转换和信号协调(将来或可以实现多进/线程并行能力)［5］。

空间运算层是软件的底层和核心，是软件运行的关键。其中，空间索引更是软件的基石，各类运算都依赖于空间索引的方式。出于效率考虑，二者之间的实现上采用紧耦合方式设计。在功能上，空间索引模块负责数据的空间索引建立，并向运算库提供其必须的运算数据;扩展运算库为基于空间索引的各类空间运算，直接由接口模块调用与数据交互。

基本运算库由各类不依赖于空间索引的空间运算函数和对象组成，为扩展运算库提供原子运算功能。

(1)基本数据结构

如表1所示。

表1

续表1

为了发挥格网的Hash快速检索能力和四叉树能够节约存储空间的能力，格网行列数量都被划分为2的幂，行列数相等，以使得格网和四叉树数量上可以“对齐”。

(2)数据索引建立与存取

将空间数据通过接口模块转换为内部数据结构后可以求得其在格网中的编号，然后可通过格网上的平面编号快速地求出其在四叉树上的位置，并将该对象的ID添加至四叉树的对象链表中，以此来迅速生成具有合适深度的四叉树。最后遍历四叉树将叶子树较少的节点往上级合并，叶子较多的节点可进一步分解深化，以优化四叉树。同时建立“对象－叶子映射”Hash表，以加快对象索引。

由于采用紧耦合设计，空间运算与索引在同一地址空间，可直接遍历建立的四叉树，配合“对象－叶子映射”表进行单元的各类运算，并将运算结果与四叉树的编号或格网层级编号合成，然后汇总传给接口模块，经处理后反馈到CAD软件［6］。以下为几种索引的映射算法。

1)平面格网→四叉树

2)四叉树→层级格网

四、数据测试及分析

现将主要几种常见操作的传统算法编写的程序和采用基于格网索引的算法编写的程序进行比较，如表2～表3所示。

表2 传统未添加空间索引算法(AutoCAD 2004环境)

表3 采用基于格网、四叉树索引算法(AutoCAD 2004环境)

由表2～表3可知，基于格网、四叉树索引算法在时间效率方面有着极大的优势，而且用于建立索引的时间开支也很少。当数据规模不断增大时更是如此，基于格网索引算法的线段求交的时间效率曲线如图4所示。

由图4可看出，此算法的时间效率曲线基本为线性，说明算法的时间复杂度为O(n)。此算法的实现验证了本文前段关于格网索引算法的分析。

图4

五、结束语

格网索引作为一种成熟的技术已经用于许多GIS平台，但其在基于CAD的入库软件中应用还不多。笔者通过将此技术引入CAD软件，将其改造成为具备一定空间索引和计算能力的软件，不但发挥了CAD软件的强大编辑能力，同时兼顾高效，其生产的数据也将更符合GIS平台的需求，并能产生良好的经济效益和社会效益。

［1］孟妮娜，周校东.固定格网划分的空间索引的实现技术［J］.北京测绘，2003(1)：7-11.

［2］吴信才.地理信息系统原理［M］.2版.北京：电子工业出版社，2009.

［3］李志猛，高有行.四叉树在Virtual GIS系统中的应用［J］.太原理工大学学报，2003，34(1)：90-92.

［4］王晓庆.曾文英.王明文.丁晖.设计模式中的面向对象原则及其子模式［J］.计算机工程，2003，29(9)：192-194.

［5］李长勋.AutoCAD ObjectARX程序开发技术［M］.北京：国防工业出版社，2005.

［6］张戈.CAD系统开发软件工程管理方法探索［J］.微型电脑应用，2000(6)：26-27.

［7］殷超.算用算法时间复杂度的计算方法［J］.科技信息，2011(29)：87.

［8］谢露蓉.地图图形数据拓扑关系的建立［J］.测绘科技动态，1999(2)：25-29.

［9］邵晓艳.刘宁 基于GIS海量数据的网格空间索引技术［J］.科技风，2009(22)：266-268.

［10］王欣.程耀东.孟凡相.ObjectARX二次开发运行机制及应用研究［J］.测绘科学，2009(S2)：184-187.

［11］KROENKE D M.数据库原理［M］.冯飞，译.北京：清华大学出版社，2009.