GIS原理与应用3 空间数据结构与数据库ppt课件.ppt

《GIS原理与应用3 空间数据结构与数据库ppt课件.ppt》由会员分享，可在线阅读，更多相关《GIS原理与应用3 空间数据结构与数据库ppt课件.ppt（105页珍藏版）》请在三一办公上搜索。

1、第三章 空间数据结构与数据库,3-2,数据结构即指数据组织的形式，是适合于计算机存储、管理和处理的数据逻辑结构。对空间数据则是地理实体的空间排列方式和相互关系的抽象描述。 在地理系统中描述地理要素和地理现象的空间数据，主要包括空间位置、拓扑关系和属性三个方面的内容。,3-3,数据库结构,关系模型（relational model）满足一定条件的二维表格层次模型（hierarchical model）以记录类型为节点的有向树（tree），其主要特征是： （1）除根节点外，任何节点都有且只有一个“父亲”；（2）“父”节点表示的实体与“子”节点表示的实体是一对多的联系。网状模型（network mo

2、del） 特点：1）可以有一个以上的结点没有“父”结点； 2）至少有一个结点有多于一个“父”结点； 3）结点之间可以有多种联系； 4）可以存在回路,3-4,3-5,描述地理实体的数据本身的组织方法，称为空间数据的内部数据结构。基本上可分为两大类：,空间数据结构栅格数据结构(显式表示 )矢量数据结构(隐式表示 ),3.1 空间数据库结构,3-6,矢量图,栅格图,3-7,显式描述-栅格数据结构,显式表示：就是栅格中的一系列像元(点)，为使计算机认识这些像元描述的是某一物体而不是其它物体。注：“c”不一定用c的形式，而可以用颜色、符号、数字、灰度值来显示。则得到椅子的简单数据结构为： 椅子的属性符号

3、颜色像元x,3-8,隐式表示：由一系列定义了始点和终点的线及某种连接关系来描述，线的始点和终点坐标定义为一条表示椅子形式的矢量，线之间的指示字，告诉计算机怎样把这些矢量连接在一起形成椅子，隐式表示的数据为： 椅子的属性一系列矢量连接关系,隐式描述-矢量数据结构,3-9,一、栅格数据结构:,栅格结构是最简单最直观的空间数据结构，又称为网格结构(raster或grid cell)或象元结构(pixel)，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素,由行、列号定义，并包含一个代码,表示该象素的属性类型或量值。因此，栅格结构是以规则的阵列来表示空间地物或现象分布的数据组

4、织，组织中的每个数据表示地物或现象的非几何属性特征。,3-10,点、线、面数据的栅格表示,3-11,点,线,面,对于栅格数据结构点：为一个像元线：在一定方向上连接成串的相邻像元集合。面：聚集在一起的相邻像元集合。,3-12,栅格数据结构：坐标系与描述参数,Y：列,X：行,西南角格网坐标（XWS，YWS）,格网分辨率,3-13,栅格数据结构就是像元阵列，每个像元的行列号确定位置，用像元值表示空间对象的类型、等级等特征。每个栅格单元只能存在一个值。,（a）三角形,（b）,菱形,（c) 六边形,特点: 位置隐含,属性明显,栅格数据结构特点:,3-14,例如影像(4*4阶的矩阵)： A A A A A

5、 B B B A A B B A A A B最直接的存储方式: A A A A A B B B A A B B A A A B,存在的问题是?:当每个像元都有唯一一个属性值时，一层内的编码就需要m行n列3(x,y和属性编码值)个存储单元。,栅格数据结构特点:,特点: 数据结构简单,3-15,空间分析模型(叠加模型)计算简单:,面向位置的数据结构,难以建立空间对象之间关系,3-16,栅格数据组织(多层),3-17,栅格数据单元值确定,百分比法,面积占优,重要性,中心点法,A连续分布地理要素,C具有特殊意义的较小地物,A分类较细、地物斑块较小,AB,为了逼近原始数据精度，除了采用这几种取值方法外，

6、还可以采用缩小单个栅格单元的面积，增加栅格单元总数的方法,属性存在偏差:,3-18,几何偏差,属性偏差,几何特性存在偏差:,栅格数据单元几何特性,3-19,栅格数据结构特点总结：,离散的量化栅格值表示空间对象位置隐含,属性明显数据结构简单,易与遥感数据结合,但数据量大存在几何和属性偏差面向位置的数据结构,难以建立空间对象之间的关系,3-20,栅格数据的编码方法,直接栅格编码行程压缩编码链式数据编码分块压缩编码四叉树编码八叉树编码,3-21,直接栅格编码以行为记录单位按行存储地理数据。缺点：存在大量冗余，精度提高有限制。,3-22,栅格阵列,直接栅格编码,3-23,2. 游程压缩栅格编码（Run

7、-Length Encoding）将原始栅格矩阵中属性值相同的连续若干个单元映射为一个游程，每个游程的数据结构为（A，P），A表示属性值或属性值的指针，P代表该游程最右端的列号或个数。,原始栅格数据,(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),3-24,变长编码,3-25,游程长度编码(RunLengthCodes),游程长度编码是按行帧序存储多边形内的各个像元的列号，即在某行上从左至右存储属该多边

8、形的始末像元的列号。问：对左图的进行游程长度编码 。,3-26,3. 链式数据编码（Chain Encoding，弗里曼Freeman）链式编码主要是记录线状地物和面状地物的边界。它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：东0，东南l，南2，西南3，西4，西北5，北6，东北7等八个基本方向。,链式编码的方向代码,3-27,链式编码(ChainCodes),右图多边形编码为: 10，l，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

9、。,3-28,4、块码(BlockCodes),采用方形区域作为记录单元，数据编码由初始位置行列号加上半径，再加上记录单元的代码组成。,（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，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

10、，6，3，3）；（7，4，1，0），（7，5，1，3）；（8，4，1，0），（8，5，1，0）。,3-29,块式编码是将游程长度编码扩大到二维的情况，把多边形范围划分成由像元组成的正方形，然后对各个正方形进行编码。如图：,块式编码的数据结构由初始位置(行号，列号)和半径，再加上记录单元的代码组成。根据这一编码原则，上述多边形只需17个单位正方形。9个4单位的正方形和1个16单位的正方形就能完整表示，总共要57个数据，其中27对坐标，3个块的半径。,4、块码(BlockCodes),3-30,5、四叉树编码,是根据栅格数据二维空间分布的特点，将空间区域按照4个象限进行递归分割（2n2 n，且n1

11、），直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。四叉树分解，各子象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，它对应于整个图形。不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。 为了保证四叉树分解能不断的进行下去，要求图形必须为2n2 n的栅格阵列。n 为极限分割次数，n1是四叉树最大层数或最大高度,3-31,四叉树编码又称为四分树、四元树编码。它是一种更有效地压编数据的方法。它将2n2n像元阵列连续进行4等

12、分，一直分到正方形的大小正好与象元的大小相等为止（如下图），而块状结构则用四叉树描述，习惯上称为四叉树编码。,5、四叉树编码,3-32, ,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,36,37,38,39,34,35,40,0 0 0,0 3 3 3 0 3 3 3,3 3 5 3 0 0 2 2,2 3 2 2 2 2 0 2,2 2 2 5 2 5 5 5,3 3,3 5 5,西南,东南,西北,东北,四叉树编码思路,3-33,3-34,3-35,3-36,四叉树编码方法,常规四叉树,线性四叉树,

13、3-37,常规四叉树,存储4个叶结点,一个父指针,一个属性; 结点之间借助指针联系.,缺点：数据存储量较大，操作比较复杂；主要用在数据索引和图幅索引等方面,3-38,只存储最后叶结点的信息,含结点的位 置、深度和属性。,线性四叉树,特点：数据存储量大大减少，应用广泛,3-39,线性四叉树编码方法,（1）基于四进制的编码方法,对一个nn（n=2k，k1）的栅格方阵组成的区域作第一次分割。得到四个子象限，即：,3-40,第二次分割：,标号的位置随着分割的进行而不断增加，标号即Morton码(Mq)，Mq的每一位都不大于3；,3-41,最后的编码：,这种自上而下分割的方法需要大量重复运算，因而应用得

14、比较少。,3-42,思路：将栅格矩阵的每个元素的下标转换成Morton码，并将元素按码的升序排列成线性表：,自下而上的编码方法：, 将十进制的行列号转换成二进制表示，然后计算每个栅格单元的Morton,3-43,列号,行号,基于四叉树的Morton码,3-44, 按照码的升序排成线性表, 在排好序的线性表中，依次检查四个相邻的MQ码对应的栅格值，如果相同则可合并为一个大块，否则将四个格网值记盘，内容包括MQ码、深度和格网值。这一轮检测完成后依次检查四个大块的格网值，如相同就再合并，不同则分别记盘。如此循环，直到没有能够合并的子块为止。,3-45,（2）基于十进制的线性四叉树编码方法,基于四进制

15、的线性四叉树直观上很切合四叉树的分割， 但大部分语言不支持四进制变量，需要用十进制的长整型量表示Morton码，这是一种浪费； 同时线性表的排序过程也要花费较多的时间。,基于十进制的编码MD, 十进制表示的行、列号的二进制数分别为：,II=,JJ=, II，JJ的二进制数交叉结合, 将得到的二进制数转换为十进制即可,3-46,列号,行号,3-47,还存在什么问题？,3-48,特点:1）容易而有效地计算多边形的数量特征；2）阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；3）栅格到四叉树及

16、四叉树到简单栅格结构的转换比其它压缩方法容易；4）多边形中嵌套异类小多边形的表示较方便。,5、四叉树编码,3-49,（一）、三维GIS发展的需要,目前GIS主要处理地球表面的数据，若数据是地表以下或以上，则先将它投影到地表，再进行处理，其实质是以二维的形式来模拟、处理任何数据（DEM），在有些领域可行，但涉及到三维问题的处理时，往往力不从心。,真三维模型V=f(x,y,z)，三维GIS的要求与二维GIS相似，但在数据采集，系统维护和界面设计等方面比二维GIS复杂得多。,6、八叉树编码,3-50,栅格数据结构：将地理实体的三维空间分成细小单元-体元。普遍用八叉树 矢量结构：x,y,z，抽象为点、

17、线、面、体，面构成体。方法多种，常用三维边界表示法。,（二）、三维数据结构,3-51,八叉树结构的思想： 四叉树在三维空间的推广。 将要表示的形体V放在一个充分大的正方体C内，C的边长为2n，不断用两个与XOY、XOZ的平面均分C为8个子体，并判断属性单一性。 当子体部分为V-灰结点 需再1分为8。 子体中无V-白结点 停止分割，叶结点。 子体全为V黑结点,1、栅格结构-八叉树结构,3-52,八叉树结构就是将空间区域不断地分解为八个同样大小的子区域(即将一个六面的立方体再分解为八个相同大小的小立方体)，同区域的属性相同。八叉树主要用来解决地理信息系统中的三维问题。,2）示例,3-53,存储结构

18、,1）规则八叉树 与常规四叉树类似，用10项字段来记录每个结点（8个子结点指针， 1个父结点指针，1个结点属性）。指针占总存储量的94%，空间使用率低。,特点：节省存贮空间，便于某些运算，但丧失一定的灵活性，不便于其它遍历方式对树的结点进行存取，应用效果不佳。,2）线性八叉树 Morton码 用某一预先确定的次序将八叉树转换成一个线性表，表中的每个元素与一个结点相对应。每个结点用固定的字节描述，其中某些位专门用来说明它是否为叶结点。,3-54,3）一对八式的八叉树,每个结点均1分为8，并标记为 0，1，2，3，4，5，6，7。隐含地假定了这些子结点记录存放的次序 -便于检索，浪费存储，除非完全

19、八叉树，即所有叶结点均在同一层次出现，上层均为非叶结点。,3-55,、面表：给出围成多面体某个面的各条边。,、当有若干个多面体时，还必须有一个对象表。,1、顶点表：用来表示多面体各顶点的坐标,、边表：指出构成多面体某边的两个顶点；,可避免重复表示某些点、边、面，节约存储，便于图形显示，如公共边不重复。缺点？,2、矢量结构-三维边界表示法,3-56,为表达拓扑还可将其它一些有关的内容结合到所使用的表中，如将边所属的多边形信息结合进边表中以后的形式：,包含s1,s4公共边为l1的信息,2、矢量结构-扩充后的边表,3-57,三维边界法一般用于表示规则形体，如建筑物； 对于不规则形体，可在形体的外表面

20、s，测一组点p1,p2pn坐标，再建这些点的关系，即结构图，决定顶点连接的不同方式。同样数据点，由于连接方式不同，构成的平面多面体也不同。如类似TIN结构。或在研究体的相关特征之后，采取逼近的方法： 表面S0的逼近：以确定后的平面多面体的表面作为对原三维形体的表面S0的逼近，着眼于形体的边界表示。 三维形体的逼近：给出一系列的四面体，这些四面体的集合就是对原三维形体的逼近。着眼于形体的分解表示。,3、具体应用,3-58,栅格数据压缩存储的编码方法,起点行列号，单位矢量R: (1,5),3,2,2,3,3,2,3,链式编码,游程长度编码,逐行编码数据结构: 行号, 属性, 重复次数A, 4, R

21、, 1, A, 6,.,块状编码,正方形区域为记录单元数据结构: 初始位置, 半径, 属性(1,1,3,A),(1,5,1,R),(1,6,2,A),四叉树编码,3-59,二、矢量数据结构:,是较为常用的一种表示空间数据的方法，它是通过记录地理实体坐标的方式精确地表示点、线、面等实体的空间位置和形状。,3-60,矢量数据结构,点实体:包括由单独一对x，y坐标定位的一切地理或制图实体。 线实体:可以定义为直线元素组成的各种线性要素，直线元素由两对以上的x，y坐标定义。 面实体: 多边形、区域,3-61,3-62,3-63,3-64,矢量数据结构,1.实体型数据结构,2.索引编码,3.双重独立式（

22、DIME）,4.链状双重独立式,f,g,h,i,3-65,1、实体式,实体式数据结构是指构成多边形边界的各个线段，以多边形为单元进行组织，边界数据和多边形单元实体一一对应，各个多边形边界都单独编码。,3-66,3-67,实体式编码的特点：,优点： 编码容易,数字化操作和数据编排简单;缺点: 公共边界数字化2遍,造成数据冗余,可能导致输出的公共边界出现裂隙或重叠; 缺少多边形的邻域信息和图形的拓扑信息; 岛只作为一个单个图形,没有建立与外界多边形的联系.,3-68,2、索引式,对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构.,

23、3-69,线与多边形之间的树状索引,点与线之间的树状索引,3-70,索引式编码的特点：,优点： 消除了相邻多边形边界的数据冗余； 解决了坐标数据的不一致问题;缺点: 编码表需要人工建立，容易出错； 相关运算比较复杂（如公共边的查询）；,3-71,3、双重独立式,美国人口统计局研制，用来进行人口普查分析和制图，简称为DIME（Dual independent Map Encoding）系统或双重独立式的地图编码法，它以城市街道为编码的主体，其特点是采用了拓扑编码结构。,3-72,3-73,4、链状双重独立式,链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点

24、的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。编码需要建立文件： 结点文件； 弧段坐标文件； 弧段文件； 多边形文件。,3-74,弧段坐标文件,弧段文件,3-75,多边形文件,3-76,三、矢量数据模型与栅格数据模型比较,3-77,四、矢量结构与栅格结构的相互转换,矢量数据结构向栅格数据结构的转换 栅格数据结构向矢量数据结构的转换,3-78,（一）、矢量到栅格栅格化过程包括以下操作：1）确定栅格矩阵(行列数分辨率)；2）点的变换3）线的变换4)多边形的变换(面的变换),3-79,栅格尺寸的大小要尽量满足精度要求，使之不过多地损失地理

25、信息。为了提高精度，栅格需要细化，但栅格细化，数据量将以平方指数递增，因此，精度和数据量是确定栅格大小的最重要的影响因素。,确定栅格单元的大小,确定矢量转换成栅格坐标系；,确定栅格尺寸大小；,3-80,1、矢量数据结构向栅格数据结构的转换,在转换之前需要确定栅格单元的大小，栅格单元的大小又称为栅格图像的分辨率。直接决定了矢量数据的精度。,M=| Ymax-Ymin|/dyN=|Xmax-Xmin|/dx,3-81,X,Y,点的栅格化；,3-82,线的栅格化转换,曲线或折线是由直线段组成或逼近的。只要了解直线转换的方法即可。,设某一线段两端点的坐标为(xA,yA)和(xB,yB)且yByA，线段

26、两端点所在栅格的行列号分别为IA,JA和IB,JB。点(xi,yi)为直线段经过的中间栅格的水平中心线与该直线段交点的坐标，则：,3-83,3) 矢量化： 找出线段经过的所有栅格； 将栅格的（i，j）坐标变成直角坐标（ x，y）; 剔除中间点； 保存；,3-84,面域栅格化（边界）,3-85,算法较多，有内部点扩散法、复数积分算法、射线算法、边界代数充填算法。,1）内部点扩散算法该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界上，则该新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该

27、种子点赋以该多边形的编号。重复上述过程直到所有种子点填满该多边形并遇到边界停止为止。扩散算法程序设计比较复杂，,2）复数积分算法对全部栅格阵列逐个栅格单元地判断该栅格归属的多边形编码，判别方法是由待判点对每个多边形的封闭边界计算复数积分，对某个多边形，如果积分值为2r，则该待判点属于此多边形，赋以多边形编号，否则在此多边形外部，不属于该多边形。,面域栅格化（内部的充填）,3-86,3）射线算法 射线算法可逐点判断数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形外部，如为奇数次，则待判点在该多边形内部。采用

28、射线算法，要注意的是：射线与多边形边界相交时，有一些特殊情况会影响交点的个数，必须予以排除。,射线算法,3-87,射线算法的特殊情况,3-88,4边界点跟踪算法(扫描算法)多边形边界的栅格单元确定后，从边界上的某栅格单元开始，按顺时针方向跟踪单元格，以保证多边形位于前进方向的右方。将边界经过的每个格网赋予字符R、L、N中的一个，直至回到起始点。其中R代表右，行数一直增加的单元为R；L代表左，行数一直减少的单元为L；N代表中，与相邻单元行数相同或出现极值现象的单元均赋值N。最后逐行扫描，以多边形同一属性值充填所有与之间的栅格单元。对于多边形中的岛，则按逆时针方向跟踪。这样，岛区内将不充填。,3-

29、89,5）边界代数算法（BAF-Boundary Algebra Filling）边界代数多边形填充算法是一种基于积分思想的矢量格式向栅格格式转换算法，它适合于记录拓扑关系的多边形矢量数据转换为栅格结构。下图表示转换单个多边形的情况，多边形编号为a，模仿积分求多边形区域面积的过程，初始化的栅格阵列各栅格值为零，以栅格行列为参考坐标轴，由多边形边界上某点开始顺时针搜索边界线，当边界上行时，位于该边界左侧的具有相同行坐标的所有栅格被减去a；当边界下行时，该边界左边（前进方向看为右侧）所有栅格点加一个值a，边界搜索完毕则完成了多边形的转换。,单个多边形的转换,3-90,从栅格单元转换到几何图形的过程

30、称为矢量化，矢量化过程要保证以下两点：1）拓扑转换，即保持栅格表示出的连通性与邻接性；2）转换物体正确的外形。,（二）栅格到矢量,3-91,（二）、栅格数据结构向矢量数据结构的转换,多边形边界提取边界线追踪拓扑关系生成去除多余点及曲线圆滑,3-92,多边形边界提取 二值化 细化,3-93,边界点和内部点,边界点的6种情况,结点的8种情况,如果窗口内4个栅格值相同，则为内部点，若有两种栅格值，则为边界点，若有三种栅格值，则为结点。,3-94,2) 细化: 将占有多个栅格宽的图形要素缩减为只有1个像素。,剥皮法 每次剥掉一层，最后只留下彼此连通的由单个栅格组成的图形。其原则是不允许剥去会导致图形不

31、连通的栅格，也不能在图形中形成孔,原则：保持图形的连通性，不能在图形中形成孔。,3-95,骨架法确定图像的骨架，将非骨架上的多余栅格删除，方法是扫描全图，凡是像元值为1的栅格都用V值代替，计算各栅格的V值，最后在保证连通的基础上，保留最大的V值,3-96,（二）栅格数据结构向矢量数据结构的转换,边界线追踪：边界线跟踪的目的就是将写入数据文件的细化处理后的栅格数据，整理为从结点出发的线段或闭合的线条，并以矢量形式存储特征栅格点中心的坐标拓扑关系生成：对于矢量表示的边界弧段，判断其与原图上各多边形空间关系，形成完整的拓扑结构，并建立与属性数据的联系。去除多余点及曲线圆滑：由于搜索是逐个栅格进行的，

32、必须去除由此造成的多余点记录，以减少冗余。,3-97,矢量格式和栅格格式的相互转换,矢量格式向栅格格式的转换内部点扩散法复数积分算法射线算法扫描算法边界代数算法栅格格式向矢量格式的转换多边形边界提取边界线追踪拓扑关系生成去除多余点及曲线圆滑,3-98,一、矢栅一体化概念,四、矢栅一体化数据结构,将矢量面对目标的方法和栅格元子充填的方法结合起来，具体采用填满线状目标路径和充填面状目标空间的方法作为一体化数据结构的基础。线状地物：除记录原始取样点外，还记录路径所通过的栅格。面状地物：除记录它的多边形周边以外，还包括中间的面域栅格。一方面，它保留了矢量的全部性质，以目标为单元直接聚集所有的位置信息，

33、并能建立拓扑关系；另一方面，它建立了栅格与地物的关系，即路径上的任一点都直接与目标建立了联系。,3-99,二、三个约定和细分格网法,为便于组织数据，首先作如下约定：a. 地面上的点状地物是地球表面上的点，它仅有空间位置，没有形状和面积，在计算机内部仅有一个位置数据。,为提高栅格表示精度，采用细分格网法：将一对X,Y坐标用两个Morton码代替：前一M1表示该点（采样点或附加的交叉点）所在基本格网的地址码，后者M2 表示该点对应的细分格网的Morton码，既顾全整体定位，又保证精度。,b. 地面上的线状地物是地球表面的空间曲线，它有形状但没有面积，它在平面上的投影是一连续不间断的直线或曲线，在计

34、算机内部需要用一组元子填满整个路径。,c. 地面上的面状地物是地球表面的空间曲面，并具有形状和面积，它在平面上的投影是由边界包围的紧致空间和一组填满路径的元子表达的边界组成。,x,y,M1 M2,3-100,三、一体化数据结构设计,线性四叉树(Morton)是基本数据格式，三个约定设计点、线、面数据结构的基本依据，细分格网法保证足够精度。,约定1，点仅有位置、没有形状和面积，只要将点的坐标转化为地址码M1 和M2 ,结构简单灵活，便于点的插入和删除，还能处理一个栅格内包含多个点状目标的情况。,1、点状地物和结点的数据结构,3-101,2、线状地物的数据结构,约定（2），线状地物有形状但没有面积

35、，没有面积意味着只要用一串数据表达每个线状地物的路径即可，将该线状地物经过的所有栅格的地址全部记录下来。仿照矢量数据组织的链状双重独立式编码，以弧段为记录单位。,弧段的数据结构:,线状地物的数据结构:,3-102,3、面状地物的数据结构,1) 弧段文件,2）带指针的二维行程码,叶结点的属性值,改为指向该地物的下一个子块的循环指针,边界弧段-表示形状,面域:填充,循环指针指向该地物下一个子块的地址码，并在最后指向该地物本身,3-103,用循环指针将同属于一个目标的叶结点链接起来,只要进入第一块就可以顺着指针直接提取该地物的所有子块，从而避免像栅格数据那样为查询某一个目标需遍历整个矩阵，大大提高了查询速度。,0,8,32,40,46,3-104,3）面文件,这种数据结构是面向地物的，具有矢量的特点。通过面状地物的标识号可以找到它的边界弧段并顺着指针提取所有的中间面块。同时它又具有栅格的全部特性，二维行程本身就是面向位置的结构，带指针的二维行程码中的Morton码表达了位置的相互关系，前后M码之差隐含了该子块的大小。给出任意一点的位置都可顺着指针找到面状地物的标识号确定是哪一个地物。,3-105,4、复杂地物的数据结构,由几个或几种点、线、面状简单地物组成的地物称为复杂地物。例如将一条公路上的中心线、交通灯、立交桥等组合为一个复杂地物，用一个标识号表示。复杂地物的数据结构如表7所示。,