第1讲 空间数据模型与数据结构

空间数据模型与数据结构目标要求：了解、掌握GIS空间数据模型的概念；了解、掌握常用的矢量数据结构和栅格数据结构。空间数据模型栅格数据结构矢量数据结构两种数据结构的比较与转换§1空间数据模型模型是对现实世界的简化表达。空间数据模型是关于现实世界中空间实体及其相互间联系的概念，它为描述空间数据的组织和设计空间数据库模式提供基本方法。1.1概述GIS空间数据模型由概念数据模型、逻辑数据模型和物理数据模型三个有机联系的层次组成。概念数据模型是关于实体及实体间联系的抽象概念集逻辑数据模型是表达概念数据模型中数据实体（或记录）及其间关系物理数据模型是描述数据在计算机中的物理组织、存储路径和数据库结构图3-1-1空间数据模型的三个层次概念数据模型由于职业、专业等的不同，人们所关心的问题、研究对象、期望的结果等方面存在着差异，因而对现实世界的描述和抽象也是不同的，形成了不同的用户视图，称之为外模式。GIS空间数据模型的概念模型是考虑用户需求的共性，用统一的语言描述和综合、集成各用户视图。概念数据模型是关于实体及实体间联系的抽象概念集。场模型--栅格数据模型要素模型--矢量数据模型网络模型……空间逻辑数据模型逻辑数据模型是根据概念数据模型确定的空间数据库信息内容（空间实体及相互关系），具体地表达数据项、记录等之间的关系，可以有若干不同的实现方法。结构化逻辑数据模型

层次数据模型：按树型结构组织数据记录，以反映数据之间的隶属或层次关系。网络数据模型面向操作的逻辑数据模型关系数据模型：用二维表格表达数据实体之间的关系，用关系操作提取或查询数据实体之间的关系

对象数据模型物理数据模型逻辑数据模型并不涉及最底层的物理实现细节，但计算机处理的是二进制数据，必须将逻辑数据模型转换为物理数据模型，即要设计空间数据的物理组织、空间存取方法、数据库总体存储结构等。

物理表示与组织：物理组织主要是考虑如何在外存储器上以最优的形式存放数据，通常要考虑操作效率、响应时间、空间利用和总的开销。层次逻辑数据模型的物理表示方法主要有物理邻接法、表结构法、目录法。网络数据模型的物理表示方法主要有变长指针表、位图法、目录法等。关系数据模型的物理表示是用关系表进行的。数据建模过程数据建模过程分为三步：选择一种数据模型来对现实世界的数据进行组织；选择一种数据结构来表达该数据模型；选择一种适合于记录该数据结构的文件格式。例如，表示地表高程的空间数据可以选用栅格模型进行组织，栅格模型选用游程编码这一数据结构进行表达，处理后的数据则以文件形式进行存储。地表也可用矢量模型来组织，即以等高线来表示地表，数据以拓扑结构进行安排并且以DLG文件格式存储。不规则三角网（TIN）模型，是另一种能很好地表达高程数据的数据模型。因此，一种空间数据建模可能有几种可选的数据结构，而每一种数据结构又可能有多种文件格式进行存储。地理信息系统中最常用的数据组织方式为矢量模型和栅格模型。在矢量模型中，用点、线、面表达世界，在栅格模型中用空间单元（Cell）或像元（Pixel）来表达。1.2基于场的栅格模型场模型用于模拟一定空间内连续变化的地理现象。例如，空气中污染物的集中程度、地表的温度、土壤的湿度水平以及空气与水的流动速度和方向。栅格数据模型是场模型的典型代表，它是将连续空间离散化，即用栅格单元划分整个连续空间；栅格单元可以分为规则的和不规则的；栅格单元的特征参数有尺寸、形状、方位和间距。在边数从3到N的规则栅格单元中，方格、三角形和六角形是空间数据处理中最常用的。栅格模型的分层表达1.3基于要素的矢量模型基于要素的矢量模型将现实世界抽象为各类要素的集合，要素的空间位置用一系列特征点的X、Y（、Z）坐标来表达，要素之间的空间关系主要通过拓扑关系来表达。矢量数据模型已经历了CAD模型、地理相关数据模型（Coverage模型）和面向对象的数据模型（Geodatabase模型）三个发展阶段。1.4网络模型网络模型用于描述现实世界中的线性系统，如道路交通网络、给排水系统、电力网络等。网络模型将线性系统抽象为边线（Edges）和交汇点（Junctions）的集合；边线和边线之间通过交汇点相连，流（flow）（如汽车流、电流和水流）可以从一条边线传输到另一条边线。边线如街道、传输线路、管道以及河段等；交汇点如街道交叉点、保险丝、开关、服务中心以及河流的汇合点等。Geodatabase

对线性网络系统有两种描述模型：几何网络模型（geometricnetwork）和逻辑网络模型（logicalnetwork）。几何网络模型是组成线性网络系统的要素的集合，是由边线和交汇点相连组成的系统。一条边线有两个交汇点，而一个交汇点可以与任何数量的边线相连。几何网络模型是从要素集合的视角来看网络模型。网络要素类（networkfeatureclass）：简单交汇点要素（simplejunctionfeature）复杂交汇点要素（complexjunctionfeature）简单边线要素（simpleedgefeature）复杂边线要素（complexedgefeature）逻辑网络模型是一个由边线元素和交汇点元素组成的网络图表。逻辑网络与几何网络相似，也是相连的边线和交汇点的集合。主要的区别在于逻辑网络没有坐标值。它的主要目标是用特定的属性表存储网络的连通性信息。既然逻辑网络中的边线和交汇点没有几何属性，因此它们不是要素，而是元素（elements）。一个几何网络总是与一个逻辑网络相联系，在编辑几何网络要素的时候，相应的逻辑网络元素会自动更新。逻辑网络不直接出现在ArcInfo

的应用中，与你直接接触的是几何网络。逻辑网络是网络要素进行复杂行为的基础。§2栅格数据结构简单栅格数据结构栅格数据的压缩编码方式2.1简单栅格数据结构栅格结构是指将研究区域划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素，由行、列号定义，并包含一个代码,表示该象素的属性类型或量值。栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。点用一个栅格单元表示线状地物用沿线走向的一组相邻栅格单元表示面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。任何以面状分布的对象(土地利用、土壤类型、地势起伏、环境污染等)，都可以用栅格数据逼近。遥感影像就属于典型的栅格结构，每个象元的数字表示影像的灰度等级。图3-6点线面的栅格表达栅格结构特点属性明显，定位隐含：即数据直接记录属性的指针或属性本身，而所在位置则根据行列号转换为相应的坐标给出。结构容易实现，算法简单，且易于扩充、修改，也很直观，特别是易于同遥感影像结合处理。误差较大：由于栅格结构对区域的量化，在计算面积、长度、距离、形状等空间指标时，若栅格尺寸较大，则会造成较大的误差，同时由于在一个栅格的范围内，可能存在多于一种的地物，而表示在相应的栅格结构中常常只能是一个代码。确定栅格单元代码的方式当一个栅格单元中有多个地物要素时，可根据需要用下列方法来确定栅格单元的代码：①中心点法：②面积占优法③重要性法2.2栅格数据的压缩编码方式链式编码(ChainCodes)游程长度编码（run-lengthcode）块状编码(blockcode)四叉树编码(quad-treecode)八叉树编码（octreecode）2.2.1链式编码(ChainCodes)链式编码主要是记录线状地物和面状地物的边界。它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：线状地物确定其起始点为像元(1，5)，则其链式编码为：3223323面状地物其起始点为像元（5，8），则该多边形边界按顺时针方向的链式编码为：32446676021链式编码的优缺点优点对线状和多边形的表示具有很强的数据压缩能力具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易比较适于存储图形数据。缺点对叠置运算如组合、相交等则很难实施对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界则被重复存储而产生冗余。2.2.2游程长度编码（run-lengthcode）对于一幅栅格图像，常常有行(或列)方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。其游程长度编码为：(9,4)，(0,4)(9,3)，(0,5)(0,1)，(9,2)，(0,1)，(7,2)，(0,2)(0,4)，(7,2)，(0,2)(0,4)，(7,4)(0,4)，(7,4)(0,4)，(7,4)(0,4)，(7,4)游程长度编码的特点压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高。游程长度编码在栅格加密时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存贮容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。2.2.3块状编码(blockcode)采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置(行、列号)和半径，再加上记录单元的代码组成。用12个单位正方形，5个4单位的正方形和2个16单位的正方形就能完整表示，具体编码如下：(1,1,2,9)，(1,3,1,9)，(1,4,1,9)，(1,5,2,0)，(1,7,2,0)，(2,3,1,9)，(2,4,1,0)，(3,1,1,0)，(3,2,1,9)，(3,3,1,9)，(3,4,1,0)，(3,5,2,7)，(3,7,2,0)，(4,4,1,0)，(4,2,1,0)，(4,3,1,0)，(4,4,1,0)，(5,1,4,0)，(5,5,4,7)块状编码的特点一个多边形所包含的正方形越大，多边形的边界越简单，块状编码的效率就越好。块状编码对大而简单的多边形更为有效，而对那些碎部较多的复杂多边形效果并不好。块状编码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而对某些运算不适应，必须在转换成简单数据形式才能顺利进行。2.2.4四叉树编码(quad-treecode)四叉树结构的基本思想是将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值(或灰度)，如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。

四叉树结构的基本思想四叉树的生成算法从上而下的分割算法：需要大量的运算，因为大量数据需要重复检查才能确定划分。当矩阵比较大，且区域内容要素又比较复杂时，建立这种四叉树的速度比较慢。从下而上的合并算法：如果每相邻四个网格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快。为了保证四叉树能不断的分解下去，要求图像必须为2n*2n的栅格阵列，n为极限分割次数，n+1是四叉树的最大高度或最大层数。四叉树编码的特点①容易而有效地计算多边形的数量特征；②阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；③栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；④多边形中嵌套异类小多边形的表示较方便。四叉树结构分类常规四叉树常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。线性四叉树线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值。线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的Morton码。基于十进制的Morton码及四叉树的建立0145161720212367181922238912132425282910111415262730313233363748495253343538395051545540414445565760614243464758596263（a）四叉树分割示意图(b)基于十进制的线性四叉树Morton码基于按位操作的运算计算Morton码设十进制表示的行、列号在计算机内部的二进制数字分别为：十进制的Morton码实际上是II、JJ中的二进制数字交叉结合的结果，即Morton码属性值09495969708099100110Morton码属性值129130140150160200247280320487线性四叉树存储结构0145161720212367181922238912132425282910111415262730313233363748495253343538395051545540414445565760614243464758596263二维行程编码在生成的线性四叉树表中，仍存在前后叶结点的值相同的情况，因而可以采取进一步的压缩表达，即将格网值相同的前后结点合并成一个值，形成二维行程编码（TwoDimensionalRunEncoding，简称2DRE）表。在这种二维行程编码中，前后两个地址码之差表达了该行程段的格网数，它可以表示该子块的大小。Morton码属性值097099100129130247320487Morton码属性值09495969708099100110Morton码属性值129130140150160200247280320487线性四叉树存储结构二维行程编码存储结构2.2.5八叉树结构八叉树结构是四叉树结构在三维空间的扩展。八叉树结构就是将空间区域不断地分解为八个同样大小的子区域(即将一个六面的立方体再分解为八个相同大小的小立方体)，分解的次数越多，子区域就越小，一直到同—区域的属性单一为止。按从下而上合并的方式来说，就是将研究区空间先按—定的分辨率将三维空间划分为三维栅格网，然后按规定的顺序每次比较3个相邻的栅格单元，如果其属性值相同则合并，否则就记盘。依次递归运算，直到每个子区域均为单值为止。§3矢量数据结构矢量数据结构实体式索引式双重独立式链状双重独立式3.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)实体式结构的特点优点：编码容易、数字化操作简单和数据编排直观等。缺点：①相邻多边形的公共边界要数字化两遍，造成数据冗余存储，可能导致输出的公共边界出现间隙或重叠；②缺少多边形的邻域信息和图形的拓扑关系；③岛只作为一个单个图形，没有建立与外界多边形的联系。实体式编码只用在简单的系统中。3.2索引式索引式数据结构采用树状索引以减少数据冗余并间接增加邻域信息具体方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。树状索引结构消除了相邻多边形边界的数据冗余和不一致的问题。文件结构点号坐

标1X1,y12X2,y2…31X31,y31线号起点终点点号a151,2,3,4,5b585,6,7,8…j242424,25,26,…,31多边形编号多边形边界Aa,b,hB…E点文件结构线文件结构多边形文件结构3.3双重独立式这种数据结构最早是由美国人口统计局研制来进行人口普查分析和制图的DIME(DualIndependentMapEncoding)系统或双重独立式的地图编码法。它以城市街道为编码的主体。其特点是采用了拓扑编码结构。双重独立式数据结构是对图上网状或面状要素的任何一条线段，用其两端的结点及相邻面域来予以定义。双重独立式（DIME）编码线号左多边形右多边形起点终点aOA18bOA21cOB32dOB43eOB54fOC65gOC76hOC87iCA89jCB95kCD1210lCD1112mCD1011nBA923.4链状双重独立式链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。在链状双重独立数据结构中，主要有四个文件：多边形文件弧段文件弧段节点文件结点文件多边形号弧段号周长面积中心点坐标Ah,b,aBg,f,c,h,-jCjDe,i,fEe,i,d,b弧段号起始点终结点左多边形右多边形a51OAb85EAc168EBd195OEe1519ODf1516DBg115OBh81ABi1619DEj3131BC弧段号点

号a5,4,3,2,1b8,7,6,5c16,17,8d19,18,5e15,23,22,21,20,19还有点文件3.5矢量、栅格数据结构的比较矢量数据结构特点优点：（1）它是面向目标的，不仅能表达属性编码，而且容易定义和操作单个空间实体。（2）能完整地描述拓扑关系；（3）表示地理数据的精度较高；（4）图形输出精确美观；（5）严密的数据结构，数据量小；（6）图形数据和属性数据的恢复、更新、综合都能实现；缺点：（1）数据结构复杂；（2）矢量多边形的叠置算法较为复杂；（3）数学模拟比较困难；（4）技术复杂，特别是更加复杂的硬、软件。栅格数据结构特点优点：（1）数据结构简单；（2）空间数据的叠置和组合十分容易方便；（3）各类空间分析都很易于进行；（4）数学模拟方便。缺点：（1）图形数据量大；（2）用大像元减少数据量时，精度和信息量受损失；（3）地图输出不精美；（4）没有表达拓扑关系；（5）投影变换花的时间多。栅格、矢量数据结构简单比较

比较内容

矢量格式

栅格格式

数据量

小

大

图形精度

高

低

图形运算

复杂、高效

简单、低效

遥感影像格式

不一致

一致或接近

输出表示

抽象、昂贵

直观、便宜

数据共享

不易实现

容易实现

拓扑和网络分析

容易实现

不易实现§4矢量栅格一体化数据结构4.1矢栅一体化的概念一体化数据结构的基本概念：无论是点状地物、线状地物、还是面状地物均采用面向目标的描述方法，因而它可以完全保持矢量的特性，而元子空间充填表达建立了位置与地物的联系，使之具有栅格的性质。每个线状目标除记录原始取样点外，还记录路径所通过的栅格；每个面状地物除记录它的多边形周边以外，还包括中间的面域栅格。4.2三个约定和细分格网法4.2.1三个约定为了设计点、线、面状地物具体的一体化数据结构，首先作如下约定：1、地面上的点状地物是地球表面上的点，它仅有空间位置，没有形状和面积，在计算机内部仅有一个位置数据。2、地面上的线状地物是地球表面的空间曲线，它有形状但没有面积，它在平面上的投影是一连续不间断的直线或曲线，在计算机内部需要用一组元子填满整个路径。3、地面上的面状地物是地球表面的空间曲面，并具有形状和面积，它在平面上的投影是由边界包围的紧致空间和一组填满路径的元子表达的边界组成。4.2.2细分格网法由于一体化数据结构是基于栅格的，表达目标的精度必然受栅格尺寸的限制。可利用细分格网法提高点、线（包括面状地物边界）数据的表达精度，使一体化数据结构的精度达到或接近矢量表达精度。细分格网的思想在有点、线通过的基本格网内再细分成256×256细格网（精度要求低时，可细分为16×16个细格网）。基本格网和细格网均采用十进制线性四叉树编码，将采样点和线性目标与基本格网的交点用两个Morton码表示。前一M1表示该点（采样点或附加的交叉点）所在基本格网的地址码，后者M2表示该点对应的细分格网的Morton码，亦即将一对X,Y坐标用两个Morton码代替。例如X=210.00，Y=172.32，可转换为M1=275,M2=2690，对应的行列号分别为（1，21）、（51，6）。这种方法可将栅格数据的表达精度提高256倍，而存贮量仅在有点、线通过的格网上增加两个字节（当细分为16×16格网时，存贮量仅增加一个字节，精度提高16倍）。4.3矢栅一体化数据结构的设计线性四叉树编码、三个约定和多级格网法为建立矢栅一体化的数据结构奠定了基础。线性四叉树是基本数据格式，三个约定设计点、线、面数据结构的基本依据，细分格网法保证足够精度。4.3.1点状地物和结点的数据结构

点仅有位置、没有形状和面积，不必将点状地物作为一个覆盖层分解为四叉树，只要将点的坐标转化为地址码M1和M2

，而不管整个构形是否为四叉树。这种结构简单灵活，便于点的插入和删除，还能处理一个栅格内包含多个点状目标的情况。所有的点状地物以及弧段之间的结点数据用一个文件表示。可见，这种结构几乎与矢量结构完全一致。点状地物和结点的数据结构4.3.2线状地物的数据结构根据对线状地物的约定，线状地物有形状但没有面积，没有面积意味着线状地物和点状地物一样不必用一个完全的覆盖层分解四叉树，而只要用一串数据表达每个线状地物的路径即可，表达一条路径就是要将该线状地物经过的所有栅格的地址全部记录下来。一个线状地物可能有几条弧段组成，所以应先建立一个弧段数据文件。4.3.3面状地物的数据结构一个面状地物应记录边界和边界所包围的整个面域，其中边界由弧段组成，它同样引用弧段信息；面域信息则由线性四叉树或二维行程编码表示。为了建立面向地物的数据结构，二维行程编码中的属性值可以是叶结点的属性值，也可以是指向该地物的下一个子块的循环指针。即用循环指针将同属于一个目标的叶结点链接起来，形成面向地物的结构。4.3.4复杂地物的数据结构由几个或几种点、线、面状简单地物组成的地物称为复杂地物。例如将一条公路上的中心线、交通灯、立交桥等组合为一个复杂地物，用一个标识号表示。§5矢量栅格数据结构的转换5.1矢量数据结构向栅格数据结构的转换两种数据变换时，令直角坐标x、y分别与行和列平行。由于矢量数据的基本要素是点、线、面，因而只要实现点、线、面的转换，就能实现整个线划图的转换。Ymax矢量数据向栅格数据转换的步骤确定栅格单元的大小点的变换线的变换面的充填5.1.1确定栅格单元的大小栅格单元的大小就是它的分辨率，应根据原图的精度，变换后的用途及存贮空间等因素予以决定。如果变换后要和一幅卫星图像匹配，最好采用与卫星图像相同的分辨率。如果作为地形分析用，地形起伏变化小时分辨率可以低些，栅格单元就可大些；而地形变化大时，分辨率就应当高些，栅格单元就要小些。栅格单元的大小为△x和△y，设Xmax、Xmin和Ymax、Ymin分别表示全图X坐标和Y坐标的最大值与最小值，NI、NJ表示全图格网的行数和列数，它们之间的关系为5.1.2点的变换点（X，Y）的变换很简单，只要这个点落在某个栅格中，就属于那个栅格单元，其行、列号J、J可出下式求出：式中INT表示取整函数。栅格点的值用点的属性表示。假定I，J从0开始起算。5.1.3线的变换对于曲线可以近似地看成多个直线段组成的折线。每一条直线段需要求算它经过哪些格网单元。设线段两瑞点的坐标为(X1，Y1)，(X2，Y2)，先求出这二个端点栅格单元的行列号，然后求中间经过的栅格。假设求出两端点的行号分别为n1、n2（如3和7），则中间格网的行号必为n1+1，n1+2，……，n2（如4，5，6），其网格中心线的Y坐标应为它与直线段交点的X坐标为再由此Xi值可求出其列号J，即也可以先求出两端点的列号，再确定中间网格的行号。5.1.4面的充填充填的关键问题是使计算机能正确判断哪些栅格单元在多边形之内，哪些栅格在多边形之外。矢量多边形（面域）栅格面域