第三章空间数据结构.ppt

《第三章空间数据结构.ppt》由会员分享，可在线阅读，更多相关《第三章空间数据结构.ppt（44页珍藏版）》请在三一文库上搜索。

1、2019/4/5,西北大学城市与资源学系 谢元礼,1,第三章 空间数据结构,2019/4/5,西北大学城市与资源学系 谢元礼,2,数据结构即指数据组织的形式，是适合于计算机存储、管理和处理的数据逻辑结构。对空间数据则是地理实体的空间排列方式和相互关系的抽象描述。 在地理系统中描述地理要素和地理现象的空间数据，主要包括空间位置、拓朴关系和属性三个方面的内容。,2019/4/5,西北大学城市与资源学系 谢元礼,3,空间数据结构 网格数据结构(显式表示 ) 矢量数据结构(隐式表示 ),2019/4/5,西北大学城市与资源学系 谢元礼,4,显式描述,显式表示：就是栅格中的一系列像元(点)，为使计算机认

2、识这些像元描述的是某一物体而不是其它物体。 注：“c”不一定用c的形式，而可以用颜色、符号、数字、灰度值来显示。 则得到椅子的简单数据结构为： 椅子的属性符号颜色像元x,2019/4/5,西北大学城市与资源学系 谢元礼,5,隐式表示,隐式表示：由一系列定义了始点和终点的线及某种连接关系来描述，线的始点和终点坐标定义为一条表示椅子形式的矢量，线之间的指示字，告诉计算机怎样把这些矢量连接在一起形成椅子，隐式表示的数据为： 椅子的属性一系列矢量连接关系,2019/4/5,西北大学城市与资源学系 谢元礼,6,栅格数据结构,栅格数据:栅格数据结构实际就是像元阵列，每个像元由行列确定它的位置。由于栅格结构

3、是按一定的规则排列的，所表示的实体位置很容易隐含在网络文件的存储结构中，且行列坐标可以很容易地转为其它坐标系下的坐标。在网络文件中每个代码本身明确地代表了实体的属性或属性的编码。 栅格数据结构就是像元阵列，每个像元的行列号确定位置，用像元值表示空间对象的类型、等级等特征。 每个栅格单元只能存在一个值。,2019/4/5,西北大学城市与资源学系 谢元礼,7,点,线,面,对于栅格数据结构 点：为一个像元 线：在一定方向上连接成串的相邻像元集合。 面：聚集在一起的相邻像元集合。,2019/4/5,西北大学城市与资源学系 谢元礼,8,栅格数据结构：坐标系与描述参数,Y：列,X：行,西南角格网坐标 （X

4、WS，YWS）,格网分辨率,2019/4/5,西北大学城市与资源学系 谢元礼,9,栅格数据单元值确定,百分比法,面 积 占 优,重 要 性,中心点法,A 连续分布地理要素,C 具有特殊意义 的较小地物,A 分类较细、 地物斑块较小,AB,为了逼近原始数据精度，除了采用这几种取值方法外，还可以采用缩小单个栅格单元的面积，增加栅格单元总数的方法,2019/4/5,西北大学城市与资源学系 谢元礼,10,栅格数据压缩存储的编码方法,起点行列号，单位矢量 R: (1,5),3,2,2,3,3,2,3,链式编码,游程长度编码,逐行编码 数据结构: 行号, 属性, 重复次数 1, A, 4, R, 1, A

5、, 4,块状编码,正方形区域为记录单元 数据结构: 初始位置, 半径, 属性 (1,1,3,A),(1,5,1,R),(1,6,2,A),四叉树编码,2019/4/5,西北大学城市与资源学系 谢元礼,11,栅格矩阵（Raster Matrix),Raster数据是二维表面上地理数据的离散量化值，每一层的pixel值组成像元阵列（即二维数组），其中行、列号表示它的位置。 例如影像： A A A A A B B B A A B B A A A B 在计算机内是一个4*4阶的矩阵。但在外部设备上，通常是以左上角开始逐行逐列存贮。如上例存贮顺序为：A A A A A B B B A A B B A A

6、 A B 当每个像元都有唯一一个属性值时，一层内的编码就需要m行n列3(x,y和属性编码值)个存储单元。数字地面模型就属此种情况。,2019/4/5,西北大学城市与资源学系 谢元礼,12,链式编码(ChainCodes),又称为弗里曼链码(Freeman)或边界链码。 基本方向可定义为：东0，东南l，南二2，西南3，西4，西北5，北6，东北7等八个基本方向。如果再 确定原点为像元(10，1)，则该多边形边界按顺时针方向的链式编码为： 10，l，7，0，1，0，7，1，7，0，0，2，3，2，2，1，0，7，0，0，0，0，2，4，3，4，4，3，4，4，5，4，5，4，5，4，5，4，6，6。

7、,2019/4/5,西北大学城市与资源学系 谢元礼,13,游程长度编码(RunLengthCodes),游程长度编码是按行帧序存储多边形内的各个像元的列号，即在某行上从左至右存储属该多边形的始末像元的列号。 问：对左图的进行游程长度编码 。,2019/4/5,西北大学城市与资源学系 谢元礼,14,块式编码(BlockCodes),块式编码是将游程长度编码扩大到二维的情况，把多边形范围划分成由像元组成的正方形，然后对各个正方形进行编码。如图：,块式编码的数据结构由初始位置(行号，列号)和半径，再加上记录单元的代码组成。根据这一编码原则，上述多边形只需17个单位正方形。9个4单位的正方形和1个16

8、单位的正方形就能完整表示，总共要57个数据，其中27对坐标，3个块的半径。,2019/4/5,西北大学城市与资源学系 谢元礼,15,四叉树编码(Quadtree Encoding),四叉树编码又称为四分树、四元树编码。它是一种更有效地压编数据的方法。它将2n2n像元阵列连续进行4等分，一直分到正方形的大小正好与象元的大小相等为止（如下图），而块状结构则用四叉树描述，习惯上称为四叉树编码。,2019/4/5,西北大学城市与资源学系 谢元礼,16,八叉树编码,八叉树结构就是将空间区域不断地分解为八个同样大小的子区域(即将一个六面的立方体再分解为八个相同大小的小立方体)，同区域的属性相同。八叉树主要

9、用来解决地理信息系统中的三维问题。,2019/4/5,西北大学城市与资源学系 谢元礼,17,栅格数据组织,2019/4/5,西北大学城市与资源学系 谢元礼,18,栅格数据组织,2019/4/5,西北大学城市与资源学系 谢元礼,19,栅格数据结构特点,离散的量化栅格值表示空间对象 位置隐含,属性明显 数据结构简单,易于遥感数据结合,但数据量大 几何和属性偏差 面向位置的数据结构,难以建立空间对象之间的关系,2019/4/5,西北大学城市与资源学系 谢元礼,20,几何偏差,属性偏差,如以像元边线计算则为7，以像元为单金大会则为4。 三角形的面积为6个平方单位，而右图中则为7个平方单位，这种误差随像

10、元的增大而增加。,2019/4/5,西北大学城市与资源学系 谢元礼,21,矢量数据结构,矢量数据结构是通过记录坐标的方式，尽可能地将点、线、面地理实体表现得精确无误。其坐标空间假定为连续空间，不必象栅格数据结构那样进行量化处理。因此矢量数据能更精确地定义位置、长度和大小。 除数学上的精确坐标假设外，矢量数据存储是以隐式关系以最小的存储空间存储复杂的数据。,2019/4/5,西北大学城市与资源学系 谢元礼,22,矢量数据结构编码的基本内容,矢量数据结构通过记录空间对象的坐标及空间关系来表达空间对象的位置。 点：空间的一个坐标点； 线：多个点组成的弧段； 面：多个弧段组成的封闭多边形；,2019/

11、4/5,西北大学城市与资源学系 谢元礼,23,矢量数据结构编码的基本内容,标识码,属性码,空间对象编码 唯一 连接空间和属性数据,数据库,独立编码,点: ( x ,y ) 线: ( x1 , y1 ) , (x2 , y2 ) , , ( xn , yn ) 面: ( x1 , y1 ) , (x2 , y2 ) , , ( x1 , y1 ),点位字典,点: 点号文件,线: 点号串,面: 点号串,存储方法,2019/4/5,西北大学城市与资源学系 谢元礼,24,点实体,2019/4/5,西北大学城市与资源学系 谢元礼,25,线实体,面实体,多边形矢量编码，不但要表示位置和属性，更重要的是能表

12、达区域的拓扑特征，如形状、邻域和层次结构等，以便使这些基本的空间单元可以作为专题图的资料进行显示和操作。,2019/4/5,西北大学城市与资源学系 谢元礼,26,简单的矢量数据结构面条结构（实体式） 只记录空间对象的位置坐标和属性信息，不记录拓扑关系。 存储： 独立存储：空间对象位置直接跟随空间对象； 点位字典：点坐标独立存储，线、面由点号组成 特征 无拓扑关系，主要用于显示、输出及一般查询 公共边重复存储，存在数据冗余，难以保证数据独立性和一致性 多边形分解和合并不易进行，邻域处理较复杂； 处理嵌套多边形比较麻烦 适用范围： 制图及一般查询，不适合复杂的空间分析,2019/4/5,西北大学城

13、市与资源学系 谢元礼,27,简单的矢量数据结构面条结构（实体式）,多边形 数据项 A (x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5),(x6,y6),(x7,y7),(x8,y8),(x9,y9),(x1,y1) B (x1,y1), (x9,y9), (x8,y8), (x17,y17), (x16,y16), (x15,y15),(x14,y14) ,(x13,y13), (x12,y12), (x11,y11),(x10,y10),(x1,y1) C (x24,y24),(x25,y25),(x26,y26),(x27,y27),(x28,y28),(x2

14、9,y29),(x30,y30) ,(x31,y31), (x24,y24) D (x19,y19),(x20,y20),(x21,y21),(x22,y22),(x23,y23),(x15,y15),(x16,y16) ,(x19,y19) E (x5,y5),(x18,y18),(x19,y19),(x16,y16),(x17,y17),(x8,y8),(x7,y7) ,(x6,y6), (x5,y5),2019/4/5,西北大学城市与资源学系 谢元礼,28,索引式,线与多边形之间的树状索引,点与多边形之间的树状索引,2019/4/5,西北大学城市与资源学系 谢元礼,29,双重独立式DIM

15、E(Dual lndependent Map Encoding),这种数据结构除了通过线文件生成面文件外，还需要点文件,2019/4/5,西北大学城市与资源学系 谢元礼,30,链状双重独立式,链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。 在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。,2019/4/5,西北大学城市与资源学系 谢元礼,31,弧段文件 弧段号 起始点 终结点 左多边形 右多边形 a 5 1

16、 O A b 8 5 E A c 16 8 E B d 19 5 O E e 15 19 O D f 15 16 D B g 1 15 O B h 8 1 A B i 16 19 D E j 31 31 B C 弧段坐标文件 弧段号 点 号 a 5,4,3,2,1 b 8,7,6,5 c 16,17,8 d 19,18,5 e 15,23,22,21,20,19 f 15,16, g 1,10,11,12,13,14,15 h 8,9,1 i 16,19 j 31,30,29,28,27,26,25,24,31,链状双重独立式,多边形文件 多边形号 弧段号 周长 面积 中心点坐标 A h,b,

17、a B g,f,c,h,-j C j D e,i,f E e,i,d,b,2019/4/5,西北大学城市与资源学系 谢元礼,32,矢量数据结构的属性数据表达,属性特征类型 类别特征：是什么 说明信息：同类目标的不同特征 属性特征表达 类别特征：类型编码 说明信息：属性数据结构和表格 属性表的内容取决于用户 图形数据和属性数据的连接通过目标识别符或内部记 录号实现。,2019/4/5,西北大学城市与资源学系 谢元礼,33,矢量数据结构的属性数据表达,2019/4/5,西北大学城市与资源学系 谢元礼,34,矢量数据结构的特点,用离散的点描述空间对象与特征，定位明显，属性隐含 用拓扑关系描述空间对象

18、之间的关系 面向目标操作，精度高，数据冗余度小 与遥感等图象数据难以结合 输出图形质量号，精度高,2019/4/5,西北大学城市与资源学系 谢元礼,35,第三节 两种数据结构的比较与转换,2019/4/5,西北大学城市与资源学系 谢元礼,36,数据结构选择原则,要素还是位置？ 可获取的数据 定位要素的必要精度 需要什么类型的要素 需要什么类型的拓扑关联 所需空间分析类型 生产地图类型,2019/4/5,西北大学城市与资源学系 谢元礼,37,矢量数据向栅格数据转换,点的变换,2019/4/5,西北大学城市与资源学系 谢元礼,38,矢量数据向栅格数据转换,矢量线段的变换,2019/4/5,西北大学

19、城市与资源学系 谢元礼,39,矢量数据向栅格数据转换,多边形数据的转换 (边界代数算法、内部点扩散法、射线算法）,2019/4/5,西北大学城市与资源学系 谢元礼,40,矢量数据向栅格数据转换,边界代数算法,2019/4/5,西北大学城市与资源学系 谢元礼,41,栅格数据向矢量数据转换,二值化,2019/4/5,西北大学城市与资源学系 谢元礼,42,栅格数据向矢量数据转换,细化（剥皮法、骨架法）,2019/4/5,西北大学城市与资源学系 谢元礼,43,栅格数据向矢量数据转换,跟踪,2019/4/5,西北大学城市与资源学系 谢元礼,44,思考与练习,空间实体可抽象为哪几种基本类型？它们在矢量数据结构和栅格数据结构分别是如何表示的？ 叙述四种栅格数据存储的压缩编码方法。 试写出矢量和栅格数据结构的模式，并列表比较其优缺点。 叙述由矢量数据向栅格数据的转换的方法。 叙述由栅格数据向矢量数据的转换的方法。 简述栅格到矢量数据转换细化处理的两种基本方法。,