第三章空间数据结构

第三章空间数据结构栅格数据结构矢量数据结构两种数据结构的比较与转化其他数据结构数据结构是指数据组织的形式，是适合于计算机存储、管理和处理的数据逻辑结构；对空间数据而言则是地理实体的空间排列方式和相互关系的抽象描述，是对数据的一种理解和解释。不说明数据结构的数据是毫无用处的，不仅用户无法理解，计算机程序也不能正确处理。第一节栅格数据结构定义：栅格结构是最简单最直接的空间数据结构，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素，由行、列定义，并包含一个代码表示该象素的属性类型或量值，或仅仅包括指向其属性记录的指针。因此，栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。栅格数据实际就是像元阵列，每个像元由行列确定它的位置。由于栅格结构是按一定的规则排列的，所表示的实体位置很容易隐含在数据文件的存储结构中，且行列坐标可以很容易地转为其它坐标系下的坐标。遥感影像是典型的栅格结构，每个象元的数值表示影像的灰度等级。点线面点：为一个像元线：在一定方向上连接成串的相邻像元集合。面：聚集在一起的相邻像元集合。B,B,B,B,B,R,B,B,E,E,B,E,H,B,R,B,B,B,E,E,B,E,B,B,R,P,P,B,E,B,

E,B,B,B,R,P,P,B,B,B,B,B,B,R,P,P,B,B,B,B,B,B,B,R,B,B,B,B,B,B,B,B,B,R,B,B,B,B,B,B,B,B,R,B,B,B,B,B,H,B,B,B,R,B,B,B,B,B,B,B,B,R,R,B,B,B,B,B,B,B栅格数据结构特点离散的量化栅格值表示空间对象。位置隐含，属性明显。数据结构简单，易于扩充、修改，易于与遥感数据结合，但数据量大。适合于高级语言作文件或矩阵处理。存在几何和属性误差。获得栅格结构数据的途径目读法：在地图上均匀划分网格，逐个网格地确定其代码；矢量数字化法：用数字化仪得到矢量数据结构后，再转换成栅格结构；扫描数字化：逐点扫描地图，将扫描数据进行重采样和再编码；分类影像输入：将经过分类解译的遥感影像数据直接或重采样后输入系统。数据转换和重采样的方法1、决定栅格代码时尽量保持地表的真实性，保证最大的信息容量。2、缩小单个栅格单元的面积，即增加栅格单元总数，行列数也相应增加。原则：需尽可能保持原图或原始数据精度！栅格数据的几何误差

在下图中，ac的距离应为5，但在栅格结构中，如以像元边线计算则为7，以像元为单位则为4。三角形abc的面积应为6个平方单位，而在栅格结构中则为7个平方单位，这种误差随像元的增大而增加。abc345abcac距离:7/4(5)面积:7(6)4栅格数据的属性误差在一个栅格的地表范围内，可能存在具有不同属性的地理实体，如可能存在多于一种的地物，而表示在相应的栅格结构中常常只能是一个代码，因此出现属性误差。如何选取主要地物的问题？栅格数据单元属性值确定CAB百分比法面积占优重要性中心点法A连续分布地理要素C具有特殊意义的较小地物A分类较细、地物斑块较小AB为了逼近原始数据精度，除了采用这几种取值方法外，还可以采用缩小单个栅格单元的面积，增加栅格单元总数的方法。决定栅格单元代码的方式在决定栅格代码时尽量保持地表的真实性，保证最大的信息容量。下图所示的一块矩形地表区域，内部含有A、B、C三种地物类型，O点为中心点，将这个矩形区域近似地表示为栅格结构中的一个栅格单元。决定栅格单元代码的方式

——中心点法用处于栅格中心处的地物类型或现象特性决定栅格代码，在上图所示的矩形区域中，中心点O落在代码为C的地物范围内，按中心点法的规则，该矩形区域相应的栅格单元代码为C。中心点法常用于具有连续分布特性的地理要素，如降雨量分布、人口密度图等。决定栅格单元代码的方式

——面积占优法以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代码，在上图所示的例子中，显见B类地物所占面积最大，故相应栅格代码定为B。面积占优法常用于分类较细，地物类别斑块较小的情况。决定栅格单元代码的方式

——重要性法根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码，假设上图中A类最重要的地物类型，即A比B和C类更为重要，则栅格单元的代码应为A。重要性法常用于具有特殊意义而面积较小的地理要素，特别是点、线状地理要素，如城镇、交通枢纽、交通线、河流水系等，在栅格中代码应尽量表示这些重要地物。决定栅格单元代码的方式

——百分比法根据矩形区域内各地理要素所占面积的百分比数确定栅格单元的代码，如可记面积最大的两类BA，也可以根据B类和A类所占面积百分比数在代码中加入数字。栅格数据的编码方式直接栅格编码压缩编码方式直接栅格编码（1）这是最简单直观而又非常重要的一种栅格结构编码方法，通常称这种编码的图像文件为网格文件或栅格文件，栅格结构不论采用何种压缩编码方法，其逻辑原型都是直接编码网格文件。直接栅格编码（2）直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元记录，也可以奇数行地从左到右而偶数行地从右向左记录，为了特定目的还可采用其他特殊的顺序。一些常用的栅格排列顺序栅格数据压缩编码方法压缩编码的目的是用尽可能少的数据量记录尽可能多的信息，其类型又有信息无损编码和信息有损编码之分。在地理信息系统中多采用信息无损编码，而对原始遥感影像进行压缩编码时，有时也采取有损压缩编码方法。栅格数据压缩编码方法信息无损编码是指编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息；信息有损编码是指为了提高编码效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复。栅格数据压缩存储的编码方法（1）

——链式编码(ChainCodes)又称为弗里曼链码（Freeman）或边界链码。该方法将线状地物和面状地物的边界表示为：由某一起点开始并按某些基本方向确定的单位矢量链。链式编码的前两位数字表示起点的行、列数，从第三个数字开始表示单位矢量的方向。前提：规定单位矢量的方向！栅格数据压缩存储的编码方法（1）

——链式编码(ChainCodes)如果右图中面状地物的起点为像元(10，1)，则其边界按顺时针方向的链式编码为：

10，1，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。01234567栅格数据压缩存储的编码方法（1）

——链式编码(ChainCodes)优点：可有效地压缩栅格数据，对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适合于存储图形数据。缺点：对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界将被重复存储而产生冗余。栅格数据压缩存储的编码方法（2）

——游程长度编码(Run—LengthCodes)游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。栅格数据压缩存储的编码方法（2）

——游程长度编码(Run—LengthCodes)其方法有两种方案：一种编码方案是，只在各行（或列）数据的代码发生变化时依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。沿行方向编码：（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)。栅格数据压缩存储的编码方法（2）

——游程长度编码(Run—LengthCodes)另一种游程长度编码方案就是逐个记录各行（或列）代码发生变化的位置和相应代码。编码如下（沿列方向）：（1，0），（2，4），（4，0），（1，4），（4，0）；（1，4），（5，8），（6，0）；（1，7），（2，4），（4，8），（7，0）；（1，7），（2，4），（3，8），（8，0）；（1，7），（3，8）；（1，7），（6，8）；（1，7），（5，8）栅格数据压缩存储的编码方法（2）

——游程长度编码(Run—LengthCodes)游程长度编码压缩数据是十分有效又简便的。事实上，压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高。栅格数据压缩存储的编码方法（2）

——游程长度编码(Run—LengthCodes)游程长度编码在栅格压缩时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。栅格数据压缩存储的编码方法（3）

——块式编码(BlockCodes)块式编码是将游程长度编码扩大到二维的情况，把多边形范围划分成由像元组成的正方形，然后对各个正方形进行编码。如图：块式编码的数据结构由初始位置（行号，列号）和边长，再加上记录单元的代码组成。根据这一编码原则，上述多边形只需12个单位正方形。5个4单位的正方形和2个16单位的正方形就能完整表示，总共要41个数据，其中19对坐标，3个块的半径。具体编码如下（1，1，2，9），（1，3，1，9），（1，4，1，9），（1，5，2，0），（1，7，2，0），（2，3，1，9）……栅格数据压缩存储的编码方法（3）

——块式编码(BlockCodes)

在实际应用中，栅格划分细，数据冗余多的多，才能显出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少数据冗余。栅格数据压缩存储的编码方法（3）

——块式编码(BlockCodes)

块码具有可变的分辨率，即代码变化小时图块大，就是说在区域图斑内部分辨率低；反之，分辨率高以小块记录区域边界地段，以此达到压缩的目的。栅格数据压缩存储的编码方法（3）

——块式编码(BlockCodes)

块码与游程长度编码相似，随着图形复杂程度的提高而降低效率，就是说图斑越大，压缩比越高；图斑越碎，压缩比越低。块码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而在某些操作时，则必须把游程长度编码和块码解码，转换为基本栅格结构进行。栅格数据压缩存储的编码方法（4）

——四叉树编码(QuadtreeEncoding)

四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法之一，绝大部分图形操作和运算都可以直接在四叉树结构上实现，因此四叉树编码既压缩了数据量，又可大大提高图形操作的效率。四叉树将整个图像区逐步分解为一系列被单一类型区域内含的方形区域，最小的方形区域为一个栅格象元。栅格数据压缩存储的编码方法（4）

——四叉树编码(QuadtreeEncoding)

分割的原则：将图像区域划分为四个大小相同的象限，而每个象限又可根据一定规则判断是否继续等分为次一层的四个象限，其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物或符合既定要求的少数几种地物时，则不再继续划分，否则一直划分到单个栅格象元为止。栅格数据压缩存储的编码方法（4）

——四叉树编码(QuadtreeEncoding)

栅格数据压缩存储的编码方法（4）

——四叉树编码(QuadtreeEncoding)

优点：便于计算多边形的数量特征；阵列各部分的分辨率可变，既可以精确表示图形结构又可以减少存储量；栅格到四叉树的结构互换比其它压缩方法容易；对多边形中嵌套的异类小多边形表示较为方便。栅格数据压缩存储的编码方法（4）

——四叉树编码(QuadtreeEncoding)

缺点：转换的不确定性，用同一形状和大小的多边形可能得出多种不同的四叉树结构，故不利于形状分析和模式识别。栅格数据压缩存储的编码方法（5）

——八叉树编码

八叉树结构就是将空间区域不断地分解为八个同样大小的子区域（即将一个六面的立方体再分解为八个相同大小的小立方体），同一区域的属性相同。八叉树主要用来解决地理信息系统中的三维问题。栅格数据结构：数据分层土壤地貌森林建筑物ZYX栅格数据结构：数据组织栅格数据文件像元1X坐标Y坐标层2属性值层1属性值…层n属性值…像元2像元n栅格数据文件层1像元1层2…X,Y,属性值像元2X,Y,属性值……像元nX,Y,属性值层n栅格数据文件层1多边形1层2…属性值像元1坐标…多边形N像元n坐标层n栅格数据的各种压缩编码方式的比较压缩编码方式特点链式编码

对线状和面状地理实体的表示有很强的压缩能力；具有一定的运算功能；探测边界急弯和凹进部分等比较容易；类似矢量数据结构，比较适合存储图形数据。对叠置运算很难实施；对局部修改将改变整体结构；效率较低；相邻多边形的边界被重复存储从而产生冗余。游程长度编码

在栅格加密时，数据量没有明显增加，压缩效率较高，易于进行检索、叠加、合并等操作，运算简单。块状编码

对大而简单的多边形更有效；在合并、插入、检查延伸性、计算面积等操作有明显的优势。四叉树编码

能容易而有效地计算多边形的数量特征；阵列各部分的分辨率是可变的，既精确表示图形结构又可减少存储量；与简单栅格的相互转换比较容易；多边形中嵌套小多边形比较方便。具有转换的不确定性，不利于形状分析和模式识别。第二节矢量数据结构定义：矢量数据结构通过记录空间对象的坐标及空间关系来表达空间对象的位置。即通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体，坐标空间设为连续，允许任意位置、长度和面积的精确定义。矢量数据结构是通过记录坐标的方式，尽可能地将点、线、面地理实体表现得精确无误。其坐标空间假定为连续空间，不必象栅格数据结构那样进行量化处理。因此矢量数据能更精确地定义位置、长度和大小。

由于以下原因，不可能得到绝对精确的值：表示坐标的计算机字长有限；所有矢量输出设备的分辨率比栅格设备高，但也有一定的步长；矢量法输入时选取的点不可能太多；人工输图时存在不可避免的定位误差。矢量数据结构的特点用离散的点描述空间对象与特征，定位明显，属性隐含。用拓扑关系描述空间对象之间的关系。面向目标操作，精度高，数据冗余度小。与遥感等图象数据难以结合。输出图形质量好，精度高。矢量数据结构编码的基本内容矢量数据结构通过记录空间对象的坐标及空间关系来表达空间对象的位置。点：空间的一个坐标点；线：多个点组成的弧段；面：多个弧段组成的封闭多边形；点实体点实体包括由单独一对x，y坐标定位的一切地理或制图实体。在矢量数据结构中，除点实体的x，y坐标外还应存储其它一些与点实体有关的数据来描述点实体的类型、制图符号和显示要求等。点是空间上不可再分的地理实体，可以是具体的也可以是抽象的，如地物点、文本位置点或线段网络的结点等。线实体线实体可以定义为直线元素组成的各种线性要素，直线元素由两对以上的x，y坐标定义。最简单的线实体只存储它的起止点坐标、属性、显示符等有关数据。例如，线实体输出时可能用实线或虚线描绘，这类信息属符号信息，它说明线实体的输出方式。虽然线实体并不是以虚线存储，仍可用虚线输出。线实体主要用来表示线状地物(公路、水系、山脊线)、符号线和多边形边界，有时也称为“弧”、“链”、“串”等。唯一标识是系统排列序号：线标识码可以标识线的类型；起始点和终止点可以用点号或直接用坐标表示；显示信息是显示线的文本或符号等；与线相联的非几何属性可以直接存储于线文件中，也可单独存储，而由标识码联接查找。面实体多边形（区域）数据是描述地理信息的最重要的一类数据。在区域实体中，具有名称属性和分类属性的，多用多边形表示，如行政区、土地类型、植被分布等；具有标量属性的，有时也用等值线描述（如地形、降雨量等）。

多边形矢量编码，不但要表示位置和属性，更重要的是能表达区域的拓扑特征，如形状、邻域和层次结构等，以便使这些基本的空间单元可以作为专题图的资料进行显示和操作，由于要表达的信息十分丰富，基于多边形的运算多而复杂，因此多边形矢量编码比点和线实体的矢量编码要复杂得多，也更为重要。矢量数据结构编码的方式按功能和方法分为：实体式索引式双重独立式链状独立式矢量数据结构编码的方式（1）

—实体式（面条结构）构成多边形边界的各个线段，以多边形为单位进行组织，只记录空间对象的位置坐标和属性信息，不记录拓扑关系。实体式（面条结构）——多边形数据实体式（面条结构）——多边形数据文件实体式编码优缺点比较优点：（1）编码容易；（2）数字化操作简单（3）数据编排直观缺点：(1)相邻多边形的公共边界要数字化两遍，造成数据冗余存储，可能导致输出的公共边界出现间隙或重叠；(2)缺少多边形的邻域信息和图形的拓扑关系；(3)岛只作为一个单个图形，没有建立与外界多边形的联系；（4）不易检查拓扑错误。实体式（面条结构）编码方式特征无拓扑关系，主要用于显示、输出及一般查询；公共边重复存储，存在数据冗余，难以保证数据独立性和一致性；多边形分解和合并不易进行，邻域处理较复杂；处理嵌套多边形比较麻烦。实体式（面条结构）编码方式

存储及适用范围存储：独立存储：空间对象位置直接跟随空间对象；点位字典：点坐标独立存储，线、面由点号组成适用范围：制图及一般查询，不适合复杂的空间分析矢量数据结构编码的方式（2）

—索引式

索引式数据结构采用树状索引以减少数据冗余并间接增加邻域信息。具体方法：对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。索引式编码方式——树状索引图线与多边形之间的树状索引点与线之间的树状索引索引式编码优缺点比较优点：（1）相邻多边形边界无数据冗余；（2）简化或合并复杂边界线或多边形时可不必改造索引表；（3）邻域信息和岛状信息可以通过对多边形文件的线索引处理得到。缺点：(1)线索引处理比较繁琐，给邻域函数运算、消除无用边、处理岛状信息以及检查拓扑关系等带来一定的困难；（2）编码表要以人工方式建立，工作量大且容易出错。矢量数据结构编码的方式（3）

——双重独立式对任何一条线段，用其两端的节点及相邻面域来表示；（拓扑）利用这种拓扑关系来组织数据，可以有效地进行数据存储正确性检查，同时便于对数据进行更新和检索。矢量数据结构编码的方式（3）

——双重独立式

——双重独立式

矢量数据结构编码的方式（3）线号左多边形右多边形起点终点aOA18bOA21cOB32dOB43eOB54fOC65gOC76hOC87iCA89jCB95kCD1210lCD1112mCD1011nBA92

矢量数据结构编码的方式（4）

——链状双重独立式

链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。多边形矢量数据多边形文件弧段文件弧段坐标文件矢量数据结构的属性数据表达属性特征类型类别特征：是什么说明信息：同类目标的不同特征属性特征表达类别特征：类型编码说明信息：属性数据结构和表格图形数据和属性数据的连接通过目标识别符或内部记录号实现。矢量数据结构的属性数据表达点状对象目标标识目标标识地物编码坐标关联的线目标精度控制点等级测量单位测量年限线状对象目标标识目标标识地物编码坐标串起点、终点、左面、右面路面材料等级修建时间宽度管养单位…………面状对象目标标识目标标识地物编码边界目标号建筑日期所有者建筑面积建筑单位结构……空间对象地物编码地物名称制图颜色几何类型制图符号编码属性表明地物类型特征与制图属性第三节两种数据结构的比较与转换矢量数据优点：表示地理数据的精度较高严密的数据结构，数据量小完整的描述空间关系图形输出精确美观图形数据和属性数据的恢复、更新、综合都能实现面向目标，不仅能表达属性，而且能方便的记录每个目标的具体属性信息缺点：数据结构复杂矢量叠置较为复杂数学模拟比较困难技术复杂，特别是软硬件栅格数据优点：数据结构简单空间数据的叠置和组合方便各类空间分析很易于进行数学模拟方便缺点：图形数据量大用大像元减少数据量时，精度和信息量受损地图输出不美观难以建立网络连接关系投影变换比较费时栅格、矢量数据结构特点比较数据结构选择原则要素还是位置？可获取的数据定位要素的必要精度需要什么类型的要素需要什么类型的拓扑关联所需空间分析类型生产地图类型矢量数据向栅格数据转换

——点的变换

矢量数据向栅格数据转换

——矢量线段的变换如下图：先标出两端点的行数i为3和10；然后分别确定直线经过的4，5，6，7，8，9六行中的哪一列与直线相交；以第7行为例，找到第7行（i=7)中心的y值是多少，就可求出相应的j值；同法计算其它行的j值；用本直线的属性值填充直线经过的网格。2211(x,y)(x,y)(x,y)矢量数据向栅格数据转换

——多边形数据的转换从多边形的起点依次记录每一点左边面域值；对多边形的每一条边转换成栅格形式；进行节点处理，使节点的栅格值唯一而准确；从第一行起逐行按列的先后顺序排序，使得到的数据结构等同于栅格数据压