格网索引及四叉树在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的时间函数降低为线性级。……