(第三章)空间数据结构.ppt

第三章 空间数据结构,本章学习目标,掌握空间数据的计算机表示方法；了解空间数据结构的类型；掌握空间数据结构的建立。,空间数据的计算机表示指通过利用确定的数据结构和数据模型来表达空间对象的空间位置、拓扑关系和属性信息。,空间数据的计算机表示,空间数据结构的建立,系统功能与数据间的关系现代地理信息系统数据模式的一个重要特征是数据与功能之间具有密切的联系(见下表)，因此，在确定数据内容时，首先必须明确系统的功能；对开发的GIS系统的功能，是通过用户需求调查来确定的，因此，在开发GIS系统之前，首先要进行系统分析。空间数据的分类和编码,空间数据的分类，是指根据系统功能及国家规范和标准，将具有不同属性或特征的要素区别开来的过程，以便从逻辑上将空间数据组织为不同的信息层。,系统功能与数据间的关系(据Jack Dangermond等),信息层示意图,空间数据结构的建立,空间数据的编码：是指将数据分类的结果，用一种易于被计算机和人识别的符号系统表示出来的过程，编码的结果是形成代码。代码由数字或字符组成。例如，我国基础地理信息数据的分类代码由六位数字组成，其代码结构如下所示：大类码 小类码 一级代码 二级代码 识别位大类码、小类码、一级代码和二级代码分别用数字顺序排列。识别位由用户自行定义，以便于扩充。,空间数据结构的建立,国土基础信息数据分类与代码举例,矢量数据的输入与编辑矢量数据的输入，是指将分类和编码的空间对象图形转换为一系列x、y坐标，然后按照确定的数据结构加入到线段或标示点的计算机数据文件中去；空间数据编辑的目的是为了消除数字化过程中引入的各类错误和对数据进行拓扑关系检查等而进行的操作。栅格数据的输入与编辑栅格数据的输入方法包括透明格网采集输入、扫描数字化输入及其它数据传输或转换输入等；,空间数据结构的建立,栅格数据编辑的目的同样是为了消除数字化过程中引入的各类错误，根据栅格数据结构的特点，其编辑的内容还包括数据压缩和数据组织方式的变换等,如下图。,空间数据的不同组织方式,空间数据结构的建立,本章学习内容,栅格数据结构简单栅格数据结构。栅格数据的压缩编码方式：链式编码、游程长度编码、块状编码、四叉树编码。矢量数据结构矢量数据结构编码的基本内容：点实体、线实体、面实体。矢量数据结构编码的方法：实体式、索引式、双重独立式、链状双重独立式。两种数据结构的比较与转化两种数据结构的比较。矢量数据结构向栅格数据结构的转换。栅格数据结构向矢量数据结构的转换。,在栅格数据结构中，整个地理空间被规则地分为一个个小块（通常为正方形），地理实体的位置是由占据小块的横排与竖列的位置决定，小块的位置则由其横排竖列的数码决定，每个地理实体的形态是由栅格或网格中的一组点来构成。然后在各个格网单元内赋以空间对象相应的属性值的一种数据组织方式。这种数据结构和遥感图象的数据相同，因而数字遥感 图象就是栅格数据结构。,栅格数据结构,矢量结构,栅格结构,栅格数据结构,现实世界,网格,点,线,面积,数值,=0=1=2=3,行,列,三角形,六边形,栅格,栅格数据结构,關於衛星影像,栅格数据结构,關於衛星影像,栅格数据的取值(混合像元的处理),栅格数据是用阵列方式表示数据特征的。阵列中每个元素的数据值表示属性，而位置关系隐含在行列之中，这些行列值实际上是表示了地物的空间位置。栅格数据的这种表示亦称网格(格网)编码。这种编码方法同遥感图象的编码相一致，其中每个栅格(象素、元素)只能取一个值。而实际上，一个栅格可能对应于实体中几种不同属性值，这时就有如何对栅格取值的问题?,關於衛星影像,栅格数据的取值(混合像元的处理),面积占优法,面积占优法是把栅格中占有最大面积的属性值定为本栅格元素的值。,下图所示的栅格结构用面积占优法得编码方案为：,關於衛星影像,栅格数据的取值(混合像元的处理),中心点法,中心点法是将栅格中心点的值作为本栅格元素的值。,下图所示的栅格结构用中心点法得编码方案为：,關於衛星影像,栅格数据的取值(混合像元的处理),长度占优法,长度占优法是将网格中心画一横线，然后用横线所占最长部分的属性值作为本栅格元素的值。,下图所示的栅格结构用长度占优法得编码方案为：,關於衛星影像,栅格数据的取值(混合像元的处理),重要性法,重要性法往往突出某些主要属性，对于这些属性，只要在栅格中出现，就把该属性作为本栅格元素的值，在下图中假设D属性具有特殊的重要性，,下图所示的栅格结构用重要性法得编码方案为：,在重要性法中，只要该栅格中含有某特殊重要性的属性，不管所占比例大小，便认为该栅格属于该属性。,關於衛星影像,栅格数据的取值(混合像元的处理),栅格数据的上述取值方法，不论采用哪一种都会带来一定的误差。为了逼近原始数据，提高精度，除了采用这几种取值方法外，还可以采用缩小单个栅格单元的面积，增加栅格单元总数的方法，但同时使数据量大幅度增加。,空间数据的编码,空间数据编码，是根据GIS的目的和任务，把地图、图像等资料按一定数据结构转化为适于计算机存贮和处理的数据过程。,空间数据的编码是地理信息系统设计中最重要的技术步骤，它表现由现实世界到数据世界之间的接口，是联接从现实世界到数据世界的纽带。,为什么要进行编码？,编码对象：属性数据编码方法：层次分类编码 多源分类编码编码标准化,空间数据的编码,电线架715,管线:7,地下电力线与电缆72,电力线71,地下检修井74,输水管线73,低压712,电杆713,电塔714,不依比例7142,依比例7141,空间对象的层次分类编码,分类对象的从属和层次关系有明确的分类对象类别和严格的隶属关系,高压711,空间对象的多源分类编码,按空间对象不同特性进行分类并进编码代码之间没有隶属关系，反映对象特性具有较大的信息量，有利于空间分析,编码的标准化,栅格数据结构类型,栅格数据结构分为栅格矩阵结构、游程编码结构、四叉树数据结构、八叉树数据结构和十六叉树数据结构,栅格矩阵结构：一种全栅格阵列的空间数据组织形式。逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。,代表44阶的矩阵，如果矩阵的每个元素用一个双字节表示，则一个图层的全栅格数据所需要的存储空间为m行n列2字节。以一个面积为100km2的区域为例，如果网格变长取为1m，每个网格用一个双字节表示，则一个图层的要素就要占用200M字节的存储空间，对一张图形或一幅图像来说，这是一个相当大的存储容量，而且随着空间分辨率的提高，存储空间成几何级数递增，因此，栅格数据的压缩是栅格数据结构要解决的重要问题。,栅格数据结构,栅格数据结构类型,链码结构,链码又称弗里曼链码（Freeman）或边界链码，它将线状地物或区域边界，由起点和一系列在基本方向上的单位矢量给出每个后续点相对应其前继点的可能的8个基本方向之一表示，单位矢量的长度默认为一个栅格像元。,链码的表示方法,链码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适宜存贮图形数据。缺点是对边界合并、插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率低下，而且由于链码以每个区域为单位存贮边界，相邻区域的边界将被重复存贮而产生冗余。,栅格数据结构,栅格数据结构类型,游程编码结构,在栅格结构中，点用一个栅格单元表示；线状地物沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元在线上；面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。,点,线,面,栅格数据结构,栅格数据结构类型,游程编码结构,游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。其方法有两种方案：一种编码方案是，只在各行（或列）数据的代码发生变化时依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。例如对图所示栅格数据，可沿行方向进行如下游程长度编码：,（0，1），（4，2），（7，5）；（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)。,只用了44个整数就可以表示，而在前述的直接编码中却须要64个整数表示，可见游程长度编码压缩数据是十分有效又简便的。事实上，压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高。,栅格数据结构,栅格数据结构类型,游程编码结构,逐个记录各行（或列）代码发生变化的位置（行数）和相应代码。例如对图所示栅格数据，可沿列方向进行如下游程长度编码：,（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）。,栅格数据结构,（属性值发生变化的行号，属性值）,栅格数据结构类型,游程编码结构,游程终止编码：（栅格元素的属性值，游程的终止列号）,(0,1)(4,3)(7,8)(4,5)(7,8)(4,4)(8,6)(7,8)(0,2)(4,3)(8,6)(7,8)(0,2)(8,6)(7,7)(8,8)(0,3)(8,8)(0,4)(8,8)(0,5)(8,8),栅格数据结构,游程长度编码的优缺点,栅格数据结构,压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高。游程长度编码在栅格加密时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存贮容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。,游程编码结构练习题,栅格数据结构,沿行方向进行如下游程长度编码,沿列方向进行如下游程长度编码,游程终止编码：（栅格元素的属性值，游程的终止列号）,栅格数据结构类型,块码结构,块码是游程长度编码扩展到二维的情况，采用方形区域作为纪录单元每个记录单元包括相邻的若干栅格，数据编码由初始位置行列号加上半径，再加上记录单元的代码组成。,块码分解图,（1，1，1，0），（1，2，2，2），（1，4，1，5），（1，5，1，5），（1，6，2，5），（1，8，1，5），（2，1，1，2），（2，4，1，2），（2，5，1，2），（2，8，1，5），（3，1，1，2），（3，2，1，2），（3，3，1，2），（3，4，1，2），（3，5，2，3），（3，7，2，5）；（4，1，2，0），（4，3，1，2），（4，4，1，3），（5，3，1，3），（5，4，2，3），（5，6，1，3），（5，7，1，5），（5，8，1，3）；（6，1，3，0），（6，6，3，3），（7，4，1，0），（7，5，1，3）；（8，4，1，0），（8，5，1，0）。,块码表示如下,栅格数据结构,块状编码的优缺点,栅格数据结构,一个多边形所包含的正方形越大，多边形的边界越简单，块状编码的效率就越好。块状编码对大而简单的多边形更为有效，而对那些碎部较多的复杂多边形效果并不好。块状编码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而对某些运算不适应，必须在转换成简单数据形式才能顺利进行。,栅格数据结构类型,四叉树数据结构,四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法之一，绝大部分图形操作和运算都可以直接在四叉树结构上实现，因此四叉树编码既压缩了数据量，又可大大提高图形操作的效率。四叉树将整个图像区逐步分解为一系列被单一类型区域内含的方形区域，最小的方形区域为一个栅格象元，分割的原则是，将图像区域划分为四个大小相同的象限，而每个象限又可根据一定规则判断是否继续等分为次一层的四个象限，其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物或符合既定要求的少数几种地物时，则不再继续划分，否则一直划分到单个栅格象元为止。四叉树通过树状结构记录这种划分，并通过这种四叉树状结构实现查询、修改、量算等操作。,栅格数据结构,栅格数据结构类型,四叉树数据结构,各子象限尺度大小不完全一样，但都是同代码栅格单元，其四叉树如下图,栅格数据结构,栅格数据结构类型,四叉树数据结构,其中最上面的那个结点叫做根结点，它对应整个图形。总共有4层结点，每个结点对应一个象限，如2层4个结点分别对应于整个图形的四个象限，排列次序依次为南西（SW）、南东（SE）、北西（NW）和北东（NE），不能再分的结点称为终止结点（又称叶结点），可能落在不同的层上，该结点代表的子象限具有单一的代码，所有终止结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶结点编号如右图所示，共有40个叶结点，也就是原图被划分为40个大小不等的方形子区，右图最下面的一排数字表示各子区的代码。,栅格数据结构,四叉树数据结构,栅格数据结构,自上往下(Top-to-Down)的常规四叉树：四叉树分割的基本思想是首先把一幅图象或一幅栅格地图(2n2n，n1)等分成4部分，逐块检查其栅格值，若每个子区中所有栅格都含有相同值，则该子区不再往下分割；否则，将该区域再分割成4个子区域，如此递归地分割，直到每个子块都含有相同的灰度或属性值为止。这样的数据组织称为自上往下(Top-to-Down)的常规四叉树。四叉树也可自下而上(Down-to-Top)的建立。这时，从底层开始对每个栅格数据的值进行检测，对具有相同灰度或属性的四等分的子区进行合并，如此递归向上合并。,重复四叉树数据结构的理解,栅格数据结构,对2323的栅格图，利用自上而下方法表示寻找栅格A的过程。从四叉树的特点可知，一幅2N2N栅格阵列图，具有的最大深度数为N，可能具有的层次为0，1，2，3，N。每层的栅格宽度，即为每层边长上包含的最大栅格数，反映了所在叶结点表示的正方形集合的大小。其值为：2(最大深度-当前层次)例如：一幅2323的栅格阵列，它具有最大深度为3，可能层次分别为0，1，2，3。其中：第0层边长上的最大栅格数为23-0=8；第1层边长上的最大栅格数为23-1=4；第2层边长上的最大栅格数为23-2=2；第3层边长上的最大栅格数为23-3=1。当栅格阵列为非2N2N时，为了便于进行四叉树编码可适当增加一部分零使其满足2N2N。,常规四叉树,常规四叉树,栅格数据结构,常规四叉树的分解过程,线性四叉树,栅格数据结构,常规四叉树所占的内外存空间比较大，因为它不仅要记录每个结点值，还需记录结点的一个前趋结点及四个后继结点，以反映结点之间联系。对栅格数据进行运算时，还要作便利树结点的运算。这样，增加了操作的复杂性。所以实际上，在地理信息系统或图象分割中不采用常规四叉树，而用线性四叉树(Linear Quadtree)。,从数据结构角度看，树数据结构本身属于非线性数据结构。这里所说的线性四叉树编码是指用四叉树的方式组织数据，但并不以四叉树方式存储数据。也就是说，它不像常规四叉树那样存储树中各个结点及其相互间关系，而是通过编码四叉树的叶结点来表示数据块的层次和空间关系。因此，叶结点都具有一个反映位置的关键字，亦称位置码，以此表示它所处位置。其实质是把原来大小相等的栅格集合转变成大小不等的正方形集合，并对不同尺寸和位置的正方形集合赋予一个位置码。,线性四叉树,栅格数据结构,下面的栅格数据图，其中属性值为1，背景值为0。该图的线性四叉树表示可通过19个叶结点来描述。图中叶结点(1)到(19)分别表示不同尺寸的正方形集合。所以，线性四叉树的关键是如何对叶结点进行编码，通常说的各种四叉树编码法的差异，主要在于表示位置码的编码方法不同。,1,1,区域的栅格表示,区域的线性四叉树表示,线性四叉树,栅格数据结构,线性四叉树,栅格数据结构,第一次分割得第一层，这里用P0，P1，P2，P3表示如下：,2,线性四叉树,栅格数据结构,第二次分割得第二层，这里用P00，P01，P02，P03，P10，P11，P12，P13，P20，P22，P23；P30，P31，P32，P33表示如下：,P00,P01,P02,P03,P33,P11,P10,线性四叉树,栅格数据结构,其中位置码的位数决定分割的层数，图形越复杂，分割的层数越多，相应的位置码的位数亦越多。这种自上而下的分割方法需要大量重复运算，效率比较低，从而出现了自下而上的合并法。自下而上的合并法，首先根据栅格阵列的行列值转换成最大位数的位置码，然后对上述编码进行排序，依次检查4个相邻位置码的属性值是否相同，若相同将其进行合并，并除去一位最低位置码，这样不断循环直到没有可合并子块为止。这种自下而上合并法，因效率高得以采用。,四叉树编码的优点,栅格数据结构,容易而有效地计算多边形的数量特征；阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；多边形中嵌套异类小多边形的表示较方便。,四叉树编码的缺点,栅格数据结构,四叉树编码的最大缺点是转换的不定性，用同一形状和大小的多边形可能得出多种不同的四叉树结构，故不利于形状分析和模式识别。但因它允许多边形中嵌套多边形即所谓“洞”这种结构存在，使越来越多的地理信息系统工作者都对四叉树结构很感兴趣。,矢量数据结构,矢量数据结构是利用欧几里得几何学中的点、线、面及其组合体来表示地理实体空间分布的一种数据组织方式；矢量数据结构分为简单数据结构（也称面条数据结构）、拓扑数据结构和曲面数据结构；拓扑数据结构最重要的技术特征和贡献是具有拓扑编辑功能，包括多边形连接编辑和结点连接编辑。,1、简单数据结构,如采用坐标系列编码。点目标（x,y)线目标(x1y1,x2y2,.xnyn)面目标(x1y1,x2y2,.xnyn,x1y1)具体实现形式可将点，线，面直接用空间坐标点数据表示；也可将坐标点组成文件，每个点给予一个点号，而点，线，面用点号数据表示。,矢量数据结构,无拓扑关系的矢量模型实质上是面向实体的一种数据模型。它以单个的空间实体为数据组织和存储的基本单位。它采用面向对象的软件开发方式，每个对象有自己的特性、自己的行为。只记录空间目标的位置坐标和属性信息，不记录空间拓扑关系。,1、简单数据结构,无拓扑关系的矢量模型优缺点：优点：（1）数据结构简单，直观，便于用户接受；（2）便于系统的维护和更新。缺点：（1）数据余度大，如多边形公共边重复存储，但没有存储多边形之间的关系。相邻多边形易产生伪多边形。解决的办法是建立多边形边界表；（2）缺乏拓扑信息，如邻域信息等，不便于拓扑分析（临时建立拓扑关系）；（3）对岛处理能力差，无法建立外多边形的关系。,矢量数据结构,矢量结构图形基本元素,2、拓扑数据举例,矢量数据结构,拓扑数据结构的弧段文件构成,矢量数据结构,3、曲面数据结构,矢量数据结构,曲面是指连续分布现象的覆盖表面，采用不规则三角网来拟合连续分布现象的覆盖表面，称为TIN(Triangulated Irregular Network)数据结构。基于TIN的曲面数据结构，通常用于数字地形的表示，或者按照曲面要素的实测点分布，将它们连成三角网，三角网中的每个三角形要求尽量接近等边形状，并保证由最邻近的点构成的三角形，即三角形的边长之和最小。在所有可能的三角网中，狄洛尼(Delaunay)三角网在地形拟合方面表现最为出色，因此常被用于TIN的生成。,3、曲面数据结构,矢量数据结构,不规则三角网及其数据组织,利用这种数据结构，可以方便地进行地形分析，如坡度和坡向信息提取，填挖方计算，阴影和地形通视分析，等高线自动生成等。因此，TIN数据结构被广泛应用于各种地理信息系统。,矢量数据结构编码的基本内容,标识码,属性码,空间对象编码唯一连接空间和属性数据,数据库,独立编码,点:(x,y)线:(x1,y1),(x2,y2),(xn,yn)面:(x1,y1),(x2,y2),(x1,y1),点位字典,点:点号文件,线:点号串,面:点号串,存储方法,点实体,矢量数据结构,点实体包括由单独一对x，y坐标定位的一切地理或制图实体。,矢量数据结构,线实体：可以定义为直线元素组成的各种线性要素，直线元素由两对以上的x，y坐标定义。最简单的线实体只存储它的起止点坐标、属性、显示符号等有关数据。,矢量数据结构,多边形矢量编码，不但要表示位置和属性，更重要的是能表达区域的拓扑特征，如形状、邻域和层次结构等，以便使这些基本的空间单元可以作为专题图的资料进行显示和操作。,面实体,矢量数据结构编码的方法,1.实体式 实体式数据结构是指构成多边形边界的各个线段，以多边形为单元进行组织。按照这种数据结构，边界坐标数据和多边形单元实体一一对应，各个多边形边界都单独编码和数字化。,矢量数据结构编码的方法,简单的矢量数据结构面条结构（实体式）只记录空间对象的位置坐标和属性信息，不记录拓扑关系。存储：独立存储：空间对象位置直接跟随空间对象；点位字典：点坐标独立存储，线、面由点号组成特征无拓扑关系，主要用于显示、输出及一般查询公共边重复存储，存在数据冗余，难以保证数据独立性和一致性多边形分解和合并不易进行，邻域处理较复杂；处理嵌套多边形比较麻烦适用范围：制图及一般查询，不适合复杂的空间分析,矢量数据结构编码的方法,多边形 数据项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),(x29,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),简单的矢量数据结构面条结构（实体式）,矢量数据结构编码的方法,2.索引式 索引式数据结构采用树状索引以减少数据冗余并间接增加邻域信息，具体方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。,矢量数据结构编码的方法,2.索引式,线与多边形之间的树状索引,点与多边形之间的树状索引,矢量数据结构编码的方法,3.双重独立式 双重独立式数据结构是对图上网状或面状要素的任何一条线段，用其两端的节点及相邻面域来予以定义。,矢量数据结构编码的方法,3.双重独立式DIME(Dual lndependent Map Encoding),这种数据结构除了通过线文件生成面文件外，还需要点文件。,矢量数据结构编码的方法,4.链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。,矢量数据结构编码的方法,4.链状双重独立式数据结构,弧段文件弧段号 起始点 终结点 左多边形 右多边形a51OAb85EAc168EBd195OEe1519ODf1516DBg115OBh81ABi1619DEj3131BC弧段坐标文件弧段号点 号a5,4,3,2,1b8,7,6,5c16,17,8d19,18,5e15,23,22,21,20,19f15,16,g1,10,11,12,13,14,15h8,9,1i16,19j31,30,29,28,27,26,25,24,31,多边形文件多边形号弧段号周长 面积 中心点坐标Ah,b,aBg,f,c,h,-jCjDe,i,fEe,i,d,b,矢量与栅格一体化数据结构,矢量与栅格数据，按照传统的观念，认为是两类完全不同性质的数据结构，当利用它们来表达空间目标时：对于线状实体：人们习惯使用矢量数据结构。对于面状实体：在基于矢量的GIS中，主要使用边界表达法，在基于栅格的GIS中，一般用元子空间填充表达法。那么，对用矢量方法表示的线状实体，是不是也可以采用元子空间填充法来表示，即在数字化一个线状实体时，除记录原始取样点外，还记录所通过的栅格。同样，每个面状地物除记录它的多边形边界外，还记录中间包含的栅格。这样，既保持了矢量特性，又具有栅格的性质，就能将矢量与栅格统一起来。,矢量数据结构与栅格数据结构比较,矢量数据和栅格数据结构各有优缺点，适合于完成不同的功能，因此需要进行相互转换。矢量数据的基本坐标是直角坐标x,y，其坐标原点一般取图的左下方。网格数据的基本坐标是行和列（i,j），其坐标原点一般取图的左上角。,空间数据结构的转换,空间数据结构的转换,矢量数据结构向栅格数据结构的转换,两种数据变换时，令直角坐标x和y分别与行和列平行。由于矢量数据的基本要素是点、线、面，因而只要实现点、线、面的转换，就可解决矢量与栅格数据的转换。,空间数据结构的转换,矢量数据结构向栅格数据结构的转换,点：简单的坐标变换 线：线的栅格化 面：线的栅格化+面填充,空间数据结构的转换,点的变换十分简单，只要这个点落在哪个网格中就属于哪个网格元素，行列坐标（i,j）的计算公式为：,点的栅格化,矢量数据结构向栅格数据结构的转换,空间数据结构的转换,矢量数据结构向栅格数据结构的转换,曲线是由一组折线连接而成的，因此只要将折线中的每一线直线转换成栅格数据，则曲线和多边线的边的转换也就完成了。设一线段经过若干个网格元素，两端点的坐标为（x1,y1）和（x2,y2）。两端点所处的网格单元由点转换完成计算。剩下的任务是找出该线段所经过的网格。,线的栅格化,空间数据结构的转换,矢量数据结构向栅格数据结构的转换,线的栅格化,首先按点的栅格化方法确定端点1，2所在的行和列号，并将它们“涂黑”。求出这两个端点的行数差和列数差。,空间数据结构的转换,矢量数据结构向栅格数据结构的转换,（3）若行数差大于列数差，则逐行求出本行中心线与过这两个端点的直线的交点，并按上式计算出其所在栅格，并“涂黑”。（4）若行数差小于列数差，则逐列求出本列中心线与过这两个端点的直线的交点，并按上式计算出其所在栅格，并“涂黑”。,线的栅格化,空间数据结构的转换,矢量数据结构向栅格数据结构的转换,面的栅格化,内部点扩散算法（种子填充算法）按一定栅格尺寸将矢量图经栅格化后，对矢量图内每个面域多边形分别选择一个内部点（种子点）；对一个多边形，从种子点开始，向其8个相邻栅格扩散，分别判断这8个栅格是否在多边形的边界上：若是，则该栅格不作为种子点；若不是，则该栅格作为新的种子点。新的种子点与原种子点一起进行新的扩散运算；重复以上过种，直到所有新老种子点填满该多边形并遇到边界为止。,空间数据结构的转换,矢量数据结构向栅格数据结构的转换,面的栅格化,射线算法和扫描算法射线算法可逐点判断数据栅格点在某多边形之外或在多边形内，由待判断点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，若相交偶数次，则待判点在多边形外部，如为奇数次，则待判点在该多边形内部。,空间数据结构的转换,矢量数据结构向栅格数据结构的转换,面的栅格化,采用射线算法，要注意的是：射线与多边形边界相交时，有一些特殊情况会影响交点的个数，必须予以排除。扫描算法是射线算法的改进，将射线改为沿栅格阵列列或行方向扫描线，判断与射线算法相似。与扫描算法相比，其效率提高了很多。,空间数据结构的转换,矢量数据结构向栅格数据结构的转换,面的栅格化,边界代数算法 边界代数多边形填充算法适合于记录拓扑关系的多边形矢量数据转换为栅格数据结构。,空间数据结构的转换,栅格数据结构向矢量数据结构的转换,从栅格单元转换为几何图形的过程为矢量化。,空间数据结构的转换,栅格数据结构向矢量数据结构的转换,栅格数据可来源于扫描、遥感分类图像等。以黑白扫描图像为例，其转换步骤为：1.二值化 2.细化 3.线追踪 4.拓扑关系生成 5.去处多余点及曲线圆滑,空间数据结构的转换,栅格数据结构向矢量数据结构的转换,扫描图是以不同灰度值（0-255）表示的数据。首先进行栅格图像的二值化，即简化处理。二值化即某网络点要么表示地物，要么不为地物。具体方法即确定一个灰度阈值，灰度大于阈值的网格点赋1，其他为0（背景值），从而生成二值图。阈值大小的选取非常重要。,二值化,空间数据结构的转换,设地图图像的灰度范围为g1,g2，则可适当选择一灰度值Gg1,g2，对各像素的灰度值进行变换即完成地图图像的的二值化。,二值化,栅格数据结构向矢量数据结构的转换,空间数据结构的转换,栅格数据结构向矢量数据结构的转换,一般的扫描仪的分辨率可达到0.0125mm，也就是说，对于原图上0.1mm粗的线条，其横断面经扫描有8个格网。细化是消除线划横断面栅格数的差异，使得每一条线只保留代表其横轴线的单个栅格的宽度。细化的方法有很多，如“剥皮法”、“V值法”等,细化,空间数据结构的转换,栅格数据结构向矢量数据结构的转换,细化,剥皮法：该方法从线的边沿开始，每次剥掉等于一个栅格宽度 的一层，直到最后留下彼此连通的由单个栅格组成的图形。因为一条线在不同位置可能有不同的宽度，故在剥皮过程中必须注意一个条件，即不允许剥去会导致曲线不连通的栅格。,空间数据结构的转换,有了V值图以后，保留最大值，删去其它值，同时保持线的连通，即可完成细化。一般来说，要重复该过程多次才可将最大值并列现象去除。,细化,该方法是扫描全图，用下式计算出各网格的V值。,栅格数据结构向矢量数据结构的转换,V值法,空间数据结构的转换,栅格数据结构向矢量数据结构的转换,边界线跟踪的目的是将细化处理后的栅格数据，整理为从起始点出发的弧段或封闭曲线，并以矢量形式存储特征栅格点的坐标。跟踪可从图幅西北角开始，按顺时针或逆时针方向，从起始点开始，搜索八个相邻的网格，找出本线段上的一个邻点，直到本线段结束为止。线段上转折的点为结点或内点，矢量数据中只需记录这些点即可。上面示出的结点和内点，只是网格数据格式中的行列数，在矢量数据中，还需将其转换成平面直角坐标。它是矢量向栅格数据转换式的逆变换。,边界线跟踪,空间数据结构的转换,拓扑关系生成,对于矢量表示的边界弧段数据，判断其与原图上各多边形的空间关系，以形成完整的拓扑结构并建立与属性数据的联系。,栅格数据结构向矢量数据结构的转换,空间数据结构的转换,栅格数据结构向矢量数据结构的转换,去除多余点及曲线光滑,由于搜索是逐个栅格进行的，必然造成多余点记录，为减少数据冗余，必须去除多余点。此外，由于栅格精度的限制，边界线搜索的结果可能不够光滑，需要采用一定的插补算法进行光滑处理。,作业,1 名词解释 1)栅格数据 2）矢量数据 3）拓扑关系2 简答题 1）栅格数据存储压缩编码方法主要有哪几种？每种方法是如何进行压缩的？2）举例说明索引式数据结构、DIME数据结构、链状双重独立式数据结构,