技术文章 > 一体化空间数据结构及其索引机制研究*

一体化空间数据结构及其索引机制研究*

2020-04-02 00:30

文档管理软件,文档管理系统,知识管理系统,档案管理系统的技术资料:

谈国新
(武汉城市建设学院建管系,武汉,430074)
STUDY OF INTEGRATED SPATIAL DATA STRUCTURE
AND SPATIAL INDEX MECHANISM
Tan Guoxin
(Wuhan Urban Construction Institute, Wuhan, 430074)
Abstract In this paper, a new integrated spatial data structure is proposed. The strategy that dividing tile into three grades and the representation technique of spatial occupancy enumeration are adopted, that make spatial data raster, at the same time to meet the requirement of data precision. A structure which have vector characteristics to express topology is proposed. In order to have raster function to carry out overlay analysis quickly and improve spatial query speed, raster-bit-matrix for arcs which are stored in arc index file and adaptive spatial index structure for polygons are introduced. Some experiments have shown feasibility of the method proposed in this paper.
Keywords Vector, Raster, Integrated spatial data structure, Spatial index mechanism
摘 要 本文提出了一种新的栅矢一体化空间数据结构,该结构采用三级划分策略及几何目标元子充填表达技术,使空间数据栅格化的同时,也能满足精度要求。同时引入弧段栅格比特阵和面要素自适应空间索引结构,有效地提高了空间检索效率。试验证明,上述理论及方法是可行的。
关键词 矢量 栅格 一体化空间数据结构 空间索引机制
分类号 TP309.12
1 引言
  栅格数据与矢量数据的最大区别是前者用元子空间充填集合表示,后者用点串序列表达边界形状及分布。因此栅格数据面向空间的数据结构在布尔运算、整体操作特征计算及空间检索方面有着明显的优势,而矢量数据面向目标的数据结构则很容易实现模型生成、目标显示及几何变换。鉴于栅格与矢量两种数据结构的优劣互补性,研究栅格矢量一体化数据结构已成为新一代GIS软件开发的基础。
  就一体化数据结构的研究过程来看,它经历了混合型→栅格索引型→矢量栅格化型三个阶段。混合型结构通过栅矢转换接口把栅格数据和矢量数据有机地结合在一起,并置于同一界面之下。目前市场上不少GIS软件采用混合型数据结构,它是一体化数据结构发展的雏型。栅格索引型数据结构的特点是空间数据仍用点线面的矢量数据结构,与此同时加入栅格索引结构来辅助矢量数据的编辑处理及空间分析。栅格索引结构典型的代表为QUILT系统[1],该系统采用PMR四叉树结构存贮线要素索引数据,它规定经过某结点的线数不超过某常数N,并通过分裂和合并两个规则动态地组织索引数据。由于在进行空间叠加分析处理时,栅格索引型数据结构仍需把矢量数据换成栅格数据,因此人们开始探讨栅矢更深层次的结合。矢量栅格化数据结构的特点是在建立空间栅格索引的同时,传统矢量型点线面数据也部分采用元子充填形式表示,即矢量数据栅格化。目前这方面较具代表性的研究为粗细分格网法[2],该方法假设整个区域由2n×2n个基本格网组成,首先把整个区域分成2n-4×2n-4个大块(粗格网),然后在基本格网的基础上再细分(细格网)。空间点位数据分别用表示粗格网和细格网位置的十进制Morton码表示。在空间数据存贮上,线要素以点串形式存贮弧段路径通过的所有基本格网,面要素的元子充填数据则按基于Morton码顺序的二维行程编码存贮。而线要素索引采用桶方法存贮,每个桶仅存贮经过该桶的线要素标识码。矢量数据栅格化结构既拥有栅格数据的优点又具有矢量数据的特点,是未来栅格矢量一体化数据结构研究的重点。
  栅矢一体化空间数据结构一个重要的研究领域是如何建立有效的空间索引结构。目前对线要素索引结构研究较多,主要有PMR四叉树[3]、带树[4]和桶方法[5]等,而面要素的索引结构主要有四叉树[6]和R树[7]等。这些结构各有自己的应用领域和相对优势,同时也都存在着不足。
  本文针对空间对象的特点,提出了一种新的空间数据存贮结构及其空间索引机制。该结构采用三级划分的栅格化表示方法,在线要素的存贮上引入部分栅格元子充填策略,并通过线要素桶索引结构中弧段基本格网比特阵的存贮及面要素自适应空间索引结构的建立,达到面向空间的数据结构和面向目标数据结构的统一。
  
2 一体化空间数据结构设计
2.1 三级划分策略
  一体化数据结构的第一步是将图幅(或称tile)空间栅格化,考虑到不同目的的空间查询及数据精度要求,这里采用三级划分的策略。首先将图幅区域均等地分成M1×M1个部分,其中M1应为2的整幂次方。一级划分得到的块我们称之为索引块,主要用来存贮线状地物的索引信息。
  二级划分是在索引块的基础上进行的,其划分原理与一级划分一样,把每个索引块均等地分成M2×M2个小格,每个小格称作基本格网,基本格网的概念可以同传统栅格图像像元的概念相联系。经一级和二级划分后,基本格网的尺寸已经比较小,因此面状地物充填数据的精度通常只需精确到二级划分。
  三级划分是在二级划分的基础上进行的,其目的是为了提高点状地物、线状地物及面状地物边界线空间位置的表达精度,使一体化数据结构的精度达到传统矢量数据的精度。三级划分同样也是将各个基本格网在逻辑上分成M3×M3个细小格子,每个细小格称作细分格网,它是空间划分的最小单位,其大小尺寸决定了一体化数据结构的空间定位精度,因此取值可尽量大一些。例如,当用2个字节来存贮细分格网编码值时,M3可取28;当用4个字节存贮编码值时,M3可取216。
  在一体化数据结构中,M1和M2的取值对空间数据的检索、编辑及精度有极其重要的影响。M1值越大,索引块的尺寸就越小,每一个索引块中包含的目标数也越少,这虽然有利于提高空间目标检索能力,但同时也增加了索引存贮量,特别当M1大到一定的程度时,就可能会出现许多没有目标通过的空索引块;反之,M1值越小,索引块的尺寸变大,块内目标数增多,从而降低了空间索引能力。一般来说,M1宜取25。M2的取值直接影响到弧段索引文件的存贮量,一般宜取24。显然,对长度为50 cm的地图,当M3=28时,点位精度可达图上3.8μ。
  在点线要素空间坐标的表达上,笔者认为索引块、基本格网和细分格网的编码宜采用行次序法。因为行次序法在关键字值计算、开窗显示等方面均优于Morton码次序,而Morton码次序法增加了像元之间相关性这一特征在面要素表达上比较有效,但对一体化结构的点线数据表达几乎用处不大。
2.2 存贮结构
  一体化数据结构仍借用矢量数据结构中点、线、面的概念,并假设点要素无长度、面积,线要素有长度无面积,面要素有周长和面积。事实上,这种假设是相对的,即针对于某一数据精度而言,当点要素在图上尺寸小到某个精度要求时,就可以认为它无长度和面积。
2.2.1 点要素的存贮结构
  在一体化数据结构中,点要素的存贮结构可以采用与矢量数据结构完全一致的方法。所不同的是,矢量数据存贮的是(x,y)坐标,而一体化结构中则需将坐标转化成索引块、基本格网和细分格网的地址码N1、N2和N3。
  如果设ai,bi(i∈{1,2,3})分别为第i级划分格网的长度和宽度,Ni为第i级的块编码,则相对坐标为(x,y)的某点,其索引块号N1、基本格网N2及细分格网号N3的计算过程为
  (1)
式中[ ]为取整,mod为取模。如果把上式取模看作一次乘除运算,则把点坐标(x,y)转换成三级格网单元的关键字值共需13次乘除运算。
2.2.2 线要素的存贮结构
  在一体化数据结构中,线要素的存贮引入了部分栅格元子充填的策略。所谓部分栅格元子充填即只对一级划分的索引块进行充填,存贮时仍采用角点(索引块点)串的形式存贮。部分栅格元子充填的好处是充填数据量少,通过充填点串很容易查得该线要素经过的索引块号。
  图1给出的是弧段1和2在索引块中的空间分布情况。从图中可以看出,虽然弧段1结点或角点只落在编号为80和113这两个索引块中,但按部分栅格(索引块)元子充填方法,该弧段经过的索引块编号有80、81和113,即点数为3。因此存贮时,不仅要把结点或角点作为坐标点,而且把弧段经过的索引块也当作一个坐标点看待,并称之为块点。为区别于一般的结点或角点坐标,块点坐标的N2值可用大于基本格网编码范围的某个大数来表示。例如,当M2为24时,弧段1的坐标串为(80,56,3045)(81,1000,0)(113,126,1016)。


图1 弧段空间分布
Fig.1 Spatial distribution for arcs
  弧段文件的存贮仍采用面向目标的形式,其数据结构可以用表1的形式表示。从表中可以看出,弧段文件每项记录不仅存贮了弧段的空间分布信息,而且包含了弧段与结点、弧段与多边形之间的拓扑信息。
2.2.3 面要素的存贮结构
  在一体化结构中,面要素数据仍通过建立面要素标识号与其边界弧段之间的拓扑关系来存贮,如表2所示。所不同的是多边形标识码对应的不是面域中的某一点,而是面域中所有基本格网的集合,即面要素边界内区域是通过元子充填的方法表示。
表1 弧段的数据结构
Tab.1 Data structure for arcs

弧段标识码 始结点码 终结点码 左多边形码 右多边形码 点数 点串(N1,N2,N3)
1 261 262 2 1 3 (80,56,3045)…
2 262 261 2 1 11 (113,126,1016)…


表2 面要素的数据结构
Tab.2 Data structure for polygon

多边形标识码 弧段数 弧段标识码串
2 2 1,2


  由于基本格网具有一定的间隔大小,用基本格网充填面要素区域,其充填范围是面要素的近似表达。如果要精确地计算面要素的周长和面积等信息,或精确地进行空间叠置运算,还必须借助面要素的边界信息。面要素的边界弧段信息是面要素空间分布的唯一精确表达方式。
3 空间索引机制
  建立空间索引机制的主要目的是便于空间目标的定位及各种检索操作。在一体化结构中共有两种不同类型的索引结构:一种是建立面向目标数据(点和线要素数据)的索引结构,以便直接明确目标与空间位置之间的二维关系;另一种是建立面向空间数据(面要素基本格网充填数据)的索引结构,以便使其部分具有面向目标的功能。由于点要素的数据结构简单、数据量少,且位置信息中已包含了三级划分格网的编码,因此建立索引结构的意义不大。这里主要讨论一体化结构中线要素的索引结构和面要素的索引结构。
3.1 线要素索引结构
  一体化数据结构中,考虑到索引数据量及操作方便程度,选择了以一级划分格网(索引块)地址码为关键字,采用桶方法建立其空间位置与弧段标识码之间的关系。由于索引块以行次序法编码,其关键字本身隐含了位置信息,且可直接作为线性索引文件数据的下标,即根据索引块编码直接进入某个索引项,从而省去了索引文件中关键字的查找过程。
  桶索引结构主要由内存中的桶目录表和外存文件中的数据块组成,如图2所示。内存中的索引表是一个一维数组,数组下标代表索引格网块的地址编码,数组单元值用来存贮指向外存索引文件相应数据块的指针。如指针值为零,表示该索引块中无弧段通过。外存索引文件中的数据块由弧段信息区,数据块链指针两部分区域构成。数据块的弧段信息区一般可存贮多个记录,其存贮记录的个数称为数据块(桶)容n(图2中n=6)。块容越大,检索过程中询问外存的次数越少,与此同时也增加了外存文件闲置空间,一般n取4至6的值为宜。


图2 线要素索引结构
Fig.2 Index structure for line feature
  为提高弧段信息的检索速度,弧段信息区的每条记录由三部分组成:弧段标识码,弧段指针,弧段基本格网比特阵。其中弧段指针直接指向该弧段在弧段文件中空间分布数据的存贮位置,而弧段基本格网比特阵存贮弧段在该索引块基本格网中面向空间的分布信息。由于弧段经过或未经过基本格网,只要用1和0表示,因此用比特阵来表示。为减少记录的存贮长度,每个索引块中的基本格网数不宜太多,一般M2宜取23或24。当M2=23时,弧段基本格网比特阵占8个字节(如图3所示),如M2取24,则弧段基本格网比特阵将占32个字节。弧段基本格网比特阵这种面向空间的存贮结构大大地弥补了弧段文件面向目标存贮结构的不足,为空间检索及空间分析提供了极大的方便。

图3 弧段基本格网比特阵
Fig.3 Raster-bit-matrix for arc
3.2 面要素索引结构
  面要素数据结构采用基本格网元子充填结构虽能提高空间数据的检索及分析能力,但也带来了数据量大的问题。为压缩存贮,通常采用四叉树技术,并用线性代码序列存贮。然而用线性代码序列(如线性四叉树)表示面要素数据至少存在下列问题:首先,当面要素各图形极不规则时,四叉树的分割层次可能很深,甚至出现许多黑结点为单个像元的情况,每次均要存贮多边形标识码,导致存贮效率的下降;其次,由于线性四叉树用线性代码序列表示,对某面要素属性值(标识码)的提取,需遍历整个代码序列才能得到,这大大影响了空间目标的检索效率。
  紧凑二叉树表示[8]也按四叉树的线性代码序列存贮,但它显式存贮四叉树层次结构的特点为我们自由地组织面要素索引结构提供了可能。这里引入面要素自适应的空间索引结构[9],其基本思想是在四叉树各层中选择合适的索引结点,存贮该索引结点范围内图像的概略信息,从而达到快速空间检索的目的。概略信息由三部分内容组成:索引结点范围内的属性数,属性值,代码字节数。自适应空间索引结构的关键是索引结点的大小不是固定的,它与面要素的分布有关,并在满足下列条件的情况下自适应地生成:
  ① 索引结点范围内不同面要素个数不应越过N;
  ② 索引结点上层父结点范围内不同面要素个数不能少于N+1。
显然,对某一给定的面状区域图像,满足上述条件的索引结点个数及位置都是唯一的。至于N的取值,太大或太小均不利于空间检索,在本试验中我们取N值为4。
  
4 试验与结论
  借助弧段索引文件,能快速实时地进行各种图形编辑和处理,并实时生成弧段索引文件。由于弧段索引部分地采用了栅格数据结构,每条弧段均有一个栅格层,从而增加了一定的存贮量。由于栅格只精确到基本格网,且按桶存贮其比特阵,因此存贮空间增加幅度比较小。表3给出了弧段数据量不同的四幅地图各弧段索引文件的大小。
表3 弧段索引文件数据量
Tab.3 Data quantity for index files of arc

类  别
地  图 弧段文件/bit 弧段索引文件/bit
M1=32,M2=8 M1=32,M2=16
地图1 107 376 98 360 232 880
地图2 86 428 59 636 138 836
地图3 3 586 416 254 936 613 340
地图4 234 608 93 404 220 844

  从表中可以看出,弧段索引文件所占空间随图形复杂度(弧段文件所占空间大小)的提高而增大,但递增速度是非线性的。例如,地图3弧段文件所占空间是地图2弧段文件的41.5倍,可弧段索引文件的数据量仅增加了3.3倍。此外,随着基本格网分辨力的提高,数据量不是平方增加。从表中看出,分辨力提高1倍,弧段索引文件数据量增加1.3倍左右。与传统弧段索引结构相比,新提出的索引结构虽然增加了一定的数据存贮量,但其面向空间的存贮格式大大提高了空间检索及空间拓扑叠加过程中矢量数据求交运算效率。特别是空间拓扑叠加分析过程中不生成任何中间文件,实验表明其操作快速实时。
  面要素充填信息通常以离成方式自动构建其自适应空间索引结构,由于它不需要支持数据实时插入和删除这样的数据模型,从而简化了数据结构。图4为表3中地图1经多边形充填后形成自适应空间索引结构的索引结点大小及分布示意图,其索引文件所占空间为35 220个bit,如用线性四叉树存贮,则存贮空间为85 528个bit。自适应空间索引结构不仅能有效地提高空间存贮效率,而且可通过索引结点概略信息的预处理来提高空间检索速度。在PC486/33机型上,提取图4所示自适应空间索引结构中某属性值空间分布数据,平均CPU时间开销为0.09 s,而从相应线性四叉树文件中提取则需2.81s。

图4 自适应空间索引结构分布图
Fig.4 The distribution of adaptive spatial index structure
5 参考文献
1 Shaffer C A, et al. QUILT:A Geographic Information System Based on Quadtree, INT. Geographical Information System, 1990(2):103~131
2 龚健雅.整体SIS的数据组织与处理方法.武汉:武汉测绘科技大学出版社,1993
3 Nelson R C and Samet H. A Consistent Hierarchical Representation for Vector Data. Computer Graphics, 1986(20):197~206
4 Ballard D H. Strip Trees Hierarchical Representation for Curves. CACM,1981,24(5):310~321
5 李爱勤,张巍.面向对象的GIS数据结构与空间对象索引新机制.武汉测绘科技大学学报,1995,20(增刊):43~49
6 Gahegan M N. An Efficient Use of Quadtree in a Geographical Information System. INT.J.GIS,1989,3(3):201~214
7 Guttman A. R-trees:A Dynamic Index Structure for Spatial Searching. In:Proc. of ACM SIGMOD Conference on Management of Data. Boston, Ma., June, 1984.49~47
8 谈国新,林宗坚.二值图像的紧凑二叉树表示及其编码方法.武汉测绘科技大学学报,1995,20(3):219~223
9 谈国新.多值图像的自适应空间索引结构研究.武汉测绘科技大学学报,1995,20(4):296~300
  *收稿日期: 1997-12-26, 截稿日期: 1998-06-08。谈国新,男,32岁,副教授,博士。