（计算机软件与理论专业论文）面向查询的gis引擎的设计与实现.pdf

面向查询的g i s 引擎的设计与实现 计算机软件与理论 硕士生：冯黎 指导教师：李磊教授 摘要 在我们的经济建设、日常生活中，8 0 的信息都是与地理信息相关的。在g i s 应用中，高效的o i s 引擎是应用系统的核心。本文首先介绍了在g i s 引擎领域 的重要理论和概念，阐述了g i s 的数据模型：拓扑关系和面向实体的数据模型， 以及g i s 引擎的主要发展历史。 同时，本文提出了作者设计的面向查询的g i s 引擎一s m a r t b a s e ，重点讨论 了s m a r t b a s e 引擎的功能和设计架构。s m a r t b a s e 引擎是作者在李磊教授的悉心 指导下，设计和实现的面向查询的g i s 引擎。它具有面向实体的数据模型、快速 的空间索引技术、属性查询、空间查询、图形显示等功能，整个引擎借鉴了 m a p i n f o 、a r c i n f o 、o r a c l es p a t i a l 等g i s 引擎的思想，采用面向实体的数据模型， 保证了o l s 数据的完整性和一致性。 然后，本文详细介绍了s m a r t b a s e 引擎的层次模型，包括跨平台层、存储层、 空间索引层、空间运算层和表示层五层。s m a r t b a s e 跨平台层，封装了o s 的底 层接口，向上提供一个统一的接口层，使得应用在跨平台时，可阱减少移植量； 存储层，采用属性数据库和空间数据文件分开存储的模式，这是李磊教授提出的 o i s 地理对象数据存储的思想，在实际应用中能够提高查询效率；空间索引层采 用了四叉树的空间索引技术，提高了s m a r t b a s e 引擎空间运算的效率：空间运算 层详细阐述了空间运算所涉及到的空间运算算法：空间矢量运算、区域查询、 k 最近邻查询、周边查询等。最后，文章提出了s m a r t b a s e 引擎在未来需要进一 步研究的工作。 【关键字】g i s 引擎、栅格模型、拓扑关系模型、面向实体模型、g i $ 空间索引、空间矢 量运算、区域查询 量坐旦兰墅生望竺墨一 重旦奎塑塑望! ! ! 兰竺丝生皇壅婴 t h e d e s i g na n dr e a l i z a t i o no f i n q u i r y o r i e n t e dg i se n g i n e c o m p u t e r s o f t w a r ea n d t h e o r y n a m e ：f e n g l i s u p e r v i s o r ：p r o f l il e i a b s t r a c t i no u re c o n o m i cc o n s t r u c t i o na n dn o r m a ll i f e ，e i g h t yp e r c e n ti n f o r m a t i o na r e r e l a t e dw i t hg e g r a p h i ci n f o r m a t i o n i ng i s a p p l i c a t i o n s ，h i g h - e f f i c e n tg i se n g i n ei s t h ec o r e f i r s t l y ，t h i sa r t i c l ei n t r o d u c e st h ei m p o r t a n tt h e o r i e sa n d c o n c e p t i o n si ng i s d e v e l o p m e n t ， a n dt h e n e x p a t i a t e s t h ed a t am o d e lo f g i s ：t o p o l o g i c a n d e n t i t y o r i e n t e dd a t am o d e l ， a n dt h em a i n d e v e l o p m e n th i s t o r yo f g i s e n g i n e t h i sa r t i c l eb r i n g sf o r w a r dai n q u i r y - o r i e n t e dg i s e n g i n e s m a r t b a s ed e s i g n e db y a u t h o r ，a n dm a i n l yd i s c u s s e st h ef u n c t i o n sa n dd e s i g na r c h i t e c t u r eo fs m a r t b a s e e n g i n e s m a r t b a s ee n g i n ei s ai n q u i r y o r i e n t e dg i se n g i n e ，a n di s d e v e l o p e db y a u t h o ru n d e rp r o f e s s o rl il e i s g u i d a n c e i t h a s f o l l o w i n g c h a r a c t e r i s t i c s ： e n t i t y o r i e n t e dd a t am o d e l ，r a p i ds p a t i a l i n d e xt e c h n o l o g y ，a t t r i b u t e i n q u i r y ， s p a t i a li n q u i r y ，g r a p h i cd i s p l a ya n d s oo n t h ew h o l e e n g i n ea s s i m i l a t e st h ei d e ao f m a p n f o ，a r c g n f o ，o r a c l es p a t i a lg i se n g i n e ，a d o p t s t h ee n t i t y - o r i e n t e dd a t am o d e l a n dt h i se n s u r e st h ei n t e g r i t ya n dc o n s i s t e n c eo fg i sd a t a t h i sa r t i c l ea l s o p a r t i c u l a r l yd i s c u s s e st h eh i b e r a r c h yo fs m a r t b a s ee n g i n e i t a d o p t sf i v el a y e r s ：p l a t f o r m c r o s s e dl a y e r ，s t o r el a y e r ，s p a t i a ll a y e r ，s p a t i a li n d e x l a y e r ，s p a t i a lc a l c u l a t i o nl a y e ra n dd i s p l a yl a y e r p l a t f o r m ，c r o s s e dl a y e re n c a p s u l a t e s t h el o w e rl a y e ro fo s ，o f f e r sau n i f i e dr e f e r e n c ew a y st ot h eu p p e rl a y e r t h i sc a n r e d u c et h et r a n s p l a n tw o r ko ft h ee n g i n ew h e ni tc r o s s e so sp l a t f o r m 。s t o r el a y e r a d o p t sa t t r i b u t e d a t a b a s e p l u ss p a t i a l d a t af i l es t o r em o d e la n ds oe r d a a n t e st 1 1 e e f f i c i e n c y s p a t i a li n d e xl a y e ra d o p t sq t r e es p a t i a li n d e xt e c h n o l o g ya n d s oe n h a n c e s t h e s p a t i a li n q u i r ye f f i c i e n c y s p a t i a l c a l c u l a t i o n l a y e rp a r t i c u l a r l y d i s c u s s e st h e s p a t i a la l g o r i t h m s ：t h e b a s i cv e c t o rc a l c u l a t i o n ，r e g i o ni n q u i r y ，k n e a r e s tn e i g h b o r i n q u i r y ，a r o u n di n q u i r ye t c a tl a s t ，t h i sa r t i c l ep u t s f o r w a r dt h en e x ts t e pw o r ki nt h e f u t u r e k e y w o r d ：g i se n g i n e ，g r i dm o d e l ，t o p o l o g i cr e l a t i o nm o d e l e n t i t y - o r i e n t e d m o d e l ，g i s s p a t i a li n d e x ，s p a t i a l v e c t o r e a l e u l a t i n ，r e g i o ni n q u i r y 2 面向查询的g i s 引擎的设汁与实j ! ! 咆 第1 章g i s 引擎的关键理论 g i s 引擎是地理信息系统中的核心技术，它直接决定了整个应用系统的运行 效率。g i s 引擎开发要求开发和设计人员掌握扎实的地理信息知识和全面的计算 机知识。所以，在设计和实现高效的g i s 引擎之前，我首先详细地阐述关键的 g i s 理论。 1 1 地理空间基本概念 1 1 1 地球表面模型 自然表面：包括海洋底部、高山、高原在内的固体地球表面。在g i s 模型中， 自然表面由于地貌的复杂，难以用一个简洁的数学表达式描述出来，不适合数学 建模，并且它在长度、面积、体积等几何运算中都非常复杂。 大地水准面：假设地球处于当海水完全静止的平衡状态时，从海平面延伸到 所有大陆的底部，与地球重力方向处于正交的一个连续、闭合的水准面，就是大 地水准面。但是由于海水温度的变化、风浪的存在，导致水准面非常大的起伏变 化。 椭球体模型：如下。 1 1 2 地球空间数学模型 g i s 理论中的地球模型是基于椭球体模型的，椭球体模型就是以大地水准面 为基准建立起来的地球椭球体模型。设椭球体短轴上的半径记为c ，表示从极地 到地心的距离；椭球体长轴上的半径和中轴上的半径记为a 和b ，它们分别是赤 道面上的两个主轴。三者的关系用数学公式描述如下： x 2 a 2 + y 2 b 2 + z 2 c 2 ；1 依据不同的测量数据，可以得到若干不同的三轴椭球体数学模型。在实际研 究中，三轴椭球体十分复杂。所以为了计算方便，广泛采用双轴椭球体，用a 代 替了b ，双轴椭球体通常称为旋转椭球体： 一 x 2 a 2 + y 2 a 2 + z 2 c 2 = 1 旋转椭球体是地球表面模型中最简单的一类模型。我国一般采用克拉索夫斯 基椭球体作为地球表面集合模型。 中山大学硕士论文 面向查询的g i s 引擎的设计与实玑 1 1 3 地理空间坐标系 地球表面特征可以用经纬度和笛卡儿平面直角坐标系来度量。 经纬度坐标：即大地坐标，用经度和纬度表示的地球旋转椭球体坐标( n ，b ) ， 纬度用q 表示，n 一n 2 ，n 2 ，经度用0 表示，b 一n ， ，经纬度坐 标对空间位置的确定比较有利，但是难以进行距离、方向、面积等参数的计算； 笛卡几平面直角坐标：即二维欧几里德空间坐标，用( x ，y ，z ) 表示，笛卡儿 平面直角坐标对距离、方向、面积的计算有利； 大地坐标和平面直角坐标系之间的转化关系： x = a * c o s c o sb ： y = a * c o i q sa * c o s0 ： z = c * s j _ n ： 这个变换关系使得用经纬度表示的地球旋转椭球体( a ，b ) 与平面直角坐标 系之间建立了一种一一对应的空间转换关系：f ：( q ，”- - ( x ，y ) 。这个空间 变换关系实质上就是地图投影。地图投影变换引起了地理空间在平面形态上的变 化，包括长度变化、方向变化和面积变化。但是，平面直角坐标系( x ，y ) 易于 进行距离、方向、面积等空间参数的计算以及进一步的空间分析。g i s 中的地理 空间，通常就是指经过投影变化后，放在笛卡儿坐标系中的地球表层特征空间。 1 1 4 地图投影 地图投影：指的是将球面坐标转化为平面坐标，对于数据输入和数据可视化 都具有重要意义。 从球面到平面的投影导致了几何畸变，按照几何畸变，可将投影分为等角、 等面积、等距离投影。 ( 1 ) 等角投影：经纬线互相垂直，地面特征之间保持等角关系。对于面积较小 的区域，等角投影所造成的畸变程度较小，随着面积的增大，等角投影对区域所 造成的畸变程度也将增大。m e r c a t o r 投影就是等角投影的常见类型。 ( 2 ) 等面积投影：纬线投影为平行直线，经线投影为对称于中央经线的正旋曲 线，经纬线间距随着远距赤道逐渐减小，但保持等面积性质。由于点密度不受影 响，对于大面积上的点分布的表达适合于应用等面积投影。a l b e r 投影是等面积 投影的一种常见类型。 ( 3 ) 等距离投影：特征间角度关系和面积关系发生关系，但沿某个方向上的距 离关系保持不变。在地图集中经常使用等距离投影，因为等距离投影在等面积投 影所造成的角度畸变和等角度投影所造成的面积畸变之间起到平衡作用。 面向查咖的g i s 引擎的设汁与实现 按照可展表面的形状，投影可分为平而投影、圆锥投影和圆柱投影三种类型。 ( 1 ) 平面投影：球体表面的点被投影到平面上。球面等角投影是最常用的类型。 它假设表面与球体的极点相切，是地理坐标投影转化为极坐标。平面投影的公式 如下： r = 2 + t a n ( x 2 ) 和0 = 口( x = 9 0 一) ( 2 ) 圆锥投影：球体表面上的点投影到一个圆锥面上。这个圆锥或者与一个 小圆相切，或者穿过2 个小圆与其相割。与球体的一个标准纬线相切的等距离圆 锥投影的正转化方程如下： r = t a n ( x 0 ) + t a n ( x x o ) 和0 = bc o s ( x 0 ) ( 3 ) 圆柱投影面是一个圆柱的展开面。普通m e r c a t o r 投影属于圆柱投影，圆 柱轴通过地球的两极，并与地球赤道相切。球状地球的圆柱投影方程如下： x = b 和y = l o g 。t a n ( 目4 + d 2 ) 1 1 5 空间坐标的转换 在地球表面上的空间实体的位置，或者是以地理坐标( 球面坐标) 或者是以按 照某种投影类型的平面坐标来定义的。g i s 可以存储和操作地理坐标格式下的所 有空间数据。所有空间数据最终都要以平面坐标形式在显示器上显示。g i s 以平 面地图投影方式来存储空间坐标，可以避免在每次显示数据时都要进行从地理坐 标到平面投影坐标的重复性转换。 平面坐标按照原图的正北和正东方向进行分布。根据投影类型给出地图投影 的各个参数后，通过逆转换又可将平面坐标转换成地理坐标。在生成地理坐标后， 应用正转换方程可以将经、纬度转化为g i s 中所需要的平面坐标类型。 1 1 6 地理空间对象的分类 地理空间被表达为一个具有相互关系的对象集。每个对象不仅具有自己的几 何信息、属性信息和时间信息，而且与其他对象之间具有拓扑关系和语义关系。 根据地理对象的形状特点，将地理对象分为5 种基本的对象：点、线、面、标注、 复杂对象。前面四种对象比较简单，统称为简单对象，这里主要介绍第5 种对 象一复杂对象。 其中复杂对象由简单对象组合派生而来，可以划分为两种类型： 简单的复杂对象：分为复杂点、复杂线、复杂面三种。复杂点：即为点群， 由多个点状对象构成，整个集合为一个对象。复杂线：即为线群，由多个线状对 象构成的集合，整个集合是一个对象。复杂面：即为面群，由多个面状对象构成 中山大学硕士论文面向查询的g i s 引擎的设计与实现 的集合，整个集合是一个对象。 混合的复杂对象：即为点、线、面共存的复杂对象，包括点与线的混合、点 与面的混合、线与面的混合、点线面同时存在的混合。多个不同类型的对象合并 成一个就构成了混合的复杂对象。混合的复杂对象不属于点、线、面中的某一个 基本类型，在属性上也不具备这些基本类型对象的特有信息，例如线对象的长度， 面对象的面积和周长等。这些，我们在g i s 数据库设计时必须考虑的。 简单对象集中存储在相应的简单对象集中；单纯型复杂对象可以在相应类型 的简单对象集中存储，或者在复合对象集中存储；混合型复杂对象只能在复合对 象集中存储，它们不能加入简单对象集，否则会破坏简单对象集的专题特性。 我们可以将点、线、面统一抽象为面，这是软件所李磊教授提出的思想。这 样在形式上，我们具有了统一性将点可以抽象为面无限收缩即抽象为面；将 面的横跨度无限地缩小，面即抽象为线，在表达形式上，我们都得到了提升，同 时也进一步增进对地理对象的进一步认识。 1 1 7 欧氏平面的空间对象继承关系 下面，阐述欧氏平面的空间对象继承关系：空间对象在等级图的顶层；s p a t i a l 类包含p o i n t 和e x t e n t 两个类型，分别表示单独的点和二维的对象；e x t e n t 类又 可根据维数分为1 - e x t e n t 和2 - e x t e n t ；1 e x t e n t 的两个子类型a r c 和l o o p ，又包 含s i m p l ea r e 和s i m p l el o o p , 作为规则封闭集合的基本区域对象被称为a r e a 。 连通的a r e a 称为r e g i o n ，而一个简单连通的r e g i o n 被称为c e l l 。 中山大学顷士论义 面向查询的g i s 弓 擎的世计与实现 i ； ! l竺兰竺 li苎兰!l 、- 、一 兰l 一一一 f2 维刘蒙 i ! l 面对象 图1 1 欧氏平面的空间对象继承关系 1 1 8 地理空间表达 0 维矢量：0 维矢量为空间中的一个点 在三维欧氏空间中用唯一的三元数组( x ，y 点在二维欧氏空间中用( x ，y ) 表示， z ) 表示。在数学上，点没有大小、方 向。 l 维矢量：1 维矢量为空间中的一个线化要素，或者空间对象之间的边界， 也称弧段。在二维欧氏空间中用一组离散实数点( x l ，y 1 ) ，( x 2 ，y 2 ) ，( x n ， v n ) 来表示，在三维欧氏空间中用( x l ，y l ，z 1 ) ，( x 2 ，y 2 ，z 2 ) ，( x n ，y n ，z n ) 表示。其中( x 1 ，y 1 ) 或者( x 1 ，y l ，z 1 ) 是起始点，( x n ，y n ) 或者( x n ，y n ，z n ) 是终 止点。起始点和终止点统称为结点，位于起始点和终止点之间的其它点，包括( x 2 ， v 2 1 ，( x n 一1 ，y n 1 ) 或者( x 2 ，y 2 ，z 2 ) ，( x n 一1 ，y n 一1 ，z n 一1 ) 称为中间点。 一维矢量可以闭合，即孤段首尾相接。但是弧段不能与自身相交。如果相交，则 以交点为界将该一维矢量分为几个一维矢量。一维矢量是由方向的，起始于起始 点，结束于终止点。一维矢量具有长度，等于在矢量方向上相邻两点之间的距离 中山大学硕士论文 面向查询的g i s 弓【擎的设计与实现 之和。 2 维矢量：2 维矢量为空间中的一个面状要素，在二维欧氏平面上指一组闭 合弧段所包围的空间区域。描述二维矢量通常用等高线表示法、剖面表示法。描 述二维矢量的参数特征很多，主要参数有面积、凹凸性、单调性等。 我们可以将2 维矢量看作基本的空间对象，0 维矢量可以看作2 维矢量一面 无限抽象形成的点，1 维矢量可以看作是2 维矢量面的横跨度收缩维0 时抽象的 线。从而我们可以在认识上统一将2 维矢量作为基本的空间对象。 1 1 9 地理对象的拓扑空间关系 地理对象间的拓扑空间关系用来描述空间实体之间的相邻、包含和相交等空 间关系，主要有如下几种拓扑空间关系。 面和面的空间关系：分离、相离、重合、覆盖、包含、相交； 面和线的空间关系：分离、相邻、重合、包含、相交； 面和点的空间关系：分离、包含、相邻； 线和点的空间关系：分离、重合。 1 1 1 0 地理对象集 地理对象集是众多对象的集合，划分对象集的目的在于存储和管理对象a 它 可以由同种集合类型的对象构成，也可以由不同类型的对象构成。 在g i s 数据库中，简单地分为两类对象集：简单对象集、复杂对象集。 简单对象集分为简单点对象集、线对象集、面对象集和标注对象集四种。点 对象集是由简单点对象集或单纯型复杂点对象组成的集合；线对象集是由简单线 对象或单纯型复杂线对象组成的集合：面对象集是简单面对象或单纯型复杂面对 象组成的集合。 复杂对象集：由简单点、线、面对象、标注对象、单纯型复杂对象或混合型 复杂对象组成的集合。在这种集合中，可以包含任意类型的对象元素。 复合对象集为不同对象集中关联提供了一个集中存储与交互的独立空间，但 是同时也为系统开发和管理带来了一定的难度。 1 1 1 l 图层 对象集加上自己特有的显示属性即是图层，对象集类型和图层类型是一一对 应的。由于对象集包括点、线、面、标注对象集和复杂对象集5 种，所以图层也 中i j j 人学硕士论文 面向查咖的g 1 s 引擎的设计与实现 有相应的点、线、面、标注列象集、复杂对象集5 种基本类型。对象集主要负责 存储，是用来存储对象的空间和属性特征；图层是主要负责显示，用来设置对象 集的显示风格并控制对象集的显示范围、显示比例、和操作特性。 对象集是用来存储地理对象的，图层是用来控制对象的显示的。 i 对象类型存储的对象集显示的图层 点、简单的复杂点点对象集表点图层 线、简单的复杂线线对象集表线图层 面、简单的复杂面面对象集表面图层 混合的复杂对象复杂对象集表复杂图层 标注标注对象集袭 标注图层 1 1 1 2 地图窗口 表1 1 对象集和图层对比 地图窗口是一种框架，是显示对象的实际载体，也是控制图层并对之进行分 析和操作的主体。地图窗口负责显示地理对象给用户观看，进行相应的操作：编 辑、移动、放大、缩小等等。 1 2 空间对象的规范理论 c l a r k e 的有关空间个体的演算理论是空间对象规范理论的典型代表。c l a r k e 理论的中心内容是区域( r e g i o n ) 之问的二元联通关系。 c ( x ，y ) 表示“区域x 与区域y 连通”，则连通关系具有反射性和对称性， 即满足如下公理： 对任一区域x ，有c ( x ，x ) ； 对任两个区域x ，y ，如果有c ( x ，y ) ，则有c ( y ， x ) 。 c l a r k e 演算突出点在于，它表明空间对象之间的许多集合关系和拓扑关系都 可以用上述公理来构建： x d i s j o i n t f r o m y ：不存在c ( x ，y ) ，即x 和y 不连通。 x a p a r t o f y ：对任一区域z ，若c ( z ，x ) ，则c ( z ， y ) 。 x o v e r l a p s y ：存在一个区域z ，使得：z i sa p a r t o f y ，而x i s n o ta p a r to f y ， 且y i sn o ta p a r to f x 。 xm e e t s y ：c ( x ，y 1 且不存在xo v e r l a p s 。 xc o v e r s y ：y i s a p a r to f y ，而x i s n o t p a r to f y ，且存在一区域z ，使得：z 中山大学硕士论文 面向查询的g i s 引擎的设计与实现 m e e t s x 且z m e e t s y 。 x i s i n s i d e s y ：x i s a p a r t o f y ，而y i s n o ta p a r to f x ，且不存在一区域z 使得：z m e e t s x 且z m e e s t s y 。 x e q u a l s y ：x i sa p a r t o f y 且y i sa p a r t o f x 。 1 3 g i s 空间数据模型 在计算机中，现实世界使用各种符号来表达和记录的。计算机将这些符号用 二进制表达。模型是对现实世界的简化表达。地理空间必须离散化地表达，所有 地空间数据模型都是针对离散空间数据对象，如点、线、面建立的。g t s 中最常 用的数据组织方式为栅格模型和矢量模型。在栅格模型中，用空间单元c e l l 和 像元p i x e l 来表达；在矢量模型中，用点、线、面来表达世界。 1 3 1 空间实体的描述 g i s 中，空间实体可分为三种类型：空间特征数据、专题属性数据和时间属 性数据。时间和专题属性数据结合在一起，共同作为属性特征数据，空间特征数 据和属性特征数据统称为空间数据。属性特征数据通常以记录地方式组织，行代 表空间实体，列代表属性。 空间特征数据记录的是空间实体的位置、拓扑关系、几何关系，这是将地理 信息系统同其它行业的数据管理系统区分开的标志。空间位置以经纬度或带有局 部原点的线性坐标来表示。通常，人们理解空间实体的位置并不是通过实体的坐 标，而是通过这些实体和其他熟知实体的空间关系( 拓扑关系) 来考虑。为了能在 地理信息系统中，要从文字描述中提取空间实体的坐标和空间实体的参照物，拓 扑关系推理非常重要。 属性特征数据包括时间属性和专题属性。时间属性是指地理实体的时间变化 或数据采集的时间等；专题属性是指实体所具有的各种性质，如名称等。专题属 性可以以数字、符号、文本、或图像等形式来表示。 1 3 2 栅格模型 在栅格模型中，点是一个像元，线由一串彼此相连的像元构成，面由一块彼 此相连的像元构成。栅格模型适用于描述地球重力场之类的连续的空间变量。栅 格可以用数字矩阵来表达。栅格以一种简单的文件结构存储在磁盘中，文件按顺 序含有像元的直接地址。栅格的空间分辨率是指一个像元在地面所代表的实际面 积大小。栅格模型的优点是不同类型的空间数据层不需要经过复杂的几何计算就 ! 兰曼羔塑生型型! 一一 塑塑堡塑塑鱼! ! ! ! 兰塑坠生兰壅塑 可以进行叠加操作，栅格模型适合于表达模拟空间的连续变化，如海岸带的分布。 栅格模型的缺点是对于比例尺变换、投影变化等操作就很难实现。 栅格可以用数字矩阵来表达，它以种简单的文件结构储存在磁盘中，文件 按顺序含有像元的直接地址。 ( 1 ) 完全栅格结构：像元顺序以行为序，以左上角为七点，按从左到右的顺序 扫描。完全栅格结构可以波段顺序来组织( b s p 格式) ，单一波段或属性值以行的 顺序来存放，如果有两个以上的属性，第二个波段就在第一个波段结束后才开始 存放。多波段图像可以逐行格式( b i l ) 或以逐行格式( b i p ) 来记录。对于b i l ，先 存放各波段的第一扫描行，然后是各波段的第二扫描行；对于b i p ，先存储第一 个像元所有波段上的值，在存储第二个像元各波段值。对于显示较大的多波段影 像，b s p 更为有效。 ( 2 ) 游程编码：随着像元尺寸的减小，完全栅格结构影像的存储空间呈几何级 数增长，对于高分辨率的数据变得太大而无法管理。游程编码时一种简单的数据 结构，它能极大地减少存储空间。相邻属性值的邻近像元被合并在一起称为一个 游程，游程用一对数字表达；每个游程对中的第一个值表示游程长度，第二个值 表示游程属性值；每一个新航都以一个新的游程开始。表达游程长度的位数取决 于影像的列数，游程属性值取决于影像的最大类别数。通常用两个字节存储游程 长度，一个字节存储游程属性值。 123456789l o游程编码 1aaaabbbaa a( 4 ，a ) ，( 3 ，b ) ，( 3 ，a ) 2aaab bbaa ac( 3 ，a ) ( 3 b ) ，( 3 ，a ) ，( 1 ，c ) i 3aabb baaacc( 2 ，a ) ，( 3 ，b ) r ( 3 ，a ) ，( 3 ，a ) ， 2 ，c ) 4abbba accc c( 1 ，a ) ，( 3 ，b ) ，( 2 ，a ) ，( 4 c ) i 5aa a a aaccc c( 6 ，a ) ，( 4 ，c ) 1 3 3 矢量模型 表1 2 游程编码 矢量模型的点用空间坐标表示，线由一串坐标对组成，面由线形成的闭合多 边形。矢量模型能方便地进行比例尺变换、投影变换。空闻目标对象在矢量模型 中的空间特征信息连同属性特征信息一同存储，根据属性特征的不同，点可以用 不同的符号表示，线可以用不同的颜色和粗细程度不等的线来描绘，多边形可以 填充不同的图案和色彩。 ! 型型苎墅生竺鱼奎一 堕塑奎塑竺q ! ! ! ! 兰塑堡生兰壅望 1 3 3 1 拓扑关系数据模型 在拓扑模型中，多边形的边界被切割为一系列的弧和结点。弧、结点和多边 形之间的空间关系在属性表中确定。在拓扑模型中，空间目标的拓扑属性是在 s p a g h e t t i 模型空间坐标基础上定义的。在g i s 数据库中，拓扑意味着给s p a g h e t t i 文件增加拓扑结构。 在拓扑数据结构中，点是相互独立的，线是有一系列点相连构成的，链是一 个或多个多边形上的一条线，结点是线或者链相交或终止的点。多边形有一个外 环和零个或多个内环组成，这些内环在g i s 中被称为“岛”。 通常的拓扑结构有：p o l y v r t 结构、n c g i a 简单结构、c a n s i s 结构、t i g e r 结构、r o e s e l 结构。 p o l y v r t 结构是美国计算机图形与空间分析实验室研制的矢量数据结构， 是一种经弧段为基础的拓扑数据结构。主要以a r c i n f o 为代表。这些结构的基本 元素是“弧段”或“链段”。弧段在两个端点有结点，并伴有共享该段的左右两 个多边形的编码。弧段可以有任意多个中间节点。在p o l y v r t 模型中，多边形 也是弧段组成，每个多边形通过建立一个环绕边界的弧段目录表来生成。这种结 构不仅存储了空间对象的集合信息，而且还存储了空间对象之间的拓扑关系。 p o l y v r t 结构的特点是除了结点之外，每个空间对象都是由更基本的对象组成。 只有结点的坐标是被实际存储的，其他复杂对象的坐标信息实际上是逻辑构成 的，任何复杂对象能够分解为一组结点及其拓扑关系的定义。这样，一个图层中 存储的全部坐标信息就是结点的坐标，建立其他对象只是建立对这些坐标的引 用。因此，建立除结点外的其他对象，就必须建立拓扑关系。拓扑关系是显式存 储在“特征表”中的。而且，必须将此特征表填写完整，才能进行正确的拓扑关 系运算。在进行拓扑关系运算时，系统将根据现有的特征表快速进行查询。一个 简单的例子时，选定一个多边形，然后求其邻近多边形。由于已经建立了特征表， 所以只需要查找选定的多边形弧段列表，找到组成此多边形的弧，这个弧段对象 中记录的两个邻近多边形，一个时选定的多边形，而另外一个就是查询结果了。 在r o e s s e l 结构中，包括多边形拓扑表、环拓扑表、链拓扑表、中间结点坐 标表。多边形通过多边形拓扑表来定义。一个多边形有多个环，第一个环是外环， 其他的都是内环。环拓扑表，环由链组成。链拓扑表将结点和多边形建立起来。 r o e s s e l 结构的优点是多边形和多边形之间没有空间坐标的重复，消除了重复线； 拓扑信息和空间坐标分别存储，有利于近邻、包含、相连等查询操作。 1 4 ! 型堑篁茎型兰型生一 堕堕堡塑塑! ! ! ! i 兰堕丝! ! 兰壅些 环号链号 链序列号 2 3 1 2 2 2 l2 i l 4 2 31 1 35 2 表1 ，4 环拓扑表 链号开始结点终止结点 左多边形右多边形 1122 3 234 j2 343l 0 4430 1 5l2 32 表1 5 链拓扑表 结点号中间点号 11 4 21 1 31 43 表1 6 结点与中间点表 l 链号中间点号中间点序列 i 11 41 i 1 92 f 11 03 i 11 1 d 1 s 三里型苎墅生笪鱼茎一一耍塑奎塑塑婴i ! ! 兰塑堂生兰壅垫 拓扑数据模型的不足之处在于：拓扑表必须一开始就创建，需要时间和空间 图形显示较慢，因为图像显示需要空间坐标而非拓扑结构。 1 3 3 2 面向实体的数据模型 面向实体的数据模型将地理对象当作一个个实体单独存储。 s p a g h e t t i 结构： 在s p a g h e t t i 结构中，坐标表是与每个基本的空间对象例如点、线、面相联系 的。点、线和面都有各自的坐标表，互相之间并不相连。 点表：每个点由表中的一行来表示，列表示其空间特征和属性特征； 线表：由线段记录相连而成，每一条线段由顺次相连的点或中间点来定义。 定义线段的中间点的数目是可变的。线表记录信息分为两类，一类记录是线的i d 号、中间点数且和其他属性特征，它们组成每条线段记录的头文件，另类是每 个中间点坐标。 多边形表：多边形表与线表类似，但是它的最后一个坐标与第一个结点坐标 与第一个结点坐标值相同。针对多边形中存在“岛”的问题，在每个多边形的记 录中增加一条“岛”的属性来表示优先级，低优先级的的多边形先绘制先填充， 高优先级的岛后绘制后填充这样岛多边形就覆盖了原先的多边形。 【i d xya 1a 2a n i 1x ly 1a 1 la 1 2a i n 1 2x 2y 2a 2 la 2 2a 2 n 面门查询的g i s 引擎的硅计与实现 i 3x 3y 3a 3 1a 2 3 a 3 n 卜 【m x my ma m la i m l a 1 m n 表1 9 简单的点、线和闭合多边形的数据结构( s p a 曲e t t i 结构) 线的i d 号中问点总数目属性特征1属性特征2 中间点坐标 1527 ( x 1 ，y 1 ) ( x 2 y 2 ) ( x 3 ，y 3 ) ( x 4 ， y 4 ) ( x 5 ，y 5 ) 2247 ( x 1 ，y 1 ) ( x 2 ，y 2 ) 31 528 表1 1 0 线表 多边形i d中间点总数目属性特征1属性特征2中间点坐标 154 2 91 8 l f x l ，y 1 ) ( x 2 ， y 2 ) ( x 3 ，y 3 ) r x 4 ， y 4 ) ( x 5 ，y s ) 243 91 2 l f x l ，y 1 1 ) “2 ， i y 2 ) ( x 3 ty 3 ) ( x 4 ， y 4 ) l 3 8 l93 表1 1 1 多边形表 s p a g h e t t i 结构的好处就是能够顺次进行数字化绘制工作。但是这种结构的不 足，第一是数据冗余问题，由于多边形的边界重复带来的冗余问题，一幅地图由 多边形镶嵌而成，每个多边形都以闭合线段存储，每条线段都会重复记录一次： 第二是缺乏拓扑属性带来的计算代价，由于s p a g h e t t i 结构没有建立拓扑关系， 所以在空间分析和空间运算中，会带来计算的代价。 1 4 g i s 数据的组织 在g i s 中，对空间实体的数据描述分为空间特征和属性特征，属性特征是对 空间特征的描述，属性可以包括数字值和非数字值两种。 例如，在g i s 中道路的属性特征包括： 道路类型：1 = 高速公路 2 = 主干道 中山大学硕士论文 面向查询的g i s 引擎的设计与实现 路面构成 道路宽度： 道路名字： 3 = 居民街道 4 = 其他 1 = 水泥 2 = 柏油 3 = 碎石 m 米 那么，在道路的数据组织中，我们可以如下组织道路的数据 道路计数道路类型路面构成宽度道路名 ll水泥 6 0前进路 22柏油 4 8 光明路 34柏油 3 2红杉路 表1 ，1 2 道路的数据组织 表中每一条道路都有一组属性对其进行描述，这样的表被称为属性表。属性 表中每一行记录，它包含了针对某个空间实体的描述信息；表中每一列称为信息 描述的一个项。 空间特征数据的表达方式包括各种数据结构，并表现为点、线、面等各种图 形符号信息；属性特征数据的表达方式包括基于地理特征( 包括空间特征和属性 特征) 的多种分类关系的表格。地理信息系统正是通过建立空间特征数据的图形 符号表达与属性阿政数据的表格表达之间的联系，才具有强大的空间分析能力。 空间特征是通过坐标值和拓扑关系来表达，属性特征是组织成表格中一系列 的记录。如果对于每一个具有拓扑关系的空间特征以及这个空间特征的一个描述 记录赋予共同并且唯一的标识符号，那么，这个标识符号保证了在空间特征和属 性特征之间一一对应的关系。这样，我们就可以通过空间记录查找并显示属性信 息，或者依据存储在属性表格中的属性生成具有地学分析意义的空间图形。 ! 堕查兰兰生生堡兰二一堕塑垄型塑鱼! ! ! i 兰塑坠生：i 兰堡 1多边形面积区号所属区域 ia1 2 0 0 11 1 1 1 50 0 l白云区 l b1 5 7 7 51 卜1 1 5 0 0 2海珠区 1c1 9 ，1 61 l 1 1 5 0 0 3天河区 图1 2 多边形拓扑关系表与多边形属性表之间的联系 多边形一弧段拓扑关系表定义了多边形的空间特征拓扑关系，而多边形属性 表则通过共同的并且是唯一的多边形标识符a 、b 、c 与多边形一弧段拓扑关系 表建立了联系。 1 5 g i s 数据库 传统的g i s 数据库采用的数据模型有层次模型、网状模型、关系模型。 1 5 ，l 层次模型 层次模型是数据处理中发展较早、技术上比较成熟的数据模型。它的特点是 将数据组织成有向有序的树结构。结构中结点代表数据记录，连线描述位于不同 结点数据间的从属关系( 一对多关系) 。 层次模型反映了现实世界中实体间的层次关系，层次结构是众多空间对象的 自然表达，并在一定程度上支持数据的重构。 l ! 些查兰婴兰笙墨 亘塑奎塑塑望! 三! 兰塑垦盐兰壅塾 层次模型的缺点： 1 ) 对任何对象的查询必须始于其所在的层次结构的根，使得低层次对象 的处理效率比较低。难以进行反向查询。 2 ) 模拟多对多的关系导致物理存储上的冗余。 3 ) 数据独立性较差。 4 ) 基本不具备操作代数基础。 1 5 2 网状模型 网状模型的基本特征是，结点数据间没有明确的从属关系，个结点可与其 它多个结点联系。网状模型将数据组织成有向图结构。结构中结点代表数据记录， 联系描述不同结点数据之间的关系。 有向图的形式化定义为： d i g r a p h = ( v e r t e x ， r e l a t i o n ) 其中v e r t e x 为图中数据元素( 顶点) 的有限非空集合；r e l a t i o n 是两个顶点 ( v e r t e x ) 之间的关系的集合。 有向图结构比树结构具有更大的灵活性和更强的数据建模能力。网状模型可 以表示多对多的关系，其数据存储效率高于层次模型，但其结构的复杂性限制了 它在空间数据库中的应用。 网状模型反映了现实世界中常见的多对多关系，在一定程度上支持数据的重 构，具有一定的数据独立性和共享特征，并且运行效率较高。但是，存在下列缺 点：网状结构的复杂，增加了用户查询和定位的困难：网状数据操作命令具有过 程式性质；不直接支持对于层次结构的表达；基本上不具备演绎功能；基本上不 具备操作代数基础。 1 5 3 关系模型与二维表结构 关系是一组域的笛卡儿积的子集。给定一组域d 1 、d 2 、d n ( 可包含相 同的域1 ，其笛卡儿积为： d i d 2 d n = f ( d l ，d 2 ，d n ) l d i d i ，j = 1 ，2 ，n ) 其中每一个元素( d 1 ，d 2 ，d n ) q 做一个n 元组，简称元组。 关系r ( d 1 ，d 2 ，d n ) 是元组的集合，且 r ( d 1 ，d 2 ，d n ) 是d 1 d 2 x d n 的子集。 关系的具体实现是一个二维表结构，表结构中的行对应于元组，列对应于域， 列的名字称为属性。1 1 元关系必有n 个属性。满足一定条件( 如第一范式1 n f ) 的 规范化关系的集合，就构成了关系模型。 一2 0 中山大学硕卜论文 面向查铷曲g i s0 擎的敬引与丈现 关系模型具有严密的数学基础和操作代数基础，并且与一阶逻辑理论密切相 关，具有一定的演绎功能。 1 5 4 关系数据库的局限性 关系数据库的数据主要针对简单对象，无法有效地支持以复杂对象为主体的 地理空间数据。地理空间数据库系统必须具备对地理对象进行模拟和推理的功 能。一方面可以将地理空间数据库作为关系数据库的扩充；另一方面地理空间数 据库突破了传统的数据库理论。 地理空间数据库管理的主要对象是地理空倒数据，包括空间数据和非空间数 据。关系数据库管理空间数据有一下几个方面的局限： 1 ) 关系数据库