第二章空间数据结构

《第二章空间数据结构》由会员分享，可在线阅读，更多相关《第二章空间数据结构（37页珍藏版）》请在金锄头文库上搜索。

1、地理信息系统原理与方法地理信息系统原理与方法第二章 空间数据结构学习目标学习目标 理解地理空间信息的概念 掌握地理空间信息的描述方法 理解地理数据分类描述的方法 理解和掌握地理空间数据的拓扑关系 掌握栅格和矢量数据结构及其编码方法 了解栅格与矢量数据之间的转化方法重点：重点：地理空间数据的拓扑关系、两种空间数据结构的特点及其编码方法。难难 点点：拓扑结构、栅格数据编码栅格数据结构基本概念栅格数据结构指将空间分割成各个规则的网格单元，然后在各个格网单元内赋以空间对象相应的属性值的一种数据组织方式；在栅格结构中，点用一个栅格单元表示；在栅格结构中，点用一个栅格单元表示；线状地物则用沿线状地物则用沿

2、线走向的一组相邻栅格单元表示，每个栅格单元最多只有线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元在线上；面或区域用记有区域属性的相邻栅两个相邻单元在线上；面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。任何以面状分布的对象，都可以用栅格元同属一个区域。任何以面状分布的对象，都可以用栅格数据逼近。数据逼近。例子 用栅格结构表示地图，首先要给定每个物体的编码，如给定高程点的编码为8，烟囱的编码为7，铁路的编码为1，居民点的编码为5，林地的编码为3，菜地的编码为4，则地图用栅格结构表示为

3、下图。 栅格结构的特点属属性性明明显显，定定位位隐隐含含，即即数数据据直直接接记记录录属属性性本本身身或或属属性性的的编编码码，而而所所在在位位置置则则根根据据行行列列号号转转换换为为相相应应的的坐坐标标给给出出。由由于于栅栅格格结结构构是是按按一一定定的的规规则则排排列列的的，所所表表示示的的实实体体的的位位置置很很容容易易隐隐含含在在网网格格文文件件的的存存贮贮结结构构中中，在在网网格格文文件件中中每每个个代代码码本本身身明明确确地地代代表表了了实实体体的的属属性性或属性的编码或属性的编码 栅栅格格结结构构表表示示的的地地表表是是不不连连续续的的，是是量量化化和和近近似似离离散散的数据的数

4、据 栅栅格格数数据据的的比比例例尺尺就就是是栅栅格格大大小小与与地地表表相相应应单单元元大大小小之比之比图 量化示意图（a） 量化； (b) 量化为8 bit 栅格数据层在栅格数据结构中，物体的空间位置是用其在笛卡尔平面网格中的行号和列号坐标表示，物体的属性用像元的取值表示，每个像元在一个网格中只能取一次，同一像元要表示多重属性的事物就要用多个笛卡尔平面网格，每个笛卡尔网格表示一种属性或同一属性的不同特征，这种平面即层A.OBC中心点法中心点法重要性法重要性法长度占优法长度占优法面积占优法面积占优法栅格数据的取值方法栅格数据的取值方法1 1、直接栅格编码、直接栅格编码 直接编码就是将栅格数据看

5、作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。 0，2，2，5，5，5，5，5；2，2，2，2，2，5，5，5；2，2，2，2，3，3，5，5；0，0，2，3，3，3，5，5；0，0，3，3，3，3，5，3；0，0，0，3，3，3，3，3；0，0，0，0，3，3，3，3；0，0，0，0，0，3，3，3。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0

6、3 3 3 3 30 0 0 0 3 3 3 31 1、直接栅格编码、直接栅格编码 直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。 0，2，2，5，5，5，5，5；5，5，5，2，2，2，2，2；2，2，2，2，3，3，5，5；5，5，3，3，3，2，0，0；0，0，3，3，3，3，5，3；3，3，3，3，3，0，0，0；0，0，0，0，3，3，3，3；3，3，3，0，0，0，0，0。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3

7、3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 31 1、直接栅格编码、直接栅格编码 直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。 0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3

8、 3 33，3，3，3，3，2，2，2；3，3，3，3，3，3，3，0；0，0，0，2，2，2，2，2；5，5，5，5，5，3，3，3；3，0，0，0，0，0，0，0；2，2，0，2，2，5，5，5；5，5，5，5，5，3，3，3；3，3，3，0，0，0，0，0。1 1、直接栅格编码、直接栅格编码 直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。 0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50

9、0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 30 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16123456789101112131415160, 1, 02, 3, 02, 1, 0, 30, 1, 03, 32, 2, 33 ,02, 105, 32 ,22,

10、 3, 24, 3, 24, 12, 22, 1, 22, 1, 22, 132 2、链式栅格编码、链式栅格编码3 3、行程编码（游程长度编码）、行程编码（游程长度编码）只在各行（或列）数据的代码发生变化时依次记录 该代码以及相同代码重复的个数；0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3沿沿行方向进行编码行方向进行编码：( 0，1），），（2，2），（），（5，5）；（）；（2，5），），（5，3）

11、；（）；（2，4），（），（3，2），），（5，2）；（）；（0，2），（），（2，1），），（3，3），（），（5，2）；（）；（0，2），），（3，4），（），（5，1），（），（3，1）；）；（0，3），（），（3，5）；（）；（0，4），），（3，4）；（）；（0，5），（），（3，3）。）。逐个记录各行（或列）代码发生变化的位置和相应代码，即按（位置，属性值）编码。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0

12、0 3 3 3 3沿沿列方向进行编码列方向进行编码：( 1，0），），（2，2），（），（4，0）；（）；（1，2），），（4，0）；（）；（1，2），（），（5，3），），（6，0）；（）；（1，5），（），（2，2），），（4，3），（），（7，0）；（）；（1，5），），（2，2），（），（3，3），（），（8，0）；）；（1，5），（），（3，3）；（）；（1，5），），（6，3）；（）；（1，5），（），（5，3）。）。3 3、行程编码（游程长度编码）、行程编码（游程长度编码）3 3、游程长度编码、游程长度编码逐个记录各行（或列）代码发生变化的位置和相应代码，即（起位，止位，属性值）

13、。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3( 1，1，0），（），（2，3，2），（），（4，8，5）；）；（1，5，2），（），（6，8，5）；）；（1，4，2），（），（5，6，3），（），（7，8，5）；）；（1，2，0），（），（3，3，2），（），（4，6，3），），（7，8，5）；）；（1，2，0），（），（3，6，3），（），（7，7，5），），（8，8，3）；）；（1，3，0），（

14、），（4，8，3）；）；（1，4，0），（），（5，8，3）；）；（1，5，0），（），（6，8，3）。）。 4 4、块码、块码 采用方形区域作为记录单元，数据编码由初始位置行列号加上半径，再加上记录单元的代码组成。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3（1 1，1 1，1 1，0 0），（），（1 1，2 2，2 2，2 2），），（1 1，4 4，1 1，5 5），（），（1 1，5 5，1

15、 1，5 5），），（1 1，6 6，2 2，5 5），（），（1 1，8 8，1 1，5 5）；）；（2 2，1 1，1 1，2 2），（），（2 2，4 4，1 1，2 2），），（2 2，5 5，1 1，2 2），（），（2 2，8 8，1 1，5 5）；）；（3 3，3 3，1 1，2 2），（），（3 3，4 4，1 1，2 2），），（3 3，5 5，2 2，3 3），（），（3 3，7 7，2 2，5 5）；）；（4 4，1 1，2 2，0 0），（），（4 4，3 3，1 1，2 2），），（4 4，4 4，1 1，3 3）；（）；（5 5，3 3，1 1，3 3），），（5

16、5，4 4，2 2，3 3），（），（5 5，6 6，1 1，3 3），），（5 5，7 7，1 1，5 5），（），（5 5，8 8，1 1，3 3）；）；（6 6，1 1，3 3，0 0），（），（6 6，6 6，3 3，3 3）；）；（7 7，4 4，1 1，0 0），（），（7 7，5 5，1 1，3 3）；）；（8 8，4 4，1 1，0 0），（），（8 8，5 5，1 1，0 0）。）。 5 5、四叉树编码、四叉树编码 是根据栅格数据二维空间分布的特点，将空间区域按照4个象限进行递归分割（2n2 n，且n1），直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。四叉树分解，各子

17、象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，它对应于整个图形。不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。 为了保证四叉树分解能不断的进行下去，要求图形必须为2n2 n的栅格阵列。n 为极限分割次数，n1是四叉树最大层数或最大高度0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0

18、 0 3 3 3 3 30 0 0 0 3 3 3 3 1112131415161718192021222324252627282930313233363738393435400 0 00 3 3 3 0 3 3 33 3 5 3 0 0 2 2 2 3 2 2 2 2 0 22 2 2 5 2 5 5 53 33 5 5西南东南西北东北 0 0 0 0 0 0 0 1 1 0 1 0 0 1 122位6位4位根节点对应整个图形。总共有四层结点，每个结点对应一根节点对应整个图形。总共有四层结点，每个结点对应一个象限，如个象限，如2 2层层4 4个结点分别对应于整个图形的四个象限，个结点分别对应

19、于整个图形的四个象限，排列次序依次为西南、东南、西北、东北，叶子结点可能排列次序依次为西南、东南、西北、东北，叶子结点可能落在不同的层上，该结点代表的子象限具有单一的代码，落在不同的层上，该结点代表的子象限具有单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形，从上到所有叶子结点所代表的方形区域覆盖了整个图形，从上到下，从左到右为叶子结点的编号如图所示，共有下，从左到右为叶子结点的编号如图所示，共有4040个叶子个叶子结点，也就是原图被划分为结点，也就是原图被划分为4040个大小不等的方形子区，个大小不等的方形子区，图中最下面的一排数字表示各子区的代码图中最下面的一排数字表示各子区的代码分

20、割的原则： 将图像区域划分成四个大小相同的象限，而每个象限又可根据一定的规则判断是否继续等分为次一层的四个象限，其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物或符合既定要求的少数几种地物时，则不能继续划分，否则一直划分到单个栅格像元为止。 5 5、四叉树编码、四叉树编码直接栅格编码：直接栅格编码：简单直观，是压缩编码方法的逻辑原型（栅格文件）；链码：链码：压缩效率较高，以接近矢量结构，对边界的运算比较方便，但不具有区域性质，区域运算较难；游程长度编码：游程长度编码：在很大程度上压缩数据，又最大限度的保留了原始栅格结构，编码解码十分容易，十分适合于微机地理信息系统采用；块码和四叉树

21、编码：块码和四叉树编码：具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图象运算，效率较高，是很有前途的编码方法。矢量模型的概述矢量结构通过记录坐标的方式尽可能精确地表示点、矢量结构通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体线、多边形等地理实体 ；点、线、面实体坐标编码一一个个点点的位置可以二维或者三维中的坐标的单一集合来描述。一一条条线线通常由有序的两个或者多个坐标对集合来表示。特定坐标之间线的路径可以是一个线性函数或者一个较高次的数学函数，而线本身可以由中间点的集合来确定。一一个个面面通常由一个边界来定义，而边界是由形成一个封闭的环状的一条

22、或多条线所组成。如果区域有个洞在其中，那么可以采用多个环以描述它。拓扑邻接： 元素之间的拓扑关系。拓扑关联： 元素之间的拓扑关系。拓扑包含： 元素之间的拓扑关系。1、地理空间数据的拓扑关系不不 同同 类类同同 类类同类不同级同类不同级N11256473P1P3P2P4N4N3N5N2拓扑邻接：N1/N2 ,N1/N3 ,N1/N4 ;P1/P3 ;P2/P3拓扑关联：N1/1、3 、6 ；P1/1、5 、6 拓扑包含：P3与P42.2.地理空间数据拓扑关系应用价值地理空间数据拓扑关系应用价值（1）确定地理实体间的相对空间位置，无需坐标和距离（2）利于空间要素查询（3）重建地理实体点点实体编码实

23、体编码比例朝向线指针线交汇编比例朝向字体文句x,y 坐标其它非几何属性建立和显示数据库联系的属性简单点符号文本点字符结 点符号统一标识类别或系列号点类型简单点文本点结 点线实体编码线实体编码唯一标示码唯一标示码线标示码线标示码起始点起始点终止点终止点坐标对序列坐标对序列显示信息显示信息非几何属性非几何属性多边形矢量编码多边形矢量编码多边形矢多边形矢量编码量编码树状索引编码法树状索引编码法拓扑结构编码法拓扑结构编码法由多边形边界的x,y坐标队集合及说明信息组成对所有边界点数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系形成完整的拓扑结构多边形矢量编码多边形矢量编

24、码123456789101112131415P1P2P3P1 x1，y1；x2，y2； x3，y3；x4，y4； x5，y5；x6，y6； x1，y1P2 x7，y7；x8，y8； x9，y9；x10，y10； x11，y11；x5，y5；x6，y6; x7，y7P3 x12，y12；x13，y13；x14，y14；x15，y15; x12，y12树状索引法树状索引法123456789101112131415P1P2P3 P1P3P2 1 2 3 4 5 6 5 6 5 6 7 8 9 1012 13 14 15 123456789101112131415P1P2P3点文件 点号 坐标 1 x

25、1，y1 2 x2，y2 15 x15，y15树状索引法树状索引法123456789101112131415P1P2P31 2 3 4 5 6 5 6 5 6 7 8 9 1012 13 14 15 线号 起点 终点 点号 6 5 6,1,2,3,4,5 5 6 5,6 6 5 6,7,8,9,10,11,5 12 13 12,15,14,13树状索引法树状索引法123456789101112131415P1P2P3多边形文件多边形号 边界线号 1 ， 2 ， 3 P1P3P2 树状索引法树状索引法拓扑结构编码法拓扑结构编码法唯一标示唯一标示多边形标示多边形标示外包多边形指针外包多边形指针邻接

26、多边形指针邻接多边形指针边界链接边界链接范围范围较好的解决了空间关系查询等问题，但增加了算法的复杂度矢量数据矢量数据结构构栅格数据格数据结构构数据存储量小数据存储量大空间位置精度高空间位置精度低用网络连接法能完整描述拓扑关系难于建立网络连接关系输出简单容易、绘图细腻、精确、美观输出速度快，但绘图粗糙、不美观可对图形及其属性进行检索、更新和综合便于面状数据处理数据结构复杂数据结构简单获取数据慢可快速获取大量数据数学模拟困难数学模拟方便多种地图叠合分析困难多种地图叠合分析方便不能直接处理数字图像信息能直接处理数字图像信息空间分析不容易实现空间分析易于进行边界复杂和模糊的事物难以描述容易描述边界复杂和模糊的事物数据输出的费用较高技术开发费用低思考题空间实体可抽象为哪几种基本类型？它们在矢量数据结构和栅格数据结构分别是如何表示的？叙述四种栅格数据存储的压缩编码方法。试写出矢量和栅格数据结构的模式，并列表比较其优缺点。叙述由矢量数据向栅格数据的转换的方法。叙述由栅格数据向矢量数据的转换的方法。简述栅格到矢量数据转换细化处理的两种基本方法。