第4章空间数据结构

.,地理信息系统GeographicInformationSystem,徐斌长安大学,.,第4章空间数据结构,4.1矢量数据结构4.2栅格数据结构4.3矢栅一体化数据结构4.4镶嵌数据结构4.5三维数据结构,.,本章学习要点,空间数据结构是对空间逻辑数据模型描述的数据组织关系和编排方式，是空间数据模型的具体实现，对地理信息系统中数据存储、查询、检索和分析应用等操作处理有至关重要的影响。掌握数据结构类型与特点，是合理的空间建模与数据组织的基础。要点：矢量数据机构栅格数据结构,.,栅格模型,矢量模型,.,4.1矢量数据结构,1.矢量数据的概念2.矢量数据结构的表示（1）简单数据结构及编码（2）拓扑数据结构及编码,.,1.矢量数据的概念,矢量：具有长度和方向的量。矢量数据结构：通过记录坐标值的方式尽可能精确地表示点、线或面状分布的地理实体，坐标空间设为连续，允许任意位置、长度和面积的精确定义。在一般情况下，其精度比栅格数据结构高得多。其精度仅受数字化设备的精度和数值记录字长的限制。,.,2.矢量数据结构的表示,计算机地图制图中，研究表示矢量数据的结构时应考虑的问题：矢量数据的存储和处理；与属性数据的关联；矢量数据之间拓扑关系的表示。,.,（1）简单数据结构及编码简单数据结构也称为面条数据结构，只记录空间对象的位置坐标和属性信息，不记录拓扑关系。常见方法：独立实体法和点位字典法。,.,独立实体法使用点、线、面对象分别记录其坐标对，即每个实体的坐标都独立存储，并不关心相邻的多边形或线状和点状地物。具体形式和公式如下：点对象：对象标识,(x,y),属性数据;线对象：对象标识,(x1,y1),(x2,y2)(xn,yn),属性数据;面对象：对象标识,(x1,y1),(x2,y2)(xn,yn),(x1,y1),属性数据;对面状实体，最末一点坐标与第一点坐标相等。,.,地图要素的矢量数据表示例：图4.1，表4.1,.,优点：编码容易，数字化操作简单，数据编码直观，显示速度快。缺点：除了外轮廓线以外，多边形的边界数据均获取和存储两次，这样会产生裂缝或重叠，并产生数据冗余。为了消除裂缝，一般要编辑。缺少拓扑关系，空间分析困难。,.,点位字典法使用坐标文件记录所有点坐标对，并使用点号惟一标示每一个坐标对，点、线、面对象都由点号组成。点位字典：点号,(x,y);点对象：惟一标志码,点号,属性数据;线对象：惟一标志码,(点号1，点号n),属性数据;面对象：惟一标志码,(点号1，点号n，点号1),属性数据;例：图4.1，表4.2，表4.3,.,（2）拓扑数据结构及编码索引式结构（略）双重独立地图编码链状双重独立式编码,.,拓扑数据结构,记录空间实体的位置、标志及属性信息，同时记录拓扑关系。双重独立地图编码双重独立地图编码（DualIndependentMapEncoding，DIME），是美国人口调查局在人口调查的基础上发展起来的，它通过有向编码建立了多边形、边界、结点之间的拓扑关系，DIME编码成为其它拓扑编码结构的基础。例：图4.4，表4.7,.,双重独立式DIME(DuallndependentMapEncoding),这种数据结构除了通过线文件生成面文件外，还需要点文件,.,链状双重独立式编码链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、点文件。,.,点文件：标志码，（x,y）;弧段坐标文件：标志码，弧段中间点；弧段文件：标志码，起始结点，终止结点，左多边形，右多边形；多边形文件：标志码，组成多边形的弧段号，属性（面积、周长）及中心点坐标等。例：图4.4，表4.8，表4.9，表4.10，表4.11,.,弧段文件弧段号起始点终结点左多边形右多边形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,.,优点：数据结构紧凑、数据冗余小；拓扑关系明晰，拓扑查询、分析效率高。缺点：对单个地理实体的操作效率低，难以表达复杂的地理实体，查询效率低，局部更新困难。,.,实体型与拓扑型数据结构比较,两者都是目前最常用的数据结构模型实体型代表软件为MapInfo拓扑型代表软件为ARC/INFO它们各具特色,实体型虽然会产生数据冗余和歧异，但易于编辑。,拓扑型消除了数据的冗余和歧异，但操作复杂，甚至会产生新的数据冗余。,.,4.2栅格数据结构,1.栅格数据结构的基本概念栅格数据结构:栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个栅格数据表示地物或现象的非几何属性特征。在一定尺度范围和特定分辨率的情况下，栅格结构表示的地表是不连续的，是量化和近似离散的数据。,.,什么是栅格数据结构（Raster)？,Realworld,Grid,Point,Line,Area,Value,=0=1=2=3,Row,Column,Triangles,Hexagons,RASTER,.,栅格数据单元格经常是矩形（主要是正方形）的，但并不是必须如此。其单元格形状可以随应用的需要进行具体设定，比如设置为三角形。栅格数据的比例尺就是栅格大小与地表相应单元大小之比。栅格尺寸越小，其分辨率越高，数据量也越大。,栅格数据的形状、尺寸及相关问题,引申思考：栅格数据的投影与变形问题？,.,栅格数据结构,栅格数据结构就是栅格阵列，每个栅格单元的行列号确定位置，用栅格单元的数值表示空间对象的类型、等级等属性特征。每个栅格单元只能存在一个属性值。,.,栅格数据结构：坐标系与描述参数,Y：列,X：行,西南角格网坐标（XWS，YWS）,格网分辨率,.,栅格单元像元遥感影像：MSS7979米SPOT1010米TM3030米QuickBird0.610.61米,影像分辨率,扫描图象：150DPI、300DPI、600DPI,计算机屏幕分辨率：6407808006001024768,.,IKONOS卫星多光谱影像（4米）（排队参观毛主席纪念堂的队伍隐约可见，花坛信息没有，背景草坪不清晰）,IKONOS卫星融合影像（1米）（排队参观毛主席纪念堂的队伍清晰可见，花坛和背景草坪显示出来，色调自然逼真，连纪念堂柱子的阴影都很清楚）,.,西班牙马德里体育场（0.61m）,.,点,线,面,栅格数据结构点：为一个栅格单元（像元）线：在一定方向上连接成串的相邻栅格单元集合面：聚集在一起的相邻栅格单元集合。,.,表示点,点使用离散分布的单个栅格单元来表示，单元格的值表示某个地理现象的属性，不同的值表示不同的地理对象或同一地理现象的不同属性。,.,表示线,单条线通过一系列有序相连的具有相同值栅格单元来表示，不同的值表示不同的地理对象或同一地理现象的不同属性。,.,表示多边形,单个面表示为一簇具有相同值的单元格，不同的值表示不同的地理对象或同一地理现象的不同属性,.,栅格数据结构示例,（a）点（b）线（c）面,.,由于栅格结构对地表的离散，在计算面积、长度、距离、形状等空间指标时，若栅格尺寸较大，则造成较大的误差（过度概化、不连续）。由于栅格单元中存在多种地物，而数据中常常只记录一个属性值，这会导致属性误差。比如，遥感数据中的“混合像元”问题。,栅格数据的相关问题,.,栅格数据单元值确定混合像元,百分比法,面积占优,重要性,中心点法,A连续分布地理要素,C具有特殊意义的较小地物,A分类较细、地物斑块较小,AB,为了逼近原始数据精度，除了采用这几种取值方法外，还可以采用缩小单个栅格单元的面积，增加栅格单元总数的方法,.,栅格数据单元值确定,问题：每一个单元可能对应多个地物种类或多个属性值。基本原则：在决定栅格代码时尽量保持地表的真实性，保证最大的信息容量。,.,决定栅格单元代码的方式,中心点法处理方法：用处于栅格中心处的地物类型或现象特性决定栅格代码常用于具有连续分布特性的地理要素，如降雨量分布、人口密度图等。,例如：中心点O落在代码为C的地物范围内，按中心点法的规则，该矩形区域相应的栅格单元代码为C,.,2.面积占优法处理方法：以占栅格区域面积比例最大的地物类型或现象特性决定栅格单元的代码面积占优法常用于分类较细，地物类别斑块较小的情况,例如：所示的例子中，显见B类地物所占面积最大，故相应栅格代码定为B,.,3.重要性法处理方法：根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码重要性法常用于具有特殊意义而面积较小的地理要素，特别是点、线状地理要素，如城镇、交通枢纽、交通线、河流水系等，在栅格中代码应尽量表示这些重要地物,例如：假设A类最重要的地物类型，即A比B和C类更为重要，则栅格单元的代码应为A,.,4.百分比法处理方法：根据栅格区域内各地理要素所占面积的百分比数确定栅格单元的代码适用于地物面积具有重要意义的分类体系,例如：可记面积最大的两类BA，也可以根据B类和A类所占面积百分比数在代码中加入数字,.,5.其他方法根据具体的应用内容，栅格单元的代码确定方式还可以采用其他方法，如插值方法（平均值就是其中之一），或使用特定的计算函数等。,.,栅格数据结构的特点,栅格数据结构结构容易实现，算法简单，且易于扩充、修改，也很直观，特别是易于同遥感影像的结合处理，给地理空间数据处理带来了极大的方便属性明显数据中直接记录了数据属性或指向数据属性的指针，因而我们可以直接得到地物的属性代码定位隐含所在位置则根据行列号转换为相应的坐标，也就是说定位是根据数据在数据集中的位置得到的。栅格结构是按一定的规则排列的，所表示的实体的位置很容易隐含在格网文件的存储结构中,.,2.栅格数据编码,栅格数据编码方法分为两大类：直接栅格编码（完全栅格数据结构）压缩编码方法链码游程长度编码块码四叉树,.,直接栅格编码,直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元进行记录，也可以奇数行地从左到右而偶数行地从右向左记录，为了特定目的还可采用其他特殊的顺序,.,一些常用的栅格排列顺序,.,栅格矩阵（RasterMatrix),数据是二维表面上地理数据的离散量化值，每一层的值组成像元阵列（即二维数组），其中行、列号表示它的位置。例如影像：AAAAABBBAABBAAAB在计算机内是一个4*4阶的矩阵。但在外部设备上，通常是以左上角开始逐行逐行存贮。如上例存贮顺序为：AAAAABBBAABBAAAB当每个像元都有唯一一个属性值时，一层内的编码就需要m行n列3(x,y和属性编码值)个存储单元。数字地面模型就属此种情况。,.,压缩编码方式,压缩编码目的：用尽可能少的数据量记录尽可能多的信息。基本思路：对于一个栅格图形，常常有行（列）方向上若干栅格单元具有相同的属性代码，因此可采取某种方法压缩那些重复的内容。,.,压缩编码方式,类型分为：信息无损编码编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息信息有损编码为了提高编码效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复在地理信息系统中的压缩编码多采用信息无损编码，而对原始遥感影像进行压缩时也可以采取有损压缩编码方法。,.,常见的栅格数据压缩存储的编码方法,起点行列号，单位矢量R:(1,5),3,2,2,3,3,2,3,链式编码,游程长度编码,逐行编码数据结构:行号,属性,重复次数1,A,4,R,1,A,3,块状编码,正方形区域为记录单元数据结构:初始位置,半径,属性(1,1,3,A),(1,5,1,R),(1,6,2,A),四叉树编码,.,压缩编码方式,1链码（ChainEncoding）链式编码又称为弗里曼链码（Freeman，1961）或边界链码。该编码方法将数据表示为由某一原点开始进行循迹并按某些基本方向确定的单位矢量链。基本方向定义为：东0，东南1，南2，西南3，西4，西北5，北6，东北7等八个基本方向。注意：图4.15方向定义,.,例如，确定原点为像元（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。其中前两个数字10和1表示起点为第十行第一列，从第三个数字开始每个数字表示单位矢量的方向，八个方向以07的整数代表。另例：图4.15，图4.16，表4.12，注意图4.15方向定义和循迹方式。,链码（ChainEncoding）,.,链码（ChainEncoding）,优点：链式编码对多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易，比较适于存储图形数据。缺点：对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的公共边界被重复存储会产生冗余。,.,2游程长度编码（Run-LengthEncoding）所谓游程（行程）是指按行（列）的顺序连续且属性值相同的若干栅格。游程长度的记录方式有两种记录每个游程象元数记录每个游程起（迄）列号,.,游程长度编码（Run-LengthEncoding）,其实现方法有两种一种编码方案是，只在各行（或列）数据的属性代码发生变化时依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。格式：（代码，重复个数）另一种游程长度编码方案就是逐个记录各行（或列）属性代码发生变化的位置和相应代码格式：（代码变化位置，代码）,.,游程长度编码示例,按第一种编码方法，此数据游程长度编码：（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，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）。,.,游程长度编码优缺点,优点压缩效率较高，且易于进行检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况缺点对于图斑破碎，属性和边界多变的数据压缩效率较低，甚至压缩后的数据量比原始数据还大。,.,3块码（BlockEncoding）块码（二维行程编码）是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。格式：（行号，列号，方块半径，代码）,.,块码编码示例,其块码编码为：(1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),(1,6,2,7),(1,8,1,7),(2,1,1,4),(2,4,1,4),(2,5,1,4),(2,8,1,7),(3,1,1,4),(3,2,1,4),(3,3,1,4),(3,4,1,4),(3,5,2,8),(3,7,2,7),(4,1,2,0),(4,3,1,4),(4,4,1,8),(5,3,1,8),(5,4,2,8),(5,6,1,8),(5,7,1,7),(5,8,1,8),(6,1,3,0),(6,6,3,8),(7,4,1,0),(7,5,1,8),(8,4,1,0),(8,5,1,0)。,.,块码编码示例,MMRMMMMM,12345678,12345678,MMRMMMMM,MMRRMRMM,MRRRRRRM,MRRRRRRM,MRRRRRRM,MRRRRRRM,MMRRRRRM,MMMRRMMM,MMRRMRMM,MRRRRRRM,MRRRRRRM,MRRRRRRM,MRRRRRRM,MMMRRMMM,MMRRRRRM,.,块码编码示例,1，1，2，M；1，3，1，R；1，4，1，M；1，5，1，M；1，6，1，M；1，7，2，M；2，3，2，R；2，5，1，M；2，6，1，R；3，1，1，M；3，2，1，R；3，5，3，R；3，8，1，M；4，1，1，M；4，2，3，R;4，8，1，M；5，1，1，M；5，8，1，M,MMRMMMMM,12345678,12345678,MMRRMRMM,MRRRRRRM,MRRRRRRM,MRRRRRRM,MRRRRRRM,MMMRRMMM,MMRRRRRM,.,4四叉树编码(QuadtreeEncoding),四叉树编码又称为四分树、四元树编码。它是一种更有效地压编数据的方法。它将2n2n像元阵列连续进行4等分，一直分到正方形的大小正好与象元的大小相等为止（如下图），而块状结构则用四叉树描述，习惯上称为四叉树编码。,.,四叉树编码,采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为2n2n的栅格阵列，对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为2n2n的图像。,.,四叉树编码,四叉树编码将整个图像区逐步分解为一系列仅包含单一属性类型的方形区域，最小的方形区域为一个栅格单元（象元）。其基本分割方法：将一幅栅格地图或图像等分为四部分。逐块检查其栅格属性值(或灰度)。如果某个子区的所有栅格值都具有相同的值。则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。,.,四叉树编码,MMRMMMMM,MMRRMRMM,MRRRRRRM,MRRRRRRM,MRRRRRRM,MRRRRRRM,MMRRRRRM,MMMRRMMM,12345678,12345678,区域分割方法,.,四叉树编码,在四叉树中，不能再分的结点称为叶结点，可再分的结点称为树杈结点,树杈结点,叶结点,12345678,12345678,.,四叉树编码,四叉树编码方法,NW（0）,NE（1）,NW（2）,SE（3）,0层,1层,2层,3层,自上而下，记录每个叶结点的地址和属性,0,1,2,3,20,21,22,23,200,201,202,203,230,231,232,233,.,四叉树编码,由上而下的方法运算量大，耗时较长。因而实践中可以采用从下而上的方法建立四叉树编码。对栅格数据按如下的顺序进行检测：如果每相邻四个栅格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快。,.,四叉树的结构方式,四叉树结构按其编码的方法不同分为常规四叉树和线性四叉树：常规四叉树：除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。,.,线性四叉树：只存贮最后叶结点的信息。包括叶结点的位置、深度和结点的属性值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的Morton码。,.,.,2,0,3,1,.,.,2,0,3,1,.,8,11,10,9,0,3,2,1,12,15,14,13,4,7,6,5,2,0,3,1,.,四叉树编码示例,.,四叉树编码的优缺点,优点：四叉树编码具有可变的分辨率，树的深度随数据的破碎程度而变化，并且有区域性质，压缩数据灵活，许多数据和转换运算可以在编码数据上直接实现，大大地提高了运算效率，并支持拓扑“洞”（嵌套多边形）的表达，是优秀的栅格压缩编码之一。缺点：其最大不足是其不稳定性，即同样的原始数据应用不同的算法进行编码可能会得到不同的编码结果。不利于数据分析。,.,5其他编码还有很多编码方法，如傅立叶变换、小波变换、余弦变换等，常常用于遥感原始数据的压缩。由于它们多数是有损压缩，一般不用于需要进行分析的栅格数据。在四叉树基础上发展而来的八叉树目前也是研究热点之一。,.,压缩编码的相关问题,同所有的数据结构问题一样，压缩编码过程的主要矛盾也是数据量压缩和运算时间之间的矛盾：为了更有效地利用空间资源，减少数据冗余，不得不花费更多的运算时间进行编码。好的压缩编码方法就是要在尽可能减少运算时间的基础上达到最大的数据压缩效率，并且是算法适应性强，易于实现,.,常见栅格压缩编码方法总结：,链码的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域运算困难。游程长度编码既可以在很大程度上压缩数据，又最大限度地保留了原始栅格结构，编码解码十分容易。但对破碎数据处理效果不好。块码和四叉树编码具有区域性质，又具有可变的分辨率，有较高的压缩效率，但运算效率是其瓶颈。其中四叉树编码可以直接进行大量图形图像运算，效率较高，是很有前途的方法。,.,栅格结构数据应用实例,遥感图像处理数字高程模型DEM与数字地形模型DTMDigitalElevationModelDigitalTerrainModel空间分析,.,栅格数据表示类型数字栅格图,数字栅格图ThisisaDigitialRasterGraphic(DRG)ofYorkPennsylvaniaNE.ADigitalRasterGraphic(DRG)isarasterimageofascannedUSGStopographicorplanimetricmapthatisgeoreferencedtoareal-worldcoordinatesystem.,.,栅格数据表示类型数字正射影像图,数字正射影像图ThisisDigitalOrthoQuarterQuaddrangle(DOQQ)ofYorkPennsylvania.Orthophotoscombinetheimagecharacteristicsofaphotograph(aerialphotos)withthegeometricqualitiesofamap.,.,栅格数据表示类型卫星影像图,卫星影像图ThisrasterisSPOTsatelliteImageryofS