空间数据结构精品课件

1、空间数据结构第1页，共101页，2022年，5月20日，12点31分，星期五矢量表示法如果采用一个没有大小的点(坐标)来表达基本点元素时，称为矢量表示法。栅格表示法如果采用一个有固定大小的点(面元)来表达基本点元素时，称为栅格表示法。它们分别对应矢量数据模型和栅格数据模型。 第2页，共101页，2022年，5月20日，12点31分，星期五矢量图 栅格图第3页，共101页，2022年，5月20日，12点31分，星期五第一节 GIS的空间数据及其特征1.GIS的空间数据 GIS的一个重要部分就是数据。陈述彭院士曾经把GIS的数据比作水利设施中的水，没有了水，水利设施便无法发挥作用。GIS中没有了数

2、据，便成了无米之炊。但是，GIS中的数据必须适合建立实用系统的目的。在建立和维护一个GIS过程中，对数据的投入占总投入的5070%，有时甚至更多。如果GIS开发者对各类数据的特点及适用范围没有充分的了解，就难以设计和开发出完全适用的GIS。第4页，共101页，2022年，5月20日，12点31分，星期五1.1类型 GIS中的数据来源和数据类型繁多，概括起来主要有以下几种类型：1.1.1地图数据 来源于各种类型的普通地图和专业地图，这些地图的内容丰富，图上实体间的空间关系直观，实体的类别或属性清晰，实测地形图还具有很高的精度。1.1.2影像数据 主要来源于卫星遥感和航空遥感，包括多平台、多层面、

3、多种传感器、多时项、多光谱、多角度和多种分辨率的遥感影像数据，构成多源海量数据，于是GIS的最有效的数据源之一。第5页，共101页，2022年，5月20日，12点31分，星期五1.2.3地形数据 来源于地形等高线图的数字化，已建立的数字高程模型（DEM）和其他实测的地形数据等。1.2.4属性数据 来源于各类调查报告、实测数据、文献资料、解译信息等。1.2.5元数据 来源于由各类纯数据通过调查、推理、分析和总结得到的有关数据的数据，例如数据来源、数据权属、数据产生的时间、数据精度、数据分辨率、元数据比例尺、数据转换方法等。第6页，共101页，2022年，5月20日，12点31分，星期五空间数据根

4、据表示对象不同，又具体分为七种类型：类型数据 气象站、航线、野外样方分布区等面域数据 地名、河流名称、区域名称等网络数据 行政区域界线、行政单元等样本数据 点状符号、线状符号、面状符号等曲面数据 高程点、等高线、等值区域等文本数据 考古地点、道路线、土壤类型分布等符号数据 道路交点、街道、街区等第7页，共101页，2022年，5月20日，12点31分，星期五2.空间数据的基本特征 空间数据描述的是现实世界各种现象的三大基本特征：空间、属性和时间。对于GIS来说，属性和时间特征常被视为非空间属性。近年来对时间特征的研究越来越受到重视。2.1空间特征 它是指空间物体的位置、形状和大小等几何特征，以

5、及与相邻物体的拓扑关系。位置和拓扑特征是地理或空间系统所独有的，空间位置可以由不同的坐标系统来描述，如经纬度坐标、一些标准的地图投影坐标或是任意的直角坐标等。GIS的作用之一就是进行各种不同坐标系统间的相互转换。第8页，共101页，2022年，5月20日，12点31分，星期五 人类对空间目标的定位一般不是记忆其空间坐标，而是确定某一目标与其他更熟悉的目标间的空间位置关系，而这种关系往往也是拓扑关系。如一个学校是在哪两条路之间，或是靠近哪个道路叉口，一块农田离哪户农家或哪条路较近等等。通过这类空间描述，可在很大程度上确定某一目标的位置，而一串纯粹的地理坐标对人的认识来说几乎没有意义。有几个人记得

6、自己家或办公室的确切坐标？又有几个人对着坐标去上班？而对以计算机处理为主的GIS来说，最直接、最简单的空间定位方法是使用坐标，而拓扑关系则需要在空间坐标的基础上通过计算来建立。第9页，共101页，2022年，5月20日，12点31分，星期五2.2属性特征(专题特征) 数据的属性指的是除了时间和空间特征以外的空间现象的其他特征，如地形的坡度、坡向、某地的降水量、土壤酸碱度、土地利用类型、人口密度、交通流量、空气污染程度等。属性数据本身属于非空间数据，但它是空间数据中的重要数据成分，它同空间数据相结合，才能表达空间实体的全貌。目前GIS中对专题特征的输出方法大多沿用传统的专题制图方法，如分级(层)

7、设色法和符号法等。第10页，共101页，2022年，5月20日，12点31分，星期五2.3时间特征 空间数据的时间特征是指空间特征和属性特征随时间而变化的。它们可以同时随时间变化，也可以分别独立随时间变化。这说明了空间数据的时间性或周期性。例如某地区种植业的变化表示属性数据独立随时间的变化；行政边界的变更表示空间位置数据随时间的变化；土壤侵蚀而引起的地形变化不仅改变了空间位置数据也改变了属性数据。必须指出，过时的数据可能是重要的历史资料。第11页，共101页，2022年，5月20日，12点31分，星期五 严格来说，空间数据总是在某一特定时间或时间段内采集或计算得到的。由于有些空间数据随时间变化

8、相对较慢，因而有时被忽略。在很多场合时间可以被看成一个专题(属性)特征。这对于大多数GIS软件来说是可以做到的。但如何有效地利用时间在GIS中进行索引和时空分析仍处于研究阶段。 在GIS数据的表示中，如果加上时间轴将会大大增加空间数据处理的难度。因此，用时间属性来标注空间数据特征，以表示空间数据的时间性，也就是将时间特征隐含在数据当中。第12页，共101页，2022年，5月20日，12点31分，星期五 总之，空间数据的上述特点反映了它所具有的定位、定性、时间和空间关系。定位指空间实体的空间特征；定性指空间实体伴随着地理位置的自然属性；时间特征指空间实体是随时间而变化的，该特征通常是隐含的；空间

9、关系指拓扑关系，通常通过数据结构来表示。第13页，共101页，2022年，5月20日，12点31分，星期五第二节 空间数据结构与编码1.数据模型与数据结构 为了便于研究问题，人们通常把数据结构问题抽象成四个层次：1.1.1现实世界 客观存在的事物，其中某些特征可用数据来表达。1.1.2 数据模型 根据未来使用上的要求和事物的特征用概念化的语言和示意图来描述现实世界。第14页，共101页，2022年，5月20日，12点31分，星期五1.1.3 数据结构 用逻辑关系图、列表、矩阵来表达数据模型，并用某些数据项来反映现实世界以及数据之间的逻辑关系。1.1.4 文件结构 用数据项表示数据在计算机硬件中

10、的储存方式，通过用计算机语言编制的程序可以实现这种方式，并可以读、写数据。第15页，共101页，2022年，5月20日，12点31分，星期五 用计算机把现实世界的信息储存起来，并进行管理，需要人来完成转换工作，这一转换过程是先把现实世界抽象成思维模型(数据模型)，然后转变为描述事物的逻辑模型(数据结构)，再转换成计算机硬件可以接受的物理模型(文件结构)。这样人们在考虑、交流数据储存与管理问题时，可以暂不管具体的物理储存方式，而集中于概念的、逻辑的问题。在有的时候，人们也把数据模型、数据结构、文件结构合称为数据结构，以简化对问题的讨论。第16页，共101页，2022年，5月20日，12点31分，

11、星期五2.空间数据的编码 空间数据的编码是空间数据结构的组织和实现。它实际上反映了一种转换过程。也就是说，它是在数据结构的指导下，把空间的图形数据和属性数据经过分类、量化和组织转换成计算机所能接收的形式，以便进行各种处理分析。因此，可以把空间数据编码看成是把反映空间实体的信息转换成计算机所要求的信息，并将其存入到计算机中。第17页，共101页，2022年，5月20日，12点31分，星期五 不管是属性数据，还是图形数据，对其进行编码都需要注意标准化问题，如在确定分类分级体系时必须注意各专业的分级标准，对图形图象数据需要注意现有标准格式，此外编码要注意灵活性、惟一性及特征性。 空间实体的编码是GI

12、S设计中最主要的技术步骤之一，它同用户的要求、数据质量、精度和类型有一定关系，它以一定数据结构为支撑。不同类型数据必须用合适的数据结构进行组织才便于处理分析。因此后面将编码方案同空间数据结构一起讨论。第18页，共101页，2022年，5月20日，12点31分，星期五第二节 空间数据的拓扑关系 空间数据的几何目标信息包含两类信息：位置信息和空间关系信息。空间对象关系又称为拓扑关系。 1.拓扑的基本概念 拓扑关系是定义空间关系的一种数学方法，在GIS中用它来描述并确定空间的点、线、面之间的关系，并可实现相关的查询和检索。第19页，共101页，2022年，5月20日，12点31分，星期五 几何形状不

13、同，但结点间拓扑关系是相同的，均可用结点矩阵表示。1表示两结点相连。 a b c d e a - 1 0 0 1 b 1 - 1 0 1 c 0 1 - 1 0 d 0 0 1 - 1 e 1 1 0 1 - a b c d a - 1 0 1 b 1 - 1 1 c 0 1 - 1 d 1 1 1 -abcde(a)edcba(b)(c)(c)(a)abcd(b)abcd 面块之间的拓扑邻接关系用邻接矩阵表示。第20页，共101页，2022年，5月20日，12点31分，星期五 总之，拓扑关系反映了空间实体之间的逻辑关系，它不需要坐标、距离信息，不受比例尺限制，也不随投影关系变化。因此，在GI

14、S中，了解拓扑关系对空间数据的组织、空间数据的分析和处理都具有非常重要的意义。第21页，共101页，2022年，5月20日，12点31分，星期五2.拓扑关系类型2.1拓扑关系基本类型 最基本的类型是邻接和关联。拓扑邻接 概念：表示图形元素（通常指同类元素）之间的相邻性。如多边形之间、弧段之间的邻接性等。（表中值为1表示所对应多边形相邻接。）第22页，共101页，2022年，5月20日，12点31分，星期五a2a7a3a1a6a5a4N1N2N3N4N5P1P2P3P4 弧段左多边形右多边形 a1P1/ a2/P2 a3/P3 a4P3P2 a5P1P3 a6P1P2 a7P4P2邻接多边形P1

15、P2 P3 P2P2 P3 P4P3P1 P2 a4 P4P2P1 P2 P3 P4P1- 1 1 0P21 - 1 1P31 1 - 0P40 1 0 -多边形之间的关系表：第23页，共101页，2022年，5月20日，12点31分，星期五a2a7a3a1a6a5a4N1N2N3N4N5P1P2P3P4 弧段起点终点 a1N2N1 a2N2N3 a3N3N1 a4N3N4 a5N1N4 a6N4N2 a7N4N5结点弧 段N1a1 a3 a5N2a1 a2 a6N3a2 a3 a4 N4a4 a5 a6N5a7弧段和结点之间的关系表：第24页，共101页，2022年，5月20日，12点31分

16、，星期五 弧段a1 a2 a3 a4 a5 a6 a7 a1- 1 1 0 - - 0 a21 - 1 1 0 1 0 a31 1 - 1 1 0 0 a40 1 1 - 1 1 0 a51 0 1 1 - 1 0 a61 1 0 1 1 - 0 a70 0 0 0 0 0 - 结点P1 P2 P3 P4 P5 P1- 1 1 1 0P21 - 1 1 0P31 1 - 1 0P41 1 1 - 0P50 0 0 0 -弧段和结点之间的关系表：a2a7a3a1a6a5a4N1N2N3N4N5P1P2P3P4第25页，共101页，2022年，5月20日，12点31分，星期五2.1.2拓扑关联 概

17、念：表示图形基本元素间（常指不同元素间）的联接关系。如结点与弧段之间，多边形与弧段之间。 第26页，共101页，2022年，5月20日，12点31分，星期五2.1.3包含关系 概念：指点、线、面之间的相互包含关系，通常是指面状实体中包含的其它面状实体或线状、点状实体的关系。面状实体中包含面状实体情况又分为三种情况：第27页，共101页，2022年，5月20日，12点31分，星期五2.1.4重合：指同类元素间有无重合的关系。2.1.5相离：指元素间不在同一个位置。2.1.6相交：至少有一点落在另一元素上。2.1.7拓扑元素量、质不变及相互关系： 欧拉公式：L+2A+P。P、L、A表示平面图上点数

18、、线数及面块数(包括边界外的面)，2为欧拉示性数，也称为多边形地图特征。第28页，共101页，2022年，5月20日，12点31分，星期五3.拓扑关系的表达方式3.1全显式表达 不仅表示多边形弧段点之间拓扑关系，同时表示点弧段多边形之间的拓扑关系。第29页，共101页，2022年，5月20日，12点31分，星期五第30页，共101页，2022年，5月20日，12点31分，星期五3.2半隐式表示第31页，共101页，2022年，5月20日，12点31分，星期五4.拓扑关系的意义4.1便于确定空间位置关系。 4.2利用拓扑数据有利于空间要素的查询。4.3利用拓扑数据作为工具，重建地理实体。第32页

19、，共101页，2022年，5月20日，12点31分，星期五第三节 空间数据结构的类型 数据表达可以采用矢量数据模型和栅格数据模型。数据模型确定选择数据结构组织数据选择文件格式。 数据结构分为矢量数据结构、栅格数据结构、矢量栅格一体化数据结构。第33页，共101页，2022年，5月20日，12点31分，星期五1.矢量数据结构 概念：基于矢量模型的数据结构简称为矢量数据结构，是利用点、线、面及其组合体表示地理实体空间分布的一种数据组织方式。1.1简单数据结构（实体型数据结构） 将空间实体分成点、线、面3类目标，通过坐标值精确表示点、线、面等地理实体，不考虑拓扑关系。第34页，共101页，2022年

20、，5月20日，12点31分，星期五1.1.1点：用一对(x, y)坐标表示，仅有空间位置，没有形状和面积。1.1.2线：用两对以上的(x, y)坐标表示，有形状但没有面积。 1.1.3面：用首尾相接的多对(x, y)坐标表示其边界，有形状和面积，公共边界重复编码。 在简单数据结构中，空间数据以点、线、面为单元进行单独组织，不含拓扑关系数据，最典型的是面条(Spaghetti)结构。第35页，共101页，2022年，5月20日，12点31分，星期五第36页，共101页，2022年，5月20日，12点31分，星期五这种数据结构的主要特点： 数据按点、线或多边形为单元进行组织，数据编排直观，数字化操

21、作简单。 每个多边形都以闭合线段存储，多边形的公共边界被数字化两次和存储两次，造成数据冗余和不一致。 点、线和多边形有各自的坐标数据，但没有拓扑数据，相互之间不关联。 岛只作为一个单个图形，没有与外界多边形的联系。第37页，共101页，2022年，5月20日，12点31分，星期五2.索引数据结构 索引数据结构是对简单数据结构的改进。它先对所有点坐标按顺序建立点坐标文件，再建立多边形弧段索引文件、弧段点索引文件。 优缺点：索引数据结构中所有点的坐标只存贮一次，减少了数据冗余，并提高了对数据文件的访问速度。但不能处理“岛”结构的多边形数据。第38页，共101页，2022年，5月20日，12点31分

22、，星期五第39页，共101页，2022年，5月20日，12点31分，星期五3.拓扑数据结构 拓扑数据结构包括DIME(又称双重独立地图编码、对偶独立地图编码：Dual Independent Map Encoding)、TIGER(地理编码和参照系统的拓扑集成)等。第40页，共101页，2022年，5月20日，12点31分，星期五3.1 DIME编码 DIME编码文件由线段组成。每条线段包括线段名、线段的起结点和终结点、线段的左、右区号及线段所表示街道两边的地址范围。第41页，共101页，2022年，5月20日，12点31分，星期五 该数据结构中弧段是数据组织的基本对象。第42页，共101页，

23、2022年，5月20日，12点31分，星期五3.2拓扑编辑 拓扑数据结构最重要的特征和贡献是具有拓扑编辑功能。拓扑编辑可实现数据的自动查错，自动形成封闭的多边形。3.2.1 多边形连接编辑（设需对P1进行编辑，其算法过程：） 从表2-5中找出含有多边形P1的全部记录：第43页，共101页，2022年，5月20日，12点31分，星期五 计算机检查P1所处的位置。使线段右多边形号为P1，如果不是，互换左、右多边形的位置，同时也将该弧段记录的结点号位置作相应的交换。得到表： 从上表中，任取一个起结点，顺序连接各结点，必要时可对记录的前后顺序作调整，使得连接的结点能自行封闭。图第44页，共101页，2

24、022年，5月20日，12点31分，星期五 若不能闭合，或出现记录缺失或多余，则表示弧段文件有错，需改正错误的记录。直到所有多边形都经过编辑和改正，再转入结点连接编辑。3.2.2结点连接编辑（设需对N2进行编辑，其算法过程：） 检出与N2相关的所有记录：图第45页，共101页，2022年，5月20日，12点31分，星期五 在检出的记录中，计算机检查N2的位置。逐一检查上表中各线段走向，使终结点均为N2，得下表： 调整线段的顺序号，以保证该结点周围的多边形顺序连结。从而得到与结点N2相连的多边形号以逆时针方向为P2P1P4P2图第46页，共101页，2022年，5月20日，12点31分，星期五

25、即该结点的第一区P2与最后一个区P2号一致，表示编码无误。相反则表示编辑有错，应改错，重新编辑，直到所有结点都经过编辑和改正，才能将该弧段文件存入数据库。 这种拓扑数据结构及其自动编辑功能，已被许多商品化的GIS软件所采用，如Arc/Info。图第47页，共101页，2022年，5月20日，12点31分，星期五3.3曲面数据结构 曲面是指连续分布现象的覆盖表面（如地形、降水量、温度等）。常用不规则三角网来拟合连续分布现象的覆盖表面，称为TIN(Triangulated lrregular Network)数据结构。第48页，共101页，2022年，5月20日，12点31分，星期五 TIN数据结

26、构常用于数字地形的表示，三角网中的每个三角形要求尽量接近等边形状，由最邻近的点构成，即三角形的边长之和最小。 狄洛尼(Delaunay)三角网在地形拟合方面表现最好。它遵守欧拉定理：多面体顶点数-边数+面数=2。第49页，共101页，2022年，5月20日，12点31分，星期五 TIN中每个三角形可视为一个平面，每个三角形构成一个记录，Z轴表示属性，如地形高程等。利用TIN可进行地形分析。TIN已用于ARC/INFO、MGE等。第50页，共101页，2022年，5月20日，12点31分，星期五2.栅格数据结构 概念：基于栅格模型的数据结构简称为栅格数据结构，指将空间分割成有规则的网格，在各个网

27、格上给出相应的属性值来表示地理实体的一种数据组织形式。第51页，共101页，2022年，5月20日，12点31分，星期五2.1栅格矩阵结构（直接编码法） 最简单和直观的栅格数据编码法。它对栅格图从左上角开始逐行逐列地存储数字化代码。第52页，共101页，2022年，5月20日，12点31分，星期五2.1.1栅格数据取值方法 面积占优法：把栅格中占有最大面积的属性值定为本栅格元素的值。 第53页，共101页，2022年，5月20日，12点31分，星期五 中心点法：将栅格中心点的值作为本栅格元素的值。第54页，共101页，2022年，5月20日，12点31分，星期五 长度占优法：在网格中心画一横线

28、，用横线所占最长部分的属性值作为本栅格元素的值。第55页，共101页，2022年，5月20日，12点31分，星期五 重要性法：突出某些主要属性，对于这些属性，只要在栅格中出现，不管所占比例大小，就把该属性作为本栅格元素的值。假设D属性重要：第56页，共101页，2022年，5月20日，12点31分，星期五 注意： 面积占优法最适合分类较细、地物类别斑块较小的情况； 中心点法常用于具有连续分布特性的地理要素； 重要性法常用于具有特殊意义而面积较小的地理要素。 栅格矩阵结构的阵列中存在大量相同属性数据，可以压缩。数据压缩是要降低数据量，缩短解码时间。数据量和解码时间是一对矛盾。第57页，共101页

29、，2022年，5月20日，12点31分，星期五2.2费尔曼链码结构(Freemans Chain Code) 费尔曼链码也称边界码、链式编码。用8个方向码编码，用某一原点开始的矢量链表示曲线或边界。8个方向为东(E=0)，东南(SE=1)，南(S=2)，西南(SW=3)，西(W=4)，西北(NW=5)，北(N=6)，以及东北(NE=7)。第58页，共101页，2022年，5月20日，12点31分，星期五 基本方向定义为：东=0，东南=1，南=2，西南=3，西=4，西北=5，北=6，东北=7。 左图的线状地物其起始点为像元(1，5)，编码为：1,5,3,2,2,3,3,2,3 对于左图所示的面状

30、地物，假设其起始点定为像元(5,8)，按顺时针的编码为：5,8,3,2,4,4,6,6,7,6,0,2,1第59页，共101页，2022年，5月20日，12点31分，星期五 该编码的优点是：数据压缩率高，便于计算周长、面积，便于表示图形凹凸部分。缺点是难于实现叠加运算，不便于合并和插入等操作，对局部修改将改变整体数据结构，相邻区域的公用线段会重复存储，使数据冗余。第60页，共101页，2022年，5月20日，12点31分，星期五2.3游程编码结构(Run Length Code) 游程指相邻同值网格的数量，游程编码结构是逐行将相邻同值的网格合并，并记录合并后网格的值及合并网格的长度，其目的是压

31、缩栅格数据量，消除数据间的冗余。 游程(行程)编码是对具有块状地物的栅格数据进行压缩编码的方法。GIS研究对象多为块状地物。 游程编码以行为单位，将栅格数据矩阵中属性相同的连续栅格视为一游程。分为游程终点（值）编码和游程长度编码。第61页，共101页，2022年，5月20日，12点31分，星期五2.3.1游程终点（值）编码 编码中第一行(0，1)表示属性0的栅格终止点为1列，(4，3)表示属性值为4的栅格终止点为第3列.。从游程终点值可算出每个属性值所占栅格数。如属性值为7的栅格数为8-3=5。第62页，共101页，2022年，5月20日，12点31分，星期五2.3.1游程终点（值）编码(0，

32、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) 表第一行(0，1)表示属性值为0的栅格数为1，(4，2)表示属性值为4的栅格点数为2.第一行总栅格数为1+2+5=8。第63页，共101页，2022年，5月20日，12点31分，星期五注意： 游程编码只考虑了水平间的相关性（行内），而未考虑垂直间的相关性（行间）。游程越长，编码效率越高。 游程编码对面积较大的图形，数据压缩率高，易于实现叠加、合并和检索运

33、算。在GIS中应用很广。 当栅格数据为DEM时，可先进行差分处理，再采用游程长度压缩编码法。过程如下第64页，共101页，2022年，5月20日，12点31分，星期五第65页，共101页，2022年，5月20日，12点31分，星期五第66页，共101页，2022年，5月20日，12点31分，星期五2.3.3栅格数据经过压缩得到游程编码数据序列，为了提高系统对数据的访问效率，常采用索引顺序文件的方法来组织数据:第67页，共101页，2022年，5月20日，12点31分，星期五第68页，共101页，2022年，5月20日，12点31分，星期五第69页，共101页，2022年，5月20日，12点31

34、分，星期五2.4块码结构(Block Code) 块码以正方形区域为单元对块状地物的栅格数据进行编码。实质是把栅格中同一属性方形区各元素映射成一个元素序列。 块码的编码方式为：行号、列号、半径、属性代码。行号和列号表示正方形区左上角栅格的行号及列号；半径为正方形区行(或列)方向的栅格数。 块码法是把一维游程编码扩展到二维空间。若面状地物所包含的正方形越大，边界越规则，编码的效率越高。块码对计算面积、检索图形、合并和插入操作较有利。第70页，共101页，2022年，5月20日，12点31分，星期五 如（1，1，10）表示1行1列，半径为1，属性为0；（1，2，2，4）表示1行2列，半径为2，属性

35、为4。第71页，共101页，2022年，5月20日，12点31分，星期五2.5四叉树数据结构(Quadtree Code) 又称四分树、四元树编码。有许多编码方案。2.5.1常规四叉树 基本思想是把栅格地图等分成4等分，若每个子区中栅格值相同则不再分割，否则将该区再分割成4个子区，直到每个子块都含有相同的属性值为止。这称为自上往下(Top-to-Down)的常规四叉树。也可自下而上(Down-to-Top)建立。下图是利用自上而下方法寻找栅格A的过程：第72页，共101页，2022年，5月20日，12点31分，星期五第73页，共101页，2022年，5月20日，12点31分，星期五2.5.2线

36、性四叉树 常规四叉树占空间大，因为要记录所有结点值和结点之间的关系。 而线性四叉树是通过编码四叉树的叶结点表示数据块的层次和空间关系。叶结点是一地址码(Morton码，Z形编码)。第74页，共101页，2022年，5月20日，12点31分，星期五第75页，共101页，2022年，5月20日，12点31分，星期五基于四进制的线性四叉树编码(MQ) 2N*2N的图象，最多有N层，用N位四进制地址码。上图叶结点(7)的编码为： MQ=2IB+JB。行号IB和列号JB为二进制。例如011行，011列的MQ2X011+011=033第76页，共101页，2022年，5月20日，12点31分，星期五基于十

37、进制的线性四叉树编码(MD) 将栅格的二进制表示的行列号IB和JB按位交错排列，得二进制地址码，再转十进制MD。 例如求011行，010列所对应的MD=14列号 = 010行号 = 011 0 0 1 1 1 0第77页，共101页，2022年，5月20日，12点31分，星期五四叉树优点：（1）具有可变分辨率，编码效率高；（2）便于岛的表示和分析。（3）便于同栅格之间相互转换。四叉树缺点：转换不稳定性。相同形状和大小的 多边形可能得出多种不同的四叉树结构。第78页，共101页，2022年，5月20日，12点31分，星期五2.6二维行程结构 线性四叉树表前后叶结点值相同的可合并成一个值。 二维行

38、程编码中，前后两个地址码之差表达了该行程段的格网数，它可以表示该子块的大小。第79页，共101页，2022年，5月20日，12点31分，星期五 所以，二维行程编码比四叉树更省存储空间，便于以后的插入、删除和修改等操作。如0与8之间插入一个地址码为7、格网值为1的记录， 二维行程编码的压缩率很高。它和线性四叉树采用相同的地址码，相互之间的转换非常容易和快速。几乎视为同一概念。第80页，共101页，2022年，5月20日，12点31分，星期五2.7三维和四维数据结构2.7.1三维和四维数据结构的提出 二维数据结构将第三维坐标作为属性值来处理，它无法建立空间实体的三维拓扑关系。这就提出了时间和空间信

39、息系统的问题。 用三维来定义空间目标，用四维数据定义时间和空间数据：任何目标都可以由其坐标对(s，t)惟一确定。这里s=x，y，z定义空间数据，而t定义时间数据。 三维和四维数据用八叉树和十六叉树结构表示。第81页，共101页，2022年，5月20日，12点31分，星期五2.7.2八叉树数据结构 原理是将空间区域不断地分解为八个同样大小的立方体，直到同一区域的属性单一为止。也可自下而上的合并。 常规八叉树需记录父结点和子结点的地址码和属性值。线性八叉树只需要记录叶结点的地址码和属性值。第82页，共101页，2022年，5月20日，12点31分，星期五计算定位码的3规则分辨率n(分割次数)决定坐

40、标大小。X,Y,Z轴取值范围从0到2n-1。图n=3,X,Y,Z=07(10进制)编码形式:qn-1 qn-2 qn-3 qi是 07中之一(8进制),qi的个数取决于n。Z字形编码。例x=6,y=3,z=1的地址码：第83页，共101页，2022年，5月20日，12点31分，星期五第84页，共101页，2022年，5月20日，12点31分，星期五第85页，共101页，2022年，5月20日，12点31分，星期五线性八叉树的优点： 节省存储空间：只需对叶结点编码，节省了大量中间结点的存储。 可直接寻址：通过坐标值则能计算出结点的定位码(称编码)，也能从定位码中获取其坐标值(称解码)； 操作方便

41、：定位码容易存储和执行，容易实现集合、相加等组合操作。第86页，共101页，2022年，5月20日，12点31分，星期五3.矢量与栅格一体化数据结构3.1矢量与栅格数据结构的比较3.1.1矢量数据的特点 数据精度高，冗余度小，拓扑关系明确 以点坐标为基础记录数据，存储空间小，精确高，便于对图形缩放、投影转换，具拓扑关系。第87页，共101页，2022年，5月20日，12点31分，星期五 面向目标的结构 对于每一个具体的目标都直接赋有位置、属性、拓扑信息。可直接根据目标物几何形状用坐标计算方法，计算精度高，运算量少 难以同遥感数据结合 矢量数据系统，难于同DEM、遥感数据结合，限制了矢量数据系统

42、的功能和效率。目前采用：矢量数据栅格数据进行分析矢量数据第88页，共101页，2022年，5月20日，12点31分，星期五3.1.2栅格数据的特点 数据精度低，数据量大 栅格数据是用逼近方法表示实体，栅格单元的尺寸越小，精度越高，但数据量就越大，影响速度。 面向位置的结构 每一栅格元素都直接联系到某一地物。但又没有直接聚集所有信息，某一位置的多种特征值的表示需要分图层。不能建立拓扑关系。第89页，共101页，2022年，5月20日，12点31分，星期五 数据结构简单，易与遥感结合 以阵列(数组)描述空间实体，其数据结构简单，便于同遥感结合。 图形质量差 栅格元素是表示地物目标的最基本单位。所反映的实体会变形，属性会出偏差，从而影响图形质量。 第90页，共101页，2022年，5月20日，12点31分，星期五矢量数据结构栅格数据结构优点：1、便于面向现象（土壤类、土地利用单元 等）的数据表示2、数据结构紧凑、冗余度低3、有利网络分析4、图形显示质量好、精度高优点：1、数据结构简单2、空间分析和地理现象的模拟均比较容易3、有利于遥感数据的匹配应用和分析4、输出方法快速，成本比较低廉缺点：1、数据结构复杂2、软件与硬件的技术要求比较高3、多边形叠合分析比较困难4、显示与绘图成本比较高缺点：1、图形