空间数据结构及编码.ppt

《空间数据结构及编码.ppt》由会员分享，可在线阅读，更多相关《空间数据结构及编码.ppt（110页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第二章 空间数据结构及编码1、从现实世界到计算机世界概念模型数据模型数据结构文件格式四个层次现实世界用户认识 局部抽象概念模型-面向用户数据模型-面向机器按照著名数据库专家E.F.Codd的理论认为数据模型实质上是一组为用户服务的规则,这些规则规定其数据结构如何组织以及应当允许进行何种操作。一 基本概念2.Gis中地理空间数据组织的主要对象 从地理空间现象或事物到计算机世界,一般也要有概念模型,数据模型,数据结构和文件格式几个层次.这个过程有时统称为地理空间数据建模Gis怎样组织数据以模拟地理事物和现象的呢?举例 我们将gis所抽象,表达的地理事物和现象,称为空间对象;空间对象的位置相互关系,

2、称为空间关系a空间对象 点状空间对象(0维对象)线状空间对象 面状空间对象 体状空间对象除空间维数特性外,空间对象还可以从其复杂性,规则性,人为性等角度认识和区分b空间关系通常分为3类 度量空间关系 顺序空间关系 拓扑空间关系-连接性-包含-邻接性3.空间数据结构和空间数据模型两个概念之间的关系 空间数据结构和空间数据模型研究地理空间数据组织和管理.两者之间的关系,与一般的数据结构和数据模型的关系有两点相似之处.其一,空间数据结构所作的数据组织工作,比空间数据模型更基层些,它偏重数据表达的物理实现,而空间数据模型涉及到空间数据管理的层次.其二，同普通数据的数据模型一样,空间数据模型的命名通常与

3、相应的空间数据结构相同.4.空间分析与非空间分析5.空间数据 定义 特点：数据的空间性 数据的属性 数据的时间性6.空间数据的编码7.空间数据的拓扑关系地理要素之间的空间区位关系可抽象为点、线（或弧）、多边形（区域）之间的空间几何关系，其关系如下 欧氏平面上实体对象所具有的拓扑和非拓扑属性 拓扑属性 一个点在一个弧段的端点一个弧段是一个简单弧段（弧段自身不相交）一个点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的外部一个点在一个环的内部一个面是一个简单面（面上没有“岛”）一个面的连续性（给定面上任意两点，从一点可以完全在面的内部沿任意路径走向另一点）非拓扑属性两点之间的距离一个点指

4、向另一个点的方向弧段的长度一个区域的周长一个区域的面积弧属性表（AAT）多边形属性表（PAT）#id 多边形标识码 周长 面积1 0 8.418-4.5062 104 8.596 2.0783 102 4.296 1.1444 101 2.233 0.3015 103 4.325 0.983id 弧标识码 起始结点 终到结点 弧左多边形 弧右多变形 弧长1 38 3 1 3 2 1.5152 33 4 3 3 5 1.0403 35 4 1 1 3 2.1064 37 2 2 2 4 2.2335 36 1 5 1 2 4.1206 39 5 3 5 2 1.0937 34 4 5 5 1 2

5、.1931.本图有多少个多边形和弧？2.哪个多边形是包含于另一个中？3.哪个多边形和多边形102相邻？4.手工建立一个简单示意图表明本图的空间格局二、栅格数据结构 定义：又称为网格结构，它是将地表划分成为紧密相邻的网格阵列。每个网格的位置由行列号定义。它包含一个代码，以表示该网格的属性或指向属性记录的指针。注意：栅格数据模型是将连续空间离散化，即用二维铺盖或划分覆盖整个连续空间，这种铺盖可以分为规则的和不规则的1.概念三角形、方格和六角形划分 栅格数据模型 2.图形栅格数据结构表示0 0 0 0 2 0 0 00 0 0 2 0 0 0 00 1 0 2 0 3 3 00 0 0 2 3 3

6、3 30 0 2 0 3 3 3 30 0 2 0 0 3 3 00 2 0 0 0 0 0 0线 面 点3.决定栅格单元代码的方式 面积占优法 中心点法 重要性法 4.栅格结构编码方式 直接栅格编码 行程编码 块码 链式编码 四叉树结构 二维行程编码基本思路：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。游程长度编码（Run-Length Codes）1）只在各行（或列）数据的代码发生变化时依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。两种方案（属性值，长度）例如（0，1）,（4，2）,（7，5）；（4，5）,

7、（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）。0 7 4 44 4 4 47 7 7 74 7 7 74 4 4 4 8 7 7 80 8 4 0 8 7 7 80 8 8 00 8 0 08 8 7 88 8 8 80 0 0 0 8 8 8 80 0 0 0 0 8 8 8压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高44：64 2）逐个记录各行（或列）

8、代码发生变化的位置和相应代码编码如下（沿列方向）（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）。（属性值，属性发生变化的位置）0 7 4 44 4 4 47 7 7 74 7 7 74 4 4 4 8 7 7 80 8 4 0 8 7 7 80 8 8 00 8 0 08 8 7 88 8 8 80 0 0 0 8 8 8 80 0 0 0 0 8 8 8 特点：属性的变化愈少，行

9、程愈长，则压缩的比例越大，压缩比与图的复杂程度成反比。块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。块 码对图所示图像的块码编码如下：(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,

10、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)。0 7 4 44 4 4 47 7 7 74 7 7 74 4 4 4 8 7 7 80 8 4 0 8 7 7 80 8 8 00 8 0 08 8 7 88 8 8 80 0 0 0 8 8 8 80 0 0 0 0 8 8 8该例中块码用了120个整数，比直接编码还多，这是因为例中为描述方便，栅格划分很粗糙，在实际应用中，栅格划分细，数据冗余多的

11、多，才能显出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少数据冗余。块码具有可变的分辨率，即当代码变化小时图块大，就是说在区域图斑内部分辨率低；反之，分辨率高。块码与游程长度编码相似，随着图形复杂程度的提高而降低效率，就是说图斑越大，压缩比越高；图斑越碎，压缩比越低。块码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而在某些操作时，则必须把游程长度编码和块码解码，转换为基本栅格结构进行。链码（Chain Codes）链码又称为弗里曼链码Freeman或边界链码，链码可以有效地压缩栅格数据，而且对于估算

12、面积、长度、转折方向的凹凸度等运算十分方便，比较适合于存储图形数据。缺点是对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界将被重复存储而产生冗余。基本思想：将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值（或灰度），如果某个子区的所有格网值都相同，则这个子区就不再继续分割，否则还要把这个子区再分割，直到每个子块都只含有相同的属性值或灰度为止。四叉树结构四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一1）从四叉树的特

13、点可知，一幅2n*2n 栅格阵列图，具有的最大深度数为n，可能具有的层次为0，1，2，.n注 意2）每一层的栅格宽度，即每层边上包含的最大栅格数，反映了所在叶结点表示的正方形集合的大小，其值为：2（最大深度-当前层次）例如：一幅23 23 的栅格阵列，它具有的最大深度为3，可能层次分别为0，1，2，3。其中：第0层边长上的最大栅格数为2（3-0）8 第1层边长上的最大栅格数为2（3-1）4 第2层边长上的最大栅格数为2（3-2）2 第3层边长上的最大栅格数为2（3-3）11 1 1 1 0 0 0 01 1 1 1 0 0 0 01 1 1 0 0 0 0 01 1 1 0 0 0 0 03

14、3 4 4 4 0 0 03 3 4 4 4 0 0 03 3 4 4 0 0 0 03 3 4 4 0 0 0 01 1 01 1 01 03 4 4 0 04 03 4 0 00层1层2层3层（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达，即四个叶结点指针、一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据储存量，而且增加了操作的复杂性。常规四叉树与线性四叉树 线性四叉树只存储最后叶结点的信息。包括

15、叶结点的位置、深度和本结点的属性或灰度值 线性四叉树叶结点的编号需要遵循一定的规则，这种编号成为地址码，它隐含了叶结点的位置和深度信息。a.基于深度和层次码的线性四叉树的编码 它是通过记录叶结点的深度码和层次码来描述叶结点的位置码几种线性四叉树的编码1 1 1 1 0 0 0 01 1 1 1 0 0 0 01 1 1 0 0 0 0 01 1 1 0 0 0 0 03 3 4 4 4 0 0 03 3 4 4 4 0 0 03 3 4 4 0 0 0 03 3 4 4 0 0 0 01 1 01 1 01 03 4 4 0 04 03 4 0 00层1层2层3层（1）（2）（3）（4）（5）

16、（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）该地址码的十进制为：？层次码 深度码第一层 第二层 第三层00 11 11 00110层1层2层3层（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）b.基于四进制的线性四叉树编码0层1层2层3层（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）第一层 第二层 第三层0 3 3思 考 请为23 23 栅格阵列中的每个栅格建立基

17、于四进制的四叉树编码方式的地址码？你能找出何种规律？000 001 010 011 100 101 110 111000 000 001 010 011 100 101 110 111001 002 003 012 013 102 103 112 113010 020 021 030 031 120 121 130 131011 022 023 032 033 122 123 132 133100 200 201 210 211 300 301 310 311101 202 203 212 213 302 303 312 313110 220 221 230 231 320 321 330 3

18、31111 222 223 232 233 322 323 332 333 先将栅格的行列号转换为二进制，得二进制行号Iyb，列号Ixb，则M=2IybIxb 如结点7：M=2*011+011033 如果知道基于四进制四叉树编码方式的地址码，你能知道它的行列号码吗？思 考 若该位的编码值为0，1，则行号Iyb值为0；若该位的编码值为2，3，则行号Iyb值为1；若该位的编码值为0，2，则列号Ixb值为0；若该位的编码值为1，3，则列号Ixb值为1；如：M码为：1 0 3 二进制行值Iyb为：0 0 1 二进制列值Ixb为：1 0 1000 001 010 011 100 101 110 1110

19、00 000 001 010 011 100 101 110 111001 002 003 012 013 102 103 112 113010 020 021 030 031 120 121 130 131011 022 023 032 033 122 123 132 133100 200 201 210 211 300 301 310 311101 202 203 212 213 302 303 312 313110 220 221 230 231 320 321 330 331111 222 223 232 233 322 323 332 333000 001 010 011 100 1

20、01 110 11100000 01 100101002030 031011 032 03310020 21300 30131101 302 30311022 23 32 33111规则：首先将二维栅格数据的行列号转换为二进制，然后交叉放入Morton码中，即为线性四叉树的地址码：行号5（1 0 1）；列号7（1 1 1）Morton 1 1 0 1 1 155c.基于十进制的线性四叉树编码 请快速建立 8*8 栅格阵列中的每个栅格的 Morton思 考000 001 010 011 100 101 110 111000 0 1 4 5 16 17 20 21001 2 3 6 7 18 19

21、 22 23010 8 9 12 13 24 25 28 29011 10 11 14 15 26 27 30 31100 32 33 36 37 48 49 52 53101 34 35 38 39 50 51 54 55110 40 41 44 45 56 57 60 61111 42 43 46 47 58 59 62 63M码 属性值0 04 05 06 07 48 012 4.二维行程编码二维行程编码再议游程编码a.定义 游程编码结构 游程指相邻同值网格的数量，游程编码结构是逐行将相邻同值的网格合并，并记录合并后网格的值及合并网格的长度，其目的是压缩栅格数据量，消除数据间的冗余。游程

22、编码结构的建立方法是：将栅格矩阵的数据序列X1,X2,X3.XN，映射为相应的二元序列（Ai，Pi），i1，k，且k=n.其中，A为属性值，P为游程，k为游程序号2 2 5 52 7 5 57 7 7 55 5 5 5序号 二元组序列1（2，2）2（5，2）3（2，1）4（7，1）5（5，2）6（7，3）7（5，5）二元映射 这种结构特别适合于二值图数据的表示，如图1 1 1 1 11 1 0 0 00 0 1 1 11 1 0 0 00 1 1 1 1序号 二元组序号1（1，7）2（0，5）3（1，5）4（0，4）5（1，4）二元映射 b.游程编码能否压缩数据量，主要决定于栅格数据的性质，通

23、常可通过事先测试，估算图层的数据冗余度Re：Re 1Q/(MN)Q：图层内相邻属性值变化次数的累加和M：为图层网格的行数N：为图层网格的列数当的值大于1/5的情况下，表明栅格数据的压缩可取得明显的效果c.当栅格数据位数字高程时 当栅格数据为规则的数字地形高程即DEM时，由于这种类型数据的相邻的数据具有高度的相关性，可通过差分映射进行预处理，然后在采用游程长度压缩编码法。例如2 4 6 83 5 7 82 4 6 82 5 8 112 2 2 23 2 2 12 2 2 22 3 3 323 2 122 3差分d.基于游程编码结构的栅格数据文件的数据组织方式 为了提高系统对这些数据的访问效率，通

24、常采用索引顺序文件的方法来组织数据。当由位置参数访问其属性特征时，利用逻辑顺序和逻辑地址的关系，很快在索引文件中找到指向数据文件欲访栅格的指针，并求出其逻辑地址，就能找到该栅格的属性。栅格行序号 逐行游程累计数0102.10037.572游程序号 编码值0001000200030004.0007.0572R1R2R3R4.R7.R572索引文件数据文件5.多重属性下的栅格数据模型数据文件像元1X 坐标Y 坐标层1属性层2属性层3属性层n属性像元2像元n以像元为记录的序列。优点：因为n层中每个像元实际是只存储了一层的像元坐标，节约存储空间；每个网格单元的多主题或多层之间比较相对容易实现。不足之处

25、在于不能完全各主题的空间关系，即由于每个网格单元位置单独编码，要比较不同层的网格单元组是很困难的 以层为基础，每一层又以像元顺序记录它的坐标和属性值，一层记录完后再记录第二层。这种方法较为简单，但需要的存贮空间最大。数据文件层1x坐标Y坐标属性值像元2像元n像元1层2层n 以层为基础，但每一层内则以多边形（也称制图单元）为序记录多边形的属性值和充满多边形的各像元的坐标。数据文件层1属性值多边形2多边形n多边形1层2层n像元1坐标像元2坐标像元n坐标 图形文件如：TIFF、GIF、JPEG文件可用各种图像压缩算法作均称压缩，TIFF和GIF文件用无损压缩，使原图被精确重构，而JPEG采用有损压缩

26、，它可达到很大的压缩比，但不能完整重构原图像。课 内 作 业一、右图 1.以第3行，第5列为例说明如何将二维删格数据的行列号转换为Morton码 2.就下列删格数据建立十进制线性四叉树表和二维行程编码表 二、举例说明：与块码相比，四叉树在表示栅格结构时有何不足？0 0 4 40 0 4 45 4 4 04 4 0 0 三、编写程序，实现以下功能 1）将直接栅格编码文件转换为RLE格式文件 2）将RLE栅格数据文件转换为线性四叉树编码文件（基于十进制的线性四叉树编码）课 外 作 业（a）块码分割（b）四叉树分割小知识点 栅格数据类型 卫星影像 数字高程模型 数字正射影像 二进制扫描文件 数字栅格

27、图形 图形文件 特定地理信息系统软件的栅格数据小知识点 栅格数据文件 为导入要用的栅格数据，GIS软件包必须有数据结构和压缩方法的信息。此类信息通常包含在头文件中，头文件的功能类似于元数据。例如：卫星影像的头文件（常以.hdr为扩展名）包含了有关影像数据的信息，如数据结构方法，行列数，光谱波段数，每个波段每一像元的比特数。三、矢量数据结构1.概念 矢量结构：即通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体.注意：由于坐标空间设为连续，所以允许任意位置、长度和面积的精确定义。但是，其精度仅受数字化设备的精度和数值记录字长的限制，在一般情况下，比栅格结构精度高得多。矢量数据模型 对于点

28、实体（0维对象），没有长度和宽度 只记录其在特定坐标系下的坐标和属性代码；线实体（1维对象），只有长度没有宽度：用一系列足够短的直线首尾相接表示一条曲线。矢量结构中只记录这些小线段的端点坐标，将曲线表示为一个坐标序列，坐标之间认为是以直线段相连，在一定精度范围内可以逼真地表示各种形状的线状地物。“多边形”在地理信息系统中是指一个任意形状、边界完全闭合的空间区域。其边界将整个空间划分为两个部分：包含无穷远点的部分称为外部，另一部分称为多边形内部。多边形的边界线同线实体一样，可以被看作是由一系列多而短的直线段组成。2.矢量数据结构矢量数据结构分为以下几种主要类型 简单数据结构 拓扑数据结构 曲面数

29、据结构1）简单数据结构 a.面条（Spaghetti方式）在简单数据结构中，空间数据按照以基本的空间对象（点、线、多边形）为单位进行单独组织，不含有拓扑关系数据，最典型的是面条（Spaghetti方式）由多边形边界的x、y坐标对集合及说明信息组成，是最简单的一种多边形矢量编码，如上图记为以下坐标文件：10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1；20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15；x16,y16；x17,y17；x18,y18；x19,y

30、19；x20,y20；x21,y21；x22,y22；x23,y23；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1；30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40；x33,y33；40：x19,y19；x20,y20；x21,y21；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32；x19,y19；50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,

31、y28；x21,y21；坐标序列法文件结构简单，易于实现以多边形为单位的运算和显示。特点：1.数据按点、线或多边形为单元组织，数据编排直观，数字化操作简单 2多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形；3每个多边形自成体系而缺少邻域信息，难以进行邻域处理，如消除某两个多边形之间的共同边界；4.岛只作为一个单个的图形建造，没有与外包多边形的联系；5不易检查拓扑错误。这种方法可用于简单的粗精度制图系统中 该法采用树状索引以减少数据冗余并间接增加邻域信息，方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构

32、b.树状索引编码法 以下分别为右图的多边形文件和线文件树状索引示意图。其文件结构如下：线与多边形之间的树状索引点与边界线之间的树状索引 采用上述的树状结构，前图的多边形数据记录如下：1）点文件点号坐标1 x1,y12 x2,y2 40 x40,y40 2）线文件线号起点 终点 点号I 1 6 1,2,3,4,5,6II 6 8 6,7,8 X 33 33 33,34,35,36,37,38,39,40,333）多边形文件多边形编号多边形边界10I,II,IX20III,VII,VIII,IX,X30X40IV,VI,VII50II,III,IV,V 树状索引编码消除了相邻多边形边界的数据冗余和

33、不一致的问题，在简化过于复杂的边界线或合并相邻多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到 但是比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需要以人工方式建立，工作量大且容易出错 2）拓扑数据结构 拓扑型数据结构由弧段坐标文件、结点文件和多边形文件等一系列含拓扑关系的数据文件组成。结点文件由结点记录组成，存贮每个结点的结点号、结点坐标及与该结点连接的弧段等 弧段坐标文件存贮组成弧段的点的坐标 弧段文件由弧记录组成，存贮弧段的起止结点号和左右多边形号；多边形文件由多边形记录组成，存贮多边形号、组成多边形

34、的弧段号以及多边形的周长、面积、中心点坐标。DIME(双重独立坐标地图编码，Dual Independent Map Encoding)编码系统 DIME是美国人口调查局在人口调查的基础上发展起来的，它通过有向编码建立了多边形、边界、节点之间的拓扑关系，DIME编码成为其它拓扑编码结构的基础 拓扑整合的地理编码和参考系统（TIGER)多边形转换器（POLYVRT）拓扑数据结构最重要的技术特征和贡献是具有拓扑编辑功能。这种拓扑编辑功能，不但保证数字化原始数据的自动差错编辑，而且可以自动形成封闭多边形边界，为由各个单独存储的弧段组成所需要的各类多边形及建立空间数据库奠定基础。拓扑编辑功能包括多边形

35、编辑和结点编辑a.多边形编辑弧段号 起点 终点 左多边形 右多边形a2 N2 N4 0 p4a7 N3 N4 p4 p3a8 N2 N3 p4 p2弧段号 起点 终点 左多边形 右多边形a2 N4 N2 p4 0a7 N3 N4 p4 p3a8 N2 N3 p4 p2弧段号 起点 终点 左多边形 右多边形a2 N4 N2 p4 0a8 N2 N3 p4 p2a7 N3 N4 p4 p3N1N3N5N2N4P2P1P4P3b.结点编辑N1N3N5N2N4P2P1P4P3弧段号 起点 终点 左多边形 右多边形a8 N2 N3 p4 p2a6 N3 N5 p3 p1a7 N3 N4 p4 p3a5

36、N1 N3 p2 p1弧段号 起点 终点 左多边形 右多边形a8 N2 N3 p4 p2a6 N5 N3 p1 p3a7 N4 N3 p3 p4a5 N1 N3 p2 p1弧段号 起点 终点 左多边形 右多边形a5 N1 N3 p2 p1a6 N5 N3 p1 p3a7 N4 N3 p3 p4a8 N2 N3 p4 p23）曲面数据结构 曲面是指连续分布现象的覆盖表面，具有这种覆盖表面的要素有地形、降水量、温度、磁场等。表示和存储这些要素的基本要求是必须便于连续现象在任一点的内插计算，因此经常采用不规则三角网来拟合连续分布现象的覆盖表面，称为TIN（Triangulated Irregular

37、 Network）数据结构 这种基于TIN的曲面数据结构，通常用于数字地形的表示，或者按照曲面要素的实测点分布，将它们连成三角网，三角网中每个三角形要求尽量接近等边形状，并保证由最邻近的点构成的三角形，即三角形的边长之和最小。在所有可能的三角网中，狄洛尼（Delaunay）三角网在地形拟合方面表现最为出色。狄洛尼（Delaunay）三角网：为相互邻接且互相不重叠的三角形的集合，每一个三角形的外接圆内不不含其他的点。狄洛尼三角形外接圆不包含其他点的特性被用作从一系列不重合的平面点建立狄洛尼三角网的基本法则，可以称为狄洛尼法则34271865三角形的标识码相邻三角形 三角形顶点 顶点坐标和特征值1

38、 2 3 1st 2st 3stX1，y1，z1 X2，y2，z2 X3，y3，z3A B C D 1 2 7ABCD四、矢栅结合的数据结构1.矢栅混合模式 有多种形式，最简单也最实用的是不对矢量结构数据和栅格结构数据做任何特殊处理，直接将他们分别存储在同一个GIS的空间数据库系统中，并通过共同的ID号将各空间对象的矢量数据，栅格数据及属性数据关联在一起。实体ID矢量数据栅格数据属性数据缺点：矢量和栅格两套数据均要无遗漏的在系统中存储，会给系统的存储空间带来压力2.矢栅一体化模式 为了解决失栅混合增加存储空间这一问题，并更加有效的将矢量、栅格数据结构结合起来，gongjianya提出了失栅一体

39、化模式，其理论基础是多级格网方法，三个基本约定和线形四叉树编码。多级格网:包括粗格网，基本格网和细分格网三个层次 粗格网建立空间索引。基本格网的大小与常规栅格划分要求一致；细分格网是在点、线经过的基本栅格上在进一步划分为16*16或256*256的小格网，以增加栅格的空间分辨率，从而提高点线表达精度256256 粗格网、基本格网和细分格网均采用线性四叉树编码，并采用三个Morton码（M0,M1,M2）表示。其中：M0表示点所在或线所通过的粗格网的Morton码，是研究区的整体编码。M1表示点所在或线通过的基本栅格的morton码，也是研究区内的整体编码。M2表示点所在或线所通过的细分栅格的m

40、orton码，是基本栅格内的局部编码 以上编码是基于栅格的，因而据此设计的数据结构必定具有栅格的性质，为了使之具有矢量的特点，gongjianya提出了点状地物，线状地物的三个约定 约定一：点状地物仅有空间位置，而无形状和面积，在计算机中仅有一个位置数据 约定二：线状地物有形状，但无面积，在计算机中需要组织一组元子（即栅格单元）填满的路径表达；约定三：面状地物有形状和面积，在计算机内有一组元子表达的填满路径的边界线和内部（空洞出外均填满）的区域组成举例：点ID M1 M2关联的弧段弧ID 起点ID 终点ID 左域ID 右域ID 中间点坐标（M1,M2）序列据此，点状地物、线状地物和面状地物的“

41、矢量化”数据记录方式如下：点状地物：用（M1,M2）代替（x，y）线状地物：用（M1,M2）代替（x，y）记录中间点面状地物：除了要用Morton码即（M1,M2）代替（x，y）记录面状地物边界原始采样点的“拐点”（即中间点）位置，以及它们所穿过的所有基本格网的交线位置之外，还要用链指针记录多边形的内部栅格。面域ID 边界ID序列面域内点指针 面域内点指针位置面域内点坐标（M1,M2）序列点标识号M1 M2 高程z.1002510026.43105.40827725.432463.点状目标及其数据结构结点点标识号M1 M2 高程z关联弧段.10026 43 425 141 101，202，10310027 501 141 256 205，201，301，.结点及其数据结构弧段及其数据结构弧段标识 始结点 终结点 左区 右区 中间点串（M1,M2,Mz）.20044 10027 10026 30024 58，77，56；92，55，777，.面状地物及其数据结构多边形标识号关联弧段 面块头指针.30018 128，125，126 0.0 1 4 5 16 202 3 6 78 9 1210 11二维行程M码循环指针属性值二维行程M码循环指针属性值0 87 128 1612 2016 020 3625 48