《数据结构栅格.pptx》由会员分享，可在线阅读，更多相关《数据结构栅格.pptx（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第1页/共36页2由于地理数据往往有较强的由于地理数据往往有较强的相关性相关性，也，也就是说相邻像元的值往往是相同的。因就是说相邻像元的值往往是相同的。因此，为了节省存储空间，需要进行栅格此，为了节省存储空间，需要进行栅格数据的数据的压缩存储压缩存储 第2页/共36页3 游程编码游程编码栅格数据压缩栅格数据压缩（1）把具有相同属性值的把具有相同属性值的邻近栅格单元合并在一起邻近栅格单元合并在一起，合并一次称为一个游程。游程用一对，合并一次称为一个游程。游程用一对数字表达，其中，第一个值表示数字表达，其中，第一个值表示游程长度游程长度，第二个值表示，第二个值表示游程属性值游程属性值。每一个新行
2、都。每一个新行都以一个新的游程开始以一个新的游程开始 第3页/共36页4块码块码(游程编码向二维扩展游程编码向二维扩展)块式编码是将游程扩大到两维情况，把多边形范围划分成若干具有同一属性的正方形，然后对各个正方形进行编码。块式编码的数据结构由初始位置（行列号）、半径和属性代码组成。第4页/共36页5块码 采用方形区域作为记录单元，数据编码由初始位置行列号加上半径，再加上记录单元的属性组成。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3
3、30 0 0 0 3 3 3 3（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，6，3，3）；（7，4，1，0），（7，5，1，3）；（8，4，1，0），（8，5，1，0）。第5页/
4、共36页6 是根据栅格数据二维空间分布的特点，将空间区域按照4个象限进行递归分割（2n2 n，且n1），直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。根结点：最上面的一个结点，它对应于整个图形。叶子结点：不能再分的结点，可能落在不同的层上。常规四叉树栅格数据压缩第6页/共36页7第7页/共36页第二章 空间数据结构-2栅格数据结构八叉树结构八叉树结构 三维数据结构三维数据结构同二维一样，也存同二维一样，也存在着栅格和矢量两在着栅格和矢量两种形式。对于栅格种形式。对于栅格结构，较好的数据结构，较好的数据结构方式是在四叉结构方式是在四叉树基础上发展起来树基础上发展起来的八叉树结构。的八叉树
5、结构。第8页/共36页9计算：掌握：数据冗余度估计计算公式计算压缩比方法第9页/共36页10分析：对照P55图218和图2-19，分析其是如何进行游程索引编码的第10页/共36页11常规四叉树存储特点常规四叉树存储特点运算量较大。因为，大量数据需要运算量较大。因为，大量数据需要重复检查才能确定划分；重复检查才能确定划分；每个结点需要六个变量才能加以表每个结点需要六个变量才能加以表达：一个变量表示达：一个变量表示父结点指针父结点指针，四，四个变量代表个变量代表四个子结点指针四个子结点指针，一个，一个变量代表本结点的变量代表本结点的灰度或属性值灰度或属性值 第11页/共36页12为了克服常规四叉树
6、计算复杂的为了克服常规四叉树计算复杂的缺点，人们提出了线性四叉树的缺点，人们提出了线性四叉树的算法。算法。第12页/共36页13线性四叉树线性四叉树线性四叉树第13页/共36页14十进制整数转换为二进制整数十进制整数转换为二进制整数“除除2 2取余，逆序排列取余，逆序排列”法法。用用2 2去除十进制整数，可以得到一个商和余数；去除十进制整数，可以得到一个商和余数；再用再用2 2去除商，又会得到一个商和余数，如此进行，直到商为零时为止去除商，又会得到一个商和余数，如此进行，直到商为零时为止然后把所有余数按逆序排列，也就是把先得到的余数作为二进制数的低位有然后把所有余数按逆序排列，也就是把先得到的
7、余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。效位，后得到的余数作为二进制数的高位有效位，依次排列起来。这就是所谓这就是所谓“除除2 2取余，逆序排列取余，逆序排列”。线性四叉树Morton码第14页/共36页15线性四叉树编码。（线性四叉树编码。（MD码）码）线性四叉树的十进制地址码首先将二维栅格数据的行列号转化为二进制数然后交叉放入Morton码中 II=(inin-1i2i1)2 JJ=(jnjn-1j2j1)2 MD=(injnin-1jn-1i2j2i1j1)2再转换成十进制，即为线性四叉树的十进制Morton地址码。第15页/共36页16图中象元
8、值的右下脚标为Morton码，则压缩处理过程为：按Morton码读入一维数组。Morton码：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 象 元 值：A A A B A B B B A A A A B B B B 四相邻象元合并，只记录第一个象元的Morton码。MortonMorton编码后压缩处理过程编码后压缩处理过程第16页/共36页17思考：如何由十进制Morton码获得行列号分析P57图2-20f线性四叉树存储方法第17页/共36页18矢量与栅格数据结构的比较优点优点缺点缺点矢量矢量数据数据结构结构(1)结构严密，数据量小；结构严密，数据量小；(2)能
9、完整地描述拓扑关系；能完整地描述拓扑关系；(3)图形数据和属性数据的恢复、图形数据和属性数据的恢复、更新和综合都能实现；更新和综合都能实现；(4)图形输出精确美观。图形输出精确美观。(1)结构复杂，处理技术也复杂；结构复杂，处理技术也复杂；(2)图形叠置与图形组合很困难；图形叠置与图形组合很困难；(3)绘图费用高，尤其高质量绘图；绘图费用高，尤其高质量绘图；(4)数学模拟和空间分析极困难。数学模拟和空间分析极困难。栅格栅格数据数据结构结构(1)结构简单；结构简单；(2)空间数据的叠置与组合十分方空间数据的叠置与组合十分方便；便；(3)空间分析易于进行；空间分析易于进行；(4)数学模拟方便数学模
10、拟方便(5)技术开发费用低。技术开发费用低。(1)图形数据量大；图形数据量大；(2)难以建立网络连接关系；难以建立网络连接关系；(3)地图输出不精美。地图输出不精美。第18页/共36页19三三 曲面的表达曲面的表达曲面（surface）：表示一种连续的空间分布，例如地形变化、也可以描述其他的分布（人口、温度.）TINGRID第19页/共36页20不规则三角网模型不规则三角网模型（TIN,Triangulated Irregular Network）不规则三角网：特殊的矢量（拓扑）网络模型。原始数据是矢量样本点，将样本点用直线相互连接，形成不规则的三角形网络，网络的结点就是样本点，如果每个样本点
11、有自己的高程值，每个三角形就相当于三维空间中的一个斜面P60图2-13三角网存储方式第20页/共36页21作用：三维地形、等高线形作用：三维地形、等高线形成成第21页/共36页22课堂练习：第22页/共36页0123（1)栅格矩阵编码：（2)游程编码：（3)块码编码：（4)画出常规四叉树（5)对黑线区域进行线性四叉树编码（6)第9行3列转换的Morton码值？（7)Morton码37位于第？行？列。M M R M M M M MM M M R R M M M1 2 3 4 5 6 7 81 2 3 4 5 6 7 8M M R R R R R MM M R R M R M MM R R R R
12、 R R MM R R R R R R MM R R R R R R MM R R R R R R M（1）（2）（3）（4）（5）3210第23页/共36页244 空间数据结构的建立第24页/共36页25一 系统功能与数据源之间的关系参见表2-12二 空间数据的分类与编码第25页/共36页26分类、编码点、线、面特征码、坐标信息世界地理信息种类繁多、内容丰富、只有将它们按一定的规律进行分类和编码，使其有序地存储、检索，以满足各种应用分析需求。因此，地理数据的分类和编码是空间数据库建立的重要基础。第26页/共36页27属性数据的分类编码原则属性数据的分类编码原则分类是将具有共同的属性或特征的事
13、物或现象归并在一起，而把不同属性或特征的事物或现象分开的过程。分类是人类思维所固有的一种活动，是认识事物的一种方法。其要满足：u 系统性和科学性：满足所涉及学科的科学分类方法，能反映出同一类型中不同的级别特点。u 一致性：对代码所定义的同一专业名词、术语必须是唯一的。第27页/共36页28 兼容性兼容性(标准化标准化 通用性通用性)：有国家或行业标有国家或行业标准的要按标准进行，没有标准的必须考虑在准的要按标准进行，没有标准的必须考虑在有可能的条件下实现标准化。有可能的条件下实现标准化。实用性实用性(简捷性简捷性)：在满足国家标准的前提在满足国家标准的前提下、每一种编码应该是以最小的数据量载负
14、下、每一种编码应该是以最小的数据量载负最大的信息量。最大的信息量。可扩展性：可扩展性：编码的设置应留有扩展的余地，编码的设置应留有扩展的余地，避免新对象的出现而使原编码系统失效、造避免新对象的出现而使原编码系统失效、造成编码错乱现象。成编码错乱现象。第28页/共36页29属性数据的编码属性数据的编码 在属性数据中，有一部分是与几何数据的表示密切有关的。例如，道路的等级、类型等，决定着道路符号的形状、色彩、尺寸等。在GIS中，通常把这部分属性数据用编码的形式表示，并与几何数据一起管理起来。编码：是指确定属性数据的代码的方法和过程。代码：是一个或一组有序的易于被计算机或人识别与处理的符号，是计算机
15、鉴别和查找信息的主要依据和手段。编码的直接产物就是代码，而分类分级则是编码的基础。第29页/共36页30属性数据的编码属性数据的编码u层次分类编码法：u是按照分类对象的从属和层次关系为排列顺序的一种代码，它的优点是能明确表示出分类对象的类别，代码结构有严格的隶属关系。第30页/共36页31耕地71园地 72林地 73牧草地74居民点及公矿用地 75交通用地75水域 76未利用地 77土地利用类型7有林地 731灌木地 732疏林地733迹地 735针叶树疏林地7331阔叶树疏林地7332未成林林地734第31页/共36页32了解：国家基础地理信息编码行政区编码第32页/共36页33三三 矢量数据的输入与编辑矢量数据的输入与编辑1、键盘，人机对话方式2、程序批量输入。3、数字化a1a2001002001002程序空间数据库1、可手工输入2、由系统自动生成(如用顺序号代表标识符)标识码属性数据几何数据第33页/共36页34手扶跟踪数字化屏幕跟踪数字化格式转换数据扫描数字化 数字化的几种方法第34页/共36页35手扶跟踪数字化-数字化仪 数字化仪是一种重要的图形输入装置，能方便地实现图形数据的输入。数字化仪的规格一般有A00、A0、A1、A2、A3和A4等等，包括三种：数字化板、鼠标、与计算机的连线第35页/共36页36感谢您的观看！第36页/共36页