第6章_空间索引与空间信息查询

1、第第6章章 空间索引与查询6.1 空间索引空间索引一、 空间索引技术二、 简单格网空间索引三、 四叉树索引四、 R树索引五、 空间填充曲线 对一个数据集做“索引”，是为了提高对这个数据集检索的效率。 索引是用来提供快速、有选择性的存取数据库的一种机制。相当于一个映射机构，将属性的值转换为相应的地址或地址集。 对于空间数据，其存储主要依赖于空间对象之间的位置关系而非属性值。鉴于空间数据的特点，我们需要寻找适用的空间索引机制 。 一、空间索引一、空间索引1.空间索引的定义 空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，一般包括空间要素标识，外

2、包络矩形以及指向空间要素的指针。 2.空间索引的作用 为了GIS系统中快速定位到所选中的空间要素，从而提高空间操作的速度和效率。 空间索引的技术和方法是GIS关键技术之一，是快速高效的查询、检索和显示地理空间数据的重要指标，他的优劣直接影响空间数据库和GIS系统的整体性能。3.空间索引的分类 按照搜索分割对象不同,可将空间索引分为3类,即基于点区域划分的索引方法、基于面区域划分的索引方法和基于三维体区域划分的索引方法。B树是常见的基于点区域划分的索引。常见的空间索引常见的空间索引 常见空间索引一般是常见空间索引一般是自顶向下、逐级划分空自顶向下、逐级划分空间间的各种数据结构空间索引，比较有代表

3、性的包的各种数据结构空间索引，比较有代表性的包括括BSP树、树、R树、树、R+树和树和CELL树等。此外，结树等。此外，结构较为简单的格网型空间索引有着广泛的应用。构较为简单的格网型空间索引有着广泛的应用。二、二、 简单格网空间索引简单格网空间索引v基本思想是将研究区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。 为了便于建立空间索引的线性表,每个格网按一定规律进行编码，建立码与空间实体的关系,该关系表就成为格网索引文件。每个要素在一个或

4、者多个网格中,每个网格可以包含多个要素。 21232931535561632022283052546062171925274951575916182426485056585713153739454746121436384446139113335414302810323440422123293153556163202228305254606217192527495157591618242648505658571315373945474612143638444613911333541430281032344042空间索引对象索引Peano键空间对象空间对象Peano键集7BA25-2514EB7-

5、715EC54-5525AC60-6026ED32-3332DD35-3533DD38-3835D.FE14-1537EE26-2638DE37-3739EE39-3948EE48-4850EE50-5054CF35-3555C60CABCEDF每个要素在一个或者多个网格中每个要素在一个或者多个网格中,每个网格每个网格可以包含多个要素可以包含多个要素,要素不是真正被分割。要素不是真正被分割。由此建立由此建立Peano键和空间对象的关系。键和空间对象的关系。三三. 四叉树检索四叉树检索v点四叉树v区域四叉树 MX四叉树 PR四叉树vCIF四叉树1.点四叉树点四叉树 以空间点为划分点，将索引空间分

6、为两两不相交的的2k个子空间，依次与它的2k个子结点相对应，对于位于某一子空间的点，则分配给对应的子树。点四叉树的构造过程：（1）输入空间点A，以A为根节点并进行划分空间。（2）输入空间点B，B落入A的NW象限，并且A的NW象限为空，则B直接放入A的NW象限孩子结点。同理，C是A的SW孩子结点。（3）输入D，由于D落入A的NW象限，但是NW不为空，所以继续往下查找，得到B的NE象限为空，因此，D作为B的NE孩子结点。（4）同理，空间点E、F，分别为A的SE、NE孩子节点。缺点： （1）尽管点四叉树构造简单，但是删除一个节点时，该节点对应的所有子树节点必须重新插入四叉树中，效率很差。（2）对于精

7、确匹配的点查找，效率很高，但是对于区域查找，查找路径有多条，效率较差。（3）树的动态性差，树的结构完全由点的插入顺序决定。树的平衡难以保证。区域四叉树(Region-Based Quadtree)是以区域目标为循环分解对象的四叉树,分解过程既可以按照区域边界,也可以按照区域内部对二维空间进行划分。如果区域四叉树中的结点覆盖的区域中所有数组元素的值都相同，则该结点是叶子结点。否则，该结点是内部结点，被进一步划分为四个等大小的子结点。主要有MX四叉树与PR四叉树。避免了点四叉树的动态性差、结构完全由点的插入顺序决定的功能缺点。2.区域四叉树区域四叉树MX四叉树四叉树MX四叉树将每个空间点看成是区域

8、四叉树中的一个黑象素，或当成一个方阵（Square Matrix）中的非零元素，因此称为MX四叉树。利用叶子节点为黑节点或空闲点表示数据空间某一位置空间点的存在与否。树的构造过程即是对整个数据空间重复地进行2k次等分，直到每一空间点都位于某一象限的最左下角的过程。MX四叉树特点： 空间中每一个点都属于某一象限且位于该象限的最左下角，每一象限只与一个空间点相关联。尽管D同时是两个大小不等的象限的最左下角，但其应属于最下一级象限（即最后一次空间划分所产生的子象限）。这就决定了所有空间点均位于叶子节点。缺点：插入（或删除）一个点可能导致树的深度增加（或减少）一层或多层，所有的叶子节点都必须重新定位。

9、树的深度往往很大，这会影响查找效率。 PR（Point Region）四叉树叶子节点或者为空，或者包含唯一数据点。PR四叉树四叉树PR四叉树与MX四叉树的构造过程类似，不同的是，当分解到一个象限只包含一个点时，不需要继续分解使该点位于某一子象限的最左下角。另外，插入或删除一个点也不会影响到其他的分支，操作比较简单。PR四叉树与MX四叉树的区别：（1）数据点位于象限内，不要求位于左下角。（2）叶子节点可能不在树的同一层次。（3）PR四叉树的叶子结点数及树的深度都小于MX四叉树，因此PR四叉树效率高。CIF四叉树四叉树CIF四叉树是为了表示VLSI（Very Large Scale Integra

10、tion)应用中的小矩形而提出的。它可以用于索引空间矩形及其他形体。表示方式与区域四叉树类似，数据空间被递归的细分，直至产生的子象限不再包含任何矩形。在分解过程中，所有与任一划分线相交的矩形与该划分线对应的象限相关联。0数据桶的容量设为3。相交查询：从根节点开始，首先检查与之关联的所有矩形是否为查找结果；接下来检查象限空间与查询区域相交的孩子结点.直到叶子节点。插入矩形：首先检查根节点，如果与根节点的划分线相交，则插入到根节点对应的桶链表中；否则检查包含该矩形的子象限的孩子结点；如果检查到某一没有孩子的象限，而且该矩形依旧没有插入到对应的位置，那么该象限必须再次细分直到为该矩形找到对应的子象限

11、。删除矩形：找到矩形所在结点，从数据桶中删除。 如果删完后桶为空，且该节点没有孩子结点，则可以删除该节点。CIF四叉树可以用于索引矩形以及任何其他形体的空间目标而不需要经过目标近似与空间目标映射，因此对于区与查询，效率相对MX、PR四叉树要高些。但是区域查询往往需要访问多个节点对应的存储桶，尤其当索引量增大，大区域节点所包含较多数据矩形时，外存I/O开销很大。 四叉树索引优点： 结构清晰，容易建立。它同时具有聚集空间目标的能力（在栅格数据存储中发挥突出作用），提高了检索效率，得到广泛应用。有很多改进的方法被提出： （1）一体化索引，进行了索引空间的三级划分，包括索引块、基本格网、细分格网，并采

12、用行次序法对各级区域进行了编码。 （2）CELLQTREE， 叶子节点索引点对象， 中间节点索引线和面对象，较好的解决了大区域对象的标示符在子空间结点中的多次重复存储问题。 四叉树索引的缺点： 当索引数据量较大时，如果四叉树层次过小，将导致查找性能下降；如果四叉树层次过大，将导致重复存储的增加，从而增加空间开销，这同时又会影响查找性能。四四.R.R树空间索引树空间索引1.R树 1984年Guttman发表了R树:一种空间查询的动态索引结构，首次提出了R树空间索引结构。 其后，人们在此基础上针对不同空间运算提出了不同改进，才形成了一个繁荣的索引树族，是目前流行的空间索引。 R树是一种高度平衡的树

13、，由中间节点和页节点组成，实际数据对象的最小外接矩形存储在页节点中，中间节点通过聚集其低层节点的外接矩形形成，包含所有这些外接矩形。 R树是一种动态索引结构，即：它的查询可与插入或删除同时进行，而且不需要定期地对树结构进行重新组织。R树示例图树示例图五、空间填充曲线五、空间填充曲线v空间填充曲线是一种重要的近似表示方法，将数据空间划分成大小相同的网格，再根据一定的方法将这些网格编码，每个格指定一个唯一的编码，并在一定程度上保持空间邻近性，即相邻的网格的标号也相邻，一个空间对象由一组网格组成。这样可以将多维的空间数据降维表示到一维空间当中。v理想的空间映射方法是：在多维空间中聚集的空间实体，经过

14、填充曲线编码以后，在一维空间中仍然是聚集的。 （a）行排序 （b）Hilbert排序 （c）Z排序 图5-30 几种常用的空间填充编码方法1) Z-ORDERING曲线（曲线（PEANO曲曲线）线）l Z-排序（Z-ordering）技术将数据空间循环分解到更小的子空间（被称为Peano Cell），每个子空间根据分解步骤依次得到一组数字，称为该子空间的Z-排序值。l 子空间有不同的大小，Z-排序有不同的长度，显然，子空间越大，相应的Z-排序值越短。这里，分辨率（resolution）是指最大的分解层次，它决定了Z-排序值的最大长度。 图5-31 Z-排序示例2n 2n个分区， 编号为02n

15、2n-12) HILBERT曲线曲线v与Z-排序类似，Hilbert曲线也是一种空间填充曲线，它利用一个线性序列来填充空间，其构造过程如图5-33所示。v实验证明，Hi1bert曲线的方法比Z-排序好一些，因为它没有斜线。不过Hilbert曲线算法的计算量要比Z-排序复杂。 图5-33 Hilbert曲线示例6.2 空间查询空间查询一. 空间信息与 空间信息查询二. 空间查询方式三. 空间信息查询语言一一.空间信息与空间信息查询空间信息与空间信息查询v空间位置和形态 对象所在的地理区域，对象的几何和属性特征。v空间关系和关联 空间对象间的拓扑关系。v空间分布规律 特定类别地物分布在特定的区域，

16、如电子市场、娱乐场所、饮食街等。v时空演化 通过时间空间数据分析，可以研究和揭示事物发展演化的规律。空间信息分类空间信息分类空间信息查询空间信息查询 v查询什么 空间查询的一般问题是“有没有？”、“是什么？”、“在什么地方？”、“怎样（到达）？”v查询对象 图形中的信息 属性表中的信息 其它信息 一般问题是“某图元代表什么实体，有什么属性”、“处于什么位置、距离、路径”、“一定范围内包含的地物，地物之间的关系等”。查询的意义查询的意义 v信息管理 通过查询可以获取特定数据，进行信息管理和数据更新。v特定信息提取 通过查询提取需要的信息，据弃无关的信息，便于使用。v空间分析基础 查询结果一般是对

17、所需查找的信息及数据的报告，研究需要对这些数据单独提出进行相关分析。1、图查文(图形查询属性)2、文查图(属性查询图形)2、空间关系的查询(面点、面线、面面、线点、线线查询 )4、逻辑查询(SQL查询)二二.空间查询方式空间查询方式图文互查是GIS中最常用的查询。如：在中国行政区图查人口4000万的省。1）和一般SQL查询类似，构建SQL查询语句进行查询。2）查询到结果后，利用图形和属性的对应关系，再图上表示出结果。1、图查文、图查文图查文图查文图查文图查文2、文查图、文查图 一般GIS软件提供“INFO”工具。用点选、区域圈选、多边形选择、矩形选择的方式选中地物，并显示出查询对象的属性列表。

18、1）利用空间索引，在数据库中快速检索被选空间实体。2）根据实体和属性的连接关系得到所查询实体的属性列表。文查图文查图文查图文查图MapInfo软件中软件中点目标点目标的几何参数查询的几何参数查询MapInfo软件中软件中线目标线目标的几何参数查询的几何参数查询Mapinfo软件中软件中面状目标面状目标的几何参数查询的几何参数查询是指给定一个点或一个几何图形，检索出是指给定一个点或一个几何图形，检索出该图形范该图形范围内围内的空间对象以及相应的属性。这种查询方式又的空间对象以及相应的属性。这种查询方式又称为称为图形查询属性图形查询属性的方式。的方式。 MapInfo软件中图形查属性的表达方式软件

19、中图形查属性的表达方式ArcView软件中图形查属性的表达方式软件中图形查属性的表达方式3、空间关系的查询、空间关系的查询 通过空间关系查询和定位空间实体是地理数据库不同于一般数据库的功能之一。 如查询满足下列条件的城市：沪线东部（空间方位关系）；距离京沪线不超过50km（空间距离关系）;城市人口大于100万（属性信息查询）；面面查询面面查询 如与某个多边形相邻的多边形有哪些如与某个多边形相邻的多边形有哪些面线查询面线查询 如某个多边形的边界有哪些线如某个多边形的边界有哪些线面点查询面点查询 如某个多边形内有哪些点状地物如某个多边形内有哪些点状地物线面查询线面查询 如某条线经过（穿过）的多边形

20、有哪如某条线经过（穿过）的多边形有哪 些，某条链的左、右多边形是哪些些，某条链的左、右多边形是哪些线线查询线线查询 如与某条河流相连的支流有哪如与某条河流相连的支流有哪 些，某条道路跨过哪些河流。些，某条道路跨过哪些河流。线点查询线点查询 如某条道路上有哪些桥梁，某条如某条道路上有哪些桥梁，某条 输电线上有哪些变电站。输电线上有哪些变电站。点面查询点面查询 如某个点落在哪个多边形内。如某个点落在哪个多边形内。点线查询点线查询 如某个结点由哪些线相交而成。如某个结点由哪些线相交而成。 城镇城镇查询城镇是否位于平原区内举例：点面查询举例：点面查询(1)邻接查询邻接查询从多边形与弧段关系的表中，检索

21、出该多边形关从多边形与弧段关系的表中，检索出该多边形关系的所有弧段系的所有弧段从弧段关系的左右多边形的表中，检索出这些弧从弧段关系的左右多边形的表中，检索出这些弧段所关联的多边形段所关联的多边形(2) 包含关系查询包含关系查询 查询某一个面状所包含的某一类的空间对象查询某一个面状所包含的某一类的空间对象(3) 穿越查询穿越查询长江所经过的县市(4) 落入查询落入查询 查询一个空间对象它落在哪个空间对象之内。查询一个空间对象它落在哪个空间对象之内。可采用空间运算，使用点在多边形内，线在多边可采用空间运算，使用点在多边形内，线在多边形内，或面在多边形内的差别方法。形内，或面在多边形内的差别方法。

22、(5) 缓冲区查询缓冲区查询 缓冲区查询根据用户需要给定一个点缓冲、缓冲区查询根据用户需要给定一个点缓冲、线缓冲或面缓冲的距离，从而形成一个缓冲区的线缓冲或面缓冲的距离，从而形成一个缓冲区的多边形，再根据多边形检索的原理，检索出该缓多边形，再根据多边形检索的原理，检索出该缓冲区多边形内的空间地物。冲区多边形内的空间地物。 距黄河距黄河150公里范围内的主要城市公里范围内的主要城市 （6） 地址匹配查询地址匹配查询 根据街道地址来查询事物的空间位置和属性根据街道地址来查询事物的空间位置和属性信息是地理信息系统特有的一种查询功能，这种信息是地理信息系统特有的一种查询功能，这种查询利用地理编码，输入

23、街道门牌号码，就可知查询利用地理编码，输入街道门牌号码，就可知道大致的位置和所在的街区。道大致的位置和所在的街区。 （7）SQL查询查询 （7）SQL查询查询 查询机耕道ArcGIS三三.空间信息查询语言空间信息查询语言、SQL查询语言、扩展的SQL查询MapInfo软件中SQL输入标准对话框 通过SQL语言查询的结果 Select from whereGIS中中SQL查询例查询例1GIS中中SQL查询例查询例2查世界地图属性表中有多少国家查世界地图属性表中有多少国家?总人口总人口?总面积总面积?多表连接查询多表连接查询如查出美国地图数据中总人口大于1000万 且州府人口大于20万的州 。 S

24、ELECT * FROM States, Statecap WHERE States.state = Statecap .State and States.pop_199010000000 and Statecap.pop_1990 200000嵌套查询嵌套查询求世界地图中同伊拉克处于同一大洲的国家 SELECT country,continent FROM world WHERE continent = (SELECT continent FROM world WHERE country=“Iraq” )； 首先求出伊拉克处于哪个洲；之后求出同伊拉克处于同一洲的国家。扩展扩展SQL查询查询1

25、、查询谓词的扩展、查询谓词的扩展Mapinfo在SELECT语句中增加了地理函数和地理运算符.1、查询谓词的扩展、查询谓词的扩展例例 ：美国：美国“I 10”号高速公路经过哪几个洲？号高速公路经过哪几个洲？ 先先美国高速公路中美国高速公路中找出找出 “I10”号高速公路；号高速公路； 再找再找“I 10”号高速公路经过哪几个洲号高速公路经过哪几个洲。WHERE States.obj CONTAINS Us_Hiway.obj AND (States.obj INTERSECTS (SELECT obj FROM Us_Hiway WHEREus_Hiway.highway= “I 10”)地地

26、 理理 运运 算算 符符 例如查询三峡地区长江流域人口大于例如查询三峡地区长江流域人口大于50万的县万的县或市，扩展的或市，扩展的SQL空间查询语句为：空间查询语句为： SELECT * * FROM 县或市县或市 WHERE 县或市县或市人口人口50万万 AND CROSS （河流河流名称名称=“=“长江长江”） 1、查询谓词的扩展、查询谓词的扩展扩展SQL空间查询结果 这些这些SQLSQL扩充和应用有关，目前还没有形成标准。扩充和应用有关，目前还没有形成标准。例：例：（1 1）选择河南省所有城市和人口）选择河南省所有城市和人口 SELECT SELECT 城市名，人口城市名，人口 FROM

27、 FROM 城市城市 WHERE WHERE CENTERCENTER（城市地图）（城市地图）INSIDEINSIDE 河南；河南；（2 2）选择流经河南省的所有河流的名称和河南境内长度）选择流经河南省的所有河流的名称和河南境内长度 SELECT SELECT 河流名，河流名，LENGTHLENGTH（INTERSECTSINTERSECTS （ROUTEROUTE（河流流域图），（河流流域图），河南）；河南）； FROM FROM 河流河流 WHERE WHERE ROUTEROUTE ( (河流流域图河流流域图) )INTERSECTSINTERSECTS 河南；河南；1、查询谓词的扩展、

28、查询谓词的扩展 2、面向对象的扩展、面向对象的扩展2、面向对象的扩展、面向对象的扩展v OGIS协会（Open GIS）是由一些主要软件供应商组成的联盟，负责制定与GIS互操作相关的行标准。OGIS的空间数据模型可以嵌入到各种编程语言中，例如C、Java、SQL等等，提出了一套规范，把二维地理空间ADT（abstract data type, 抽象数据类型）整合到SQL之中，并且包括了指定拓扑的操作和空间分析操作。在OGIS标准中，所指定的操作可分成三类： 用于所有几何类型的基本操作。例如，用于所有几何类型的基本操作。例如，SpatialReference返回返回所定义对象几何体采用的基础坐标

29、系统。所定义对象几何体采用的基础坐标系统。 用于空间对象间拓扑关系的操作测试。例如，用于空间对象间拓扑关系的操作测试。例如，overlay判断两判断两个对象内部是否有一个非空的交集。个对象内部是否有一个非空的交集。 用于空间分析的一般操作。例如，用于空间分析的一般操作。例如，distance返回两个空间对象返回两个空间对象之间的最短距离。之间的最短距离。 例如：查询面积较小，噪声小，住宅低价偏低的宗例如：查询面积较小，噪声小，住宅低价偏低的宗地号。地号。SELECT SELECT 宗地号宗地号 FROM FROM table_pricetable_priceWHERE WHERE （面积（面积

30、=较小较小 AND AND 噪声噪声=小小 AND AND 住住宅低价宅低价=偏低偏低3、模糊扩展、模糊扩展v突破关系模型中关系必须是第一范式的限制，允许定义层次关系和嵌套关系。v增加抽象数据类型，如点、线、面、栅格、图像等。v增加空间谓词。如表示空间关系的，包含、相交等，表示空间操作的，叠加、缓冲区等。v增加适合空间数据索引的方法，如R数、四叉树等。1)扩展SQL以处理空间数据在在SQL的基础上进行扩展将是管理和分析空间的基础上进行扩展将是管理和分析空间数据的一个趋势。扩展关系模型主要表现在：数据的一个趋势。扩展关系模型主要表现在： 定义的空间操作算子包括基本操作、空间关系运算和空间分析操作

31、。操操作作类类别别 方方法法名名称称 返返回回值值 类类型型 描描述述 Dimension ( ) Integer 返回几何对象的维数。 GeometryType ( ) String 返回几何对象的类型。 SRID ( ) Integer 返回几何对象所属的空间参考系ID。 Envelope( ) Geometry 返回几何对象的最小外包矩形。 AsText( ) String 将几何对象以WKT格式输出。 AsBinary( ) Binary 将几何对象以WKB格式输出。 IsEmpty( ) Integer 如果几何对象为空集， 则返回1 （为真， 下同） 。 IsSimple( ) I

32、nteger 如果几何对象是简单的 （不自交） ， 则返回1。 基基本本操操作作 Boundary( ) Geometry 返回几何对象的边界。 Equals(anotherGeometry) Integer 如果两个几何对象的内部和边界在空间上相等，则返回1。 Disjoint(anotherGeometry ) Integer 如果两个几何对象的内部和边界在空间上都不相交，则返回1。 Intersects(anotherGeometry ) Integer 如果两个几何对象在空间上相交，则返回1。 Touches(anotherGeometry ) Integer 如果两个几何对象边界相交但内部不相交， 则返回1。 Crosses(anotherGeometry) Integer 如果一条线和面的内部相交，则返回1。 Within(anotherGeometry) Integer 如果这个几何对象空间上位于另一个几何对象内部，则返回1。 Contains(anotherGeometry) Integer 如果这个几何对象空间上包含另一个几何对象，则返回1。对于两个几何对象A、B，如果A.contains(B)为真 ，则 A.within(B)为真，即A.contai