《空间数据结构》PPT课件.ppt

1、第四章空间数据结构、数据结构即数据的组织形式是适用于校正机的存储、管理、处理的数据逻辑表现。 即，表示数据以什么样的形式被存储处理在修正计算机中。 空间数据结构是校正器中空间逻辑数据模型的组织关系和组织方法。 包括基于向量模型的向量数据结构、基于网格模型的网格数据结构、基于不规则镶嵌模型的三角网曲面数据结构等。 4.1向量数据结构、向量数据结构是对向量数据模型进行数据的组织，用记录坐标的方式尽可能准确地表现点、线、多边形等地理实体，使坐标空间连续，允许任意位置、长度和面积的精确定义。 其精度仅受数字化设备的精度和数值记录词长的限制。 矢量数据、矢量数据的类型、矢量结构允许以最小的数据冗馀存储最

2、复杂的数据，相对于网格结构数据精度高，数据存储的冗馀性小，是高效的空间数据结构。 分为物理数据结构和拓扑数据结构。 4.1.1实体数据结构、实体数据结构中，空间数据是按照基本空间对象(点、线或者多边形)为单位单独组织的，其中不包含拓扑关系信息，最典型地是所谓的意大利面结构，也称为坐标系列法。 经常采用这种数据结构的是，ArcGIS中的Shape文件和MapInfo的Tab文件等。 (第49页)、坐标系列法(Spaghetti方式)的例子、图形数据、10: x1，y1； x2、y2； x3、y3； x4、y4； x5、y5； x6、y6； x7、y7； x8、y8； x9、y9； x10、y10

3、； x11、y11； x1，y1。 20: x1、y1； x12、y12； x13、y13； x14、y14； x15、y15； x16、y16； x17、y17； x18、y18； x19、y19； x20、y20； x21、y21； x22、y22； x23、y23； x8、y8； x9、y9； x10、y10； x11、y11； x1，y1。 编码数据、坐标系列法的优缺点：文件结构简单，容易实现多边形单位的运算和显示缺点：对于连接的线，交叉点也需要对输入和存储重复的多边形的共同边重复输入和保存，产生数据冗馀和分析处理不方便的问题“岛”或“孔”只能构建为单个多边形，与周围的多边形没有建立关

4、系。 多边形的边界是否正确，也就是说很难检查多边形的完整性。各多边形是自成体系，关于近旁的信息不足，很难追踪拓扑关系，即邻接关系。 适用范围：图表和一般查询，不适合复杂空间分析的4.1.2拓扑编码法，具有拓扑关系的矢量数据结构是拓扑数据结构。 拓扑数据模型是一种基于向量的相对有效的数据模型，ArcGIS的Coverage是一种拓扑数据结构。 拓扑数据结构包括树索引编码方法、双重独立编码结构、链状双重独立编码结构等。 其本质是由地理实体间的空间关系表示的线和多边形。 中的组合图层性质变更选项。 基本概念，圆弧段：构成多边形的线段称为圆弧段，每个圆弧段可以有许多中点。 节点：两个或多个圆弧段的交点

5、称为节点岛。 由一个弧段组成的多边形称为孤岛或孔。 简单多边形：多边形图中不包含岛的多边形称为简单多边形。 复合多边形：包含岛的多边形称为复合多边形，包含作为边界和内边界，岛可以视为复合多边形的内边界。另外，一树索引编码方法(分层索引、索引式结构)采用树索引来减少数据的冗馀、间接地追加附近信息的方法将所有的边界点进行数字化，依次存储坐标对，并将点索引和边界号码相关联、线性索引树索引结构、树索引编码方法、图形数据树索引编码方法的例子、点和边界线之间的树索引、树索引编码方法的例子、创建的文档记录、索引式、线和多边形之间的树索引、点和多边形树索引编码能够消除相邻的多边形边界的数据的冗馀性和不一致，能

6、够通过对于多边形文件的划线处理得到过于复杂的边界线的附近信息和岛状信息，但是由于复杂，能够进行相邻函数的运算、不需要的边的消除、岛状信息的处理以及拓扑函数2 .双重独立编码结构，美国人口调查局于1980年设立的双重独立地图编码系统。 简称dime (dualindependentmapencoding )，该结构最适合城市地理信息系统。 行文件是双独立编码结构的基本对象。 线文件由线识别码、开始节点、结束节点、左多边形、右多边形构成，节点文件由节点识别码、节点坐标及与该节点连接的线的识别码等多边形文件由多边形的识别码和构成该多边形的线识别码构成。 多边形：多边形由一系列相互连接的线组成，由其内

7、部的唯一识别点来识别。 通过识别点的识别码和该多边形属性表的识别码一致，确立多边形空间信息和属性信息的关系。面拓扑、点拓扑、补充：使用双独立编码进行拓扑检查，从线文件中查找与当前编辑的多边形相关的所有记录。 若检查上述例子的P1，则首先在在线文件中找到关于P1的所有记录：基于双独立编码的拓扑检查，如果2.p1位于左(右)多边形的位置，则将其与位于右(左)多边形的位置的多边形编号交换的同时，该记录的节点编号位置也补充：基于双独立编码的拓扑检查从编码位置变换的记录开始，以任意起点节点为起点依次连接各节点，使各节点能够自己关闭，即N1 N2 N3 N1。 如果不能自动关闭，则表示发生记录缺失或多才多

8、艺，线路文件中存在错误。3 .链双独立编码结构，链双独立编码是对DIME数据结构的改进。 在DIME中，一条边只能由直线两端的编号和相邻的多边形表示，但在链数据结构中，多个直线段可以合并成一个圆弧段(或段)，每个圆弧段可以有多个中间点。 ARCGIS中的Coverage数据模型采用链双独立编码结构。 拓扑特征是，除了：个节点以外，每个空间对象都由更基本的对象组成。 实际上仅保存点的坐标，并且其它复杂空间对象中的坐标信息可以由逻辑组成。 复杂对象可以分解为一组节点及其拓扑关系的定义。 这将使存储在一个图层中的所有坐标信息成为节点的坐标，而只有对这些坐标的参照才能创建其他对象。 虽然构建拓扑需要额

9、外的存储数据，但坐标数据的存储没有数据冗馀的问题。 拓扑编码是部分空间分析的基础。 总结、矢量数据结构的特点：定位明确，属性隐含。 其定位直接基于坐标进行存储，不需要任何估计的属性通常存储在文件头或数据结构中的特定位置。由于该特点，矢量数据结构在图形运算的算法上总体上比栅格数据结构复杂，在叠加运算、邻域搜索等操作时困难或难以实现，但又具有方便独特的优点，在校正长度、面积、形状和图形编辑、几何变换操作中4.2网格数据结构、网格结构是最简单直接的空间数据结构，将地球表面划分为均匀大小的相邻网格排列，各网格作为像素或像素定义为行、列，并包含表示该像素的属性类型或量值的代码，或指向其属性记录的指针另外

10、，网格数据编码方法将直接网格编码(完全网格数据结构)压缩编码方法(压缩网格数据结构)链码行程码quad-tree2二维行程码、4.2.1直接网格编码、直接编码或网格数据视为1个数据矩阵一些典型的网格排列顺序，它们能够在记录代码的奇数行中从左向右记录，在偶数行中从右向左记录，或者为了特定的目的而采用其它特殊的顺序，4.2.2压缩编码方法，压缩编码的目的是以尽可能少的数据量记录尽可能多的信息该类型的有损信息编码3360在编码过程中能够通过无任何信息丢失的解码操作完全恢复原始信息的有损编码：提高了编码效率，最大程度地压缩了数据，因此在压缩过程中丢失了一些不重要的信息，使得该部分在解码时难以恢复，而地

11、理信息系统中的压缩编码是有损信息的。 链代码(Chain Codes )链代码也称为自由链代码(Freeman，1961 )或边界链代码。 此编码方法从一个原点开始，作为由一个基本方向决定的单位向量链表示数据。 例如，基本方向可以定义为东0、东南1、南2、西南3、西4、西北5、北6、东北7等8个基本方向。 另外，例如，若确定原点是像素(10，1 )，则某多边形的边界为顺时针方向的链代码： 10，1，7，0，0，7，1，7，0，0，2，其中，最初的两个数字10和1的起点是第10行的第1列，从第3个数字开始、练习、链码的优缺点：链码对多边形的表现具有较强的数据压缩能力，具有面积和周长的修正等一定的

12、运算功能，检测边界的急曲线和凹陷部分等比较容易，适合保存图形数据。 缺点：难以实施复盖运算(例如组合、交叉等)，局部修改将改变整体结构，效率低，并且链码按区域存储边界，因此如果相邻区域的公共边界重复存储，则变得冗馀。 另外，行程长度编码的基本方式是通常对于一个网格图像在行(或列)方向上相邻的若干点具有相同的属性码，并且它们的重复记录内容可以按某种方式压缩。 游程长度是指在网格矩阵内相邻的等值网格的数量。 另外，作为行程长度编码(Run-Length Codes )的实现方法，有仅在各行(或列)的数据的代码发生了变化时，依次记录与该代码相同的代码的重复个数，从而实现数据压缩的两种编码方式。另一种

13、游程长度编码方式根据各行(或列)的符号变化的位置和与其对应的符号、游程长度编码例、第一编码方式(左上角坐标、行方向)，进行该数据游程长度编码： (0，1 )、(4，2 (4，5 )、(7，3 )； (4，4 )、(8，2 )、(7，2 )、(0，2 )、(4，1 )、(8，3 )、(7，2 )、(0，2 )、(8，4 )、(7，1 )、(8，1 )、(0，3 )、(8，5 )； (0，4 )，(8，4 )； (0，5 )，(8，3 )。 原始数据中的64个网格用44个整数表现。 游程长度编码的示例、(1，0 )、(2，4 )、(4，0 )； 一，四，四，零； 一，四，五，八，六，零； (1，7

14、 )、(2，4 )、(4，8 )、(7，0 )、(1，7 )、(2，4 )、(3，8 )、(8，0 )、(1，7 )、(3，8 )； 一、七、六、八； 一，七，五，八。 在第二种编码方法中，记录与各行(或列)的代码变化的位置对应的代码的该数据的行程长度编码(左上角坐标、列方向):行程长度编码能否压缩数据量主要取决于光栅数据的性质，通常通过事先测试来推定数据冗馀度mn表达式中： q表示邻近属性值的改变的总和，m表示行数n表示列数，其中Re大于1/5时，表示栅格数据能够被压缩的显着效果，其压缩效果可以用压缩比表示： S=mn/K表达式中： k表示行程行程编码的长度而且，复杂的编码、解码运算必须避免

15、处理和操作时间的增加的缺点是，图斑破碎、属性和边界变化的数据压缩效率低、压缩后的数据量也大。 另外，块码的块码是行程码二维扩展的情况，采用方形区域作为记录单位，各记录单位包括相邻的多个网格，数据结构由初始位置(行、列编号)和半径、记录单位的码构成。 分块代码编码的例子，其块代码可以被编码为(1，1，1，0 )、(1，2，2，4 )、(1，4，1，7 )、(1)、(3，4，1，4 )、(3，5，2，8 )、(3，7，2，7 )、(4，1，2，2 ) 四叉树代码。 基本的分割方法是将一个格点地图或图像等分为四个部分。 逐块检查网格属性值(或灰度)。 子区域中的所有网格值都具有相同的值。 此次区域将

16、不再继续分割。 否则，必须将该次区域进一步划分为4个次区域。 这样，依次分割各子块，直到只包含相同的属性值或灰度。四叉树编码的例子、四叉树编码的要求、在采用四叉树编码的情况下，为了四叉树分解持续进行，图像必须是2 n-2 n的网格阵列，对于非标准尺寸的图像，首先通过追加背景，将图像缩小为2 生成四叉树的方法主要有两种：“自上而下”(top-down )和“自下而上”(bottton-up )。 自上而下的方法运算量多，很费时间。 因此，您实际上可以使用从下到上的方法创建四叉树代码。 按Morton代码的顺序检测网格数据：如果相邻的4个网格值相同，则进行合并，逐次向上递归合并，直到遵循四叉树原则为止。 该方法反复修正算少，运算速度快。、四叉树的生成、四叉树结构的编码方式、四叉树结构根据其编码方式分为通常的四叉树和线性四叉树：除了通常的四叉树：