02地图数据结构.ppt-得力文库

资源描述

《02地图数据结构.ppt》由会员分享，可在线阅读，更多相关《02地图数据结构.ppt（128页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、城市与环境科学学院1 1第二章地图数据结构第二章地图数据结构21 地图数据的描述方法地图数据：地图诸要素的数字化表示，是以点、线、面等方式采用编码技术对地理空间物体进行特征描述及在物体间建立相互联系的数据集。一、地图对地理空间的描述地图是现实世界的模型，它按照一定的比例和投影原则，有选择地将复杂的三维地理空间的某些内容投影到二维平面介质上，并用符号将这些内容要素表现出来。2 2第二章地图数据结构地图学中，把地理空间的实体分为点、线、面三种要素(对象)，分别用点状、线状、面状符号来表示。点实体点实体是有特定的位置、维数为0的实体。实体点：用来代表一个实

2、体；如城市注记点：用于定位注记；北京内点：用于记录多边形的属性，存在于多边形内；结点：表示线的终点和起点；3 3第二章地图数据结构结点：表示线的终点和起点；节点：它是两条或多条连线或链的拓扑连结点拐点：表示线段和弧段的内部点（特殊的节点）。(2)线实体（亦称为线段、弧、链、环等）线实体是维数为1的实体，由一系列坐标点表示。特征：实体长度：从起点到终点的总长；弯曲度：用于表示如道路拐弯时弯曲的程度；方向性：如河流从上游到下游，公路有单双向之分；4 4第二章地图数据结构(3)面(多边形)实体面(多边形)实体是维数为2的实体，由一个封闭的坐标点序列外加内点表示，是对湖泊、岛

3、屿、地块等现象的描述。具有以下特征：周长；面积；岛或非岛；内岛或齿状；重叠性等内面：不包括边界的面广义多边形（其他多边形覆盖面的周边以外的面，它没有外环，有一个或多个内环）虚多边形（以其他多边形为界的多边形）5 5第二章地图数据结构二、地图数据的基本特征地图数据具有空间特征、属性特征及时间特征。1空间特征(1)空间位置空间位置用以描述事物或现象的地理位置，又称几何特征、定位特征。通常用地理坐标系、平面直角坐标系来表示，也称几何特征，包括空间实体的位置、大小、形状、分布状况等，表明“在哪里”。(2)空间关系地理空间实体之间存在的一些具有空间特性的关系拓扑关系：拓扑变化下的拓扑不变

4、量，如邻接关系、关联关系和包含关系等；方位关系：实体在地理空间中的某种顺序，如左右、东南西北等；度量关系：用地理空间中的度量来描述的实体之间的关系，如实体之间的距离6 6第二章地图数据结构2属性特征属性特征用以描述事物或现象的特性，如事物或现象的类别、等级、数量、名称等，用来说明“是什么”。属性特征通常分定性和定量两种：（1）定性特征包括名称、类型等；（2）定量特征包括数量、等级等。3时间特征时间特征用以描述地理实体随着时间而变化的特征。目前的计算机地图制图还较少考虑到地图数据的时间特征，只考虑其属性特征与空间特征的结合。由于地图数据具有时间维，过时的信息虽不具有现势性，却可以作为

5、历史性数据保存起来，但这样做会增大计算机地图制图表示和处理数据的难度。7 7第二章地图数据结构图2-1：空间数据的基本特性Jack Dangermond,1984 8 8第二章地图数据结构三、地图数据的基本类型根据地图数据的特征，可以把地图数据分为空间数据、关系数据、属性数据三类。1空间数据也称几何数据，即描述地理现象或地理实体的空间位置、形状、大小等的数据。根据地理要素的空间分布待征和空间实体分类，可以将地理空间数据分为点、线、面三种类型。9 9第二章地图数据结构(1)点类型点类型可以描述如城乡居民地、工厂、学校、医院、机关、车站、山峰、隘口等现象。这里，

6、“点”是一个相对的抽象概念，即从较大的空间规模上来观测这些地物，就能把它们都归结为点状分布的地理现象，因此能用一个点的坐标(或栅格像元)来描述其空间位置。而如果从较小的空间尺度上来观察这些地理现象，它们中的多数将可以用一个面状特征来描述。例如同一个城市，在小比例尺地图上表现为点状分布，而在大比例尺地图上则可表现为面状分布，其内部表示了十分详细的城市街道分布状况。(2)线类型线类型描述如河流、运河、海岸、铁路、公路、地下管网、行政边界等线状分布的地理现象。这里的“线”(有时也称“弧”)也是一个相对的抽象概念。它们的空间位置数据是一线状坐标串(或栅格像元集合)。(3)面类型面类型描述如土地、水域

7、、森林、草原、沙漠等具有大范围连续(或断续)面状分布特征的现象。这里的“面”是一个相对的抽象概念，有时实地上不一定有明显的边界。描述面状特征的空间数据是一封闭的面坐标串(或栅格像元集合)，通常称之为多边形。10 10第二章地图数据结构2空间数据的表示方法一般地，表示地理现象的空间数据可以细分为：类型数据：类型数据：例如考古地点、道路线和土壤类型的分布等；面域数据：面域数据：例如随机多边形的中心点、行政区域界线和行政单元等；网络数据：网络数据：例如道路交点、街道和街区等；样本数据：样本数据：例如气象站、航线和野外样方的分布区等；曲面数据：曲面数据：例如高程点、等高线和等值区域；文本

8、数据：文本数据：例如地名、河流名称和区域名称；符号数据：符号数据：例如点状符号、线状符号和面状符号（晕线）等（如图2-2所示）。11 11第二章地图数据结构GIS中中各各种种数数据据以以及及其其表表现现12 12第二章地图数据结构3关系数据关系数据是描述空间数据之间的空间关系的数据。上述点、线、面空间位置数据之间存在着某种特定的拓扑关系。这类数据表达了各类地理实体空间位置之间的相互关系，如空间数据的相邻、关联、包含等。各种地理要素的空间位置数据在地图上的关系，可以概括为点、线、多边形之间的9种形式的拓扑关系：点点、点线、点面；线点、线线、线面；面与点、面与线、面与面。最

9、常用的空间实体关系有6种，即：点点、点线、点面；线线、线面；面面。13 13第二章地图数据结构它们之间的相互关系：邻接、关联、相交、相离、包含、重合L-SP-SS-SL-LP-L相离相离相交相交邻接邻接重合重合包含包含P-P14 14第二章地图数据结构4属性数据属性数据是描述空间实体属性特征的数据，也称非几何数据，即描述地理现象或地理实体的定性或定量指标，包括语义与统计数据，如类型、等级、名称、状态等。有时也把描述时间特征的数据纳入该类。属性数据中的定性(或定量)指标通常要经编码转换才能被计算机接受。为了方便计算机存储、管理和使用这些编码，需要研究统一的分类系统和编码。

10、有关这方面的详细内容将在本书第3章中进行介绍。15 15第二章地图数据结构第二节地图的数据结构地图的数据结构主要指地图数据中空间数据的结构，是指几何数据以什么形式在计算机中存储和处理。地图的数据结构矢量数据结构栅格数据结构一、矢量数据结构1、矢量数据的概念矢量本身是数学上的概念运用到地理信息系统中。矢量数据结构是表达地图空间数据的一种常见的数据结构，16 16第二章地图数据结构矢量数据它通过记录坐标值的方式尽可能精确地表示呈点、线、面状分布的地理实体。2、矢量数据的表达在计算机地图制图中，各地理要素在二维平面上的矢量数据表达为：点0维矢量：由一（x，y）坐标值表示；

11、线1维矢量：由一串有序的（x，y）坐标表示；面2维矢量：由一串有序的且首尾坐标相同的（x，y）17 17第二章地图数据结构其中，一维矢量可以闭合，但不能与自身相交。如果相交，则应以交点为界将一维矢量分成几个一维矢量。如下图：（一维矢量可能空间关系）a b c d18 18第二章地图数据结构 3、矢量数据结构的表示矢量数据结构是最早用于表达地图空间数据的一种常见的数据结构，在计算机地图制图中，表示矢量数据的结构时应考虑以下问题：方便存储和处理与属性数据的联系矢量数据之间的拓扑关系表示矢量数据的方法有多种，但基本上相似。下面按考虑问题的多寡分别介绍矢量数据的简单结构和拓扑结

12、构及其有关的编码方法。19 19第二章地图数据结构（1）简单数据结构及编码简单的矢量数据结构不考虑拓扑关系，可用于矢量数据的存储、处理、显示、输出以及一般的查询和检索。有点、线、面三种基本的矢量数据结构形式。点数据结构形式标志码属性码（x，y）标志码属性码标志码（x，y）+或标志码具有唯一性，是按某种原则进行的编码（如顺序）属性码是与点有关的基本属性的编码，可有多个。（x，y）是定位坐标2020第二章地图数据结构线数据结构形式当然也可采用将属性数据单独存放的方式标志码和属性码的含义与点的数据结构相同；坐标对数n：构成该线的坐标对个数；坐标串：是构成线的矢量坐标对序列，共

13、有n对标志码属性码坐标对数n坐标串（x1，y1）坐标串（x1，y1）坐标对数n标志码属性码标志码+21 21第二章地图数据结构面（多边形）数据结构形式常见的两种形式标志码属性码坐标对数n坐标串（x1，y1）（x1，y1）标志码属性码弧段数n弧段标志码集弧段标志码01坐标对数n坐标串（x1，y1）弧段标志码n坐标对数m坐标串（x1，y1）有N个这种方法可能会产生大量的数据冗余这种方法保证了多边形公共边的唯一性2222第二章地图数据结构简单数据结构的编码形式因在矢量的简单数据结构中不考虑拓扑关系，故其编码方法仅记录空间实体的位置、标志及属性信息，而不记录拓扑关系。常见的编码

14、方法有独立实体法和点位字典法独立实体法在独立实体法中，每个点线面都直接跟随它的空间坐标。每个实体的坐标都独立存储，毫不顾及相邻的多边形或线或点状地物。具体形式如下：2323第二章地图数据结构对面状实体而言，最末一点的坐标与第一点相等。使用这种方法时，除了外轮廓线以外，多边形的边界线数据均获取和存储两次，这就会产生重叠或列隙（当取值误差时），并产生数据冗余。为了消除裂缝，需要二次编辑。点位字典法以公用点位字典为基础建立一些系统，这克服了独立实体编码的某些局限性。点位字典包含地图上每一个边界点的坐标，然后建立点、线、面的边界表，它们由点位序号构成。即：点位字典表：点号、坐标（点位字典

15、表：点号、坐标（X，Y）点实体：标志码，地物编码，点号点实体：标志码，地物编码，点号线实体：标志码，地物编码，（点号线实体：标志码，地物编码，（点号1，点号点号n）面实体：标志码，地物编码，（点号面实体：标志码，地物编码，（点号1，点号点号n，点号，点号1）2424第二章地图数据结构下图是两种表述方法的比较：A1 237C6 345B176 358201510500 5 10 15 20ABC1 2345678多边形地物编码坐标数据项AT301X1，Y1；X2，Y2；X3，Y3；X7，Y7；X1，Y1BT302X1，Y1；X7，Y7；X3，Y3；X6，Y6；X5，Y5；X8，Y8；

16、X1，Y1CT305X3，Y3；X4，Y4；X5，Y5；X6，Y6；X3，Y3独立实体编码2525第二章地图数据结构ABC1 2345678点号坐标数据项01X1，Y102X2，Y203X3，Y304X4，Y405X5，Y506X6，Y607X7，Y708X8，Y8点位字典表多边形地物编码点号AT3011，2，3，7BT3021，7，3，6，5，8CT3053，4，5，6点位字典表编码2626第二章地图数据结构（2）拓扑数据结构及编码地图上两点间距离或方向会随地图投影的不同而发生变化，故仅用距离或仅用距离或方向不能很好地描述地图要素间的空间关系方向不能很好地描述地图要

17、素间的空间关系。如果引用拓扑关系来描述地图要素间的空间关系，则不论地图投影如何变化，其拓扑关系都不改变。可见拓扑关系能从本质上描述地图要素间的空间关系。具有拓扑关系的矢量数据结构就是拓扑数据结构。拓扑数据结构是现代计算机地图制图系统所必需的。尽管拓扑数据结构的表示方式还没有固定的格式，也没有形成标准，但其基本原理是相同的。拓扑元素点（节点）、线（链、弧、边）、面（多边形）基本拓扑关系邻接、关联、包含2727第二章地图数据结构邻接相同拓扑元素之间的关系如节点与节点、链与链、面与面等。邻接关系是借助于不同类型的拓扑元素描述的，如点通过链而邻接；线通过点而邻接；面通过点线而邻接关联是不

18、同拓扑元素之间的关系P1P2L1L2S1S2L1L2L3P1S1S2L1L2L3包含是面与其它拓扑元素之间的关系如点、线、面在某面内2828第二章地图数据结构在计算机地图制图系统中，也可能用到其他关系，如层次关系即相同元素之间的等级关系。如国家由省组成，省由市组成，市由区县组成等。拓扑关系的表示方法如何表示拓扑关系是拓扑数据结构的关键，其中几何数据的表示可参照矢量数据的简单数据结构。目前的计算机地图制图系统中，主要表示的是拓扑元素之间的基本的拓扑关系，表示方法多种多样。下面介绍一个常用的方法：节点、弧段、面块相互之间的所有关联拓扑关系都用关系表表达出来。2929N1N2N3N4N5

19、N6N7A1A2A3A4A5A6A7A8A9A10B1B2B3B4B5B1 B2 B3 B4 B5A1 A2 A3 A4 A5 A6 A7 A8 A9 A10N1 N2 N3 N4 N5 N6 N7面弧点3030第二章地图数据结构31 31第二章地图数据结构“-”表示面中含有岛3232第二章地图数据结构3333第二章地图数据结构虽然建立拓扑关系比较麻烦，但这种关系一旦建立，就为数据的采集、图形编辑和维护数据的一致性提供了大大的方便。反之还可利用共享数据来进行拓扑编辑。这种拓扑编辑，不但保证数字化原始数据的自动查错，而且可以自动形成封闭的多边形

20、边界，为由各个单独存储的弧段组成所需要的各类多边形及建立空间数据库奠定基础。具体算法如下：A、多边形连接编辑例如需要对多边形B1进行编辑，其算法过程为：从（弧点、面文件）中，检索出与当前编辑的多边形B1相关的所有记录3434第二章地图数据结构3535第二章地图数据结构*在检出的记录中，检查当前编辑的多边形B1所处的位置：如果B1位在左，将之与右相交换，同时也将该记录的节点位置作相应的变换，如果B1位在右，则所有数据记录不作改变。按上要求则检出的记录应变为：*从转换的记录中，任取一个节点为起点，按顺连接，使其能畅通并闭合。如果不能闭合或记录缺损或多余，说明文件有错，必

21、须修改。3636第二章地图数据结构B、结点连接编辑例如，需要对结点N1进行编辑，其过程相似。3737第二章地图数据结构如果首尾不能响应，或有缺损或多余，则表明文件有错，须改正，才能将其用于节点文件和多边形文件的自动生成以及数据库的建立。3838第二章地图数据结构拓扑数据结构的编码形式矢量拓扑数据结构的一般编码形式：空间实体的位置+标志+属性信息+拓扑关系空间实体位置：由“节点坐标文件”和“弧段坐标文件”来体现。标志码：同简单数据结构的标志码。属性信息：由属性特征表来体现。属性特征分为两种：一种是类别特征，即它是什么；第二种是具体的说明信息，或者说统计信息，

22、以解决两个同类目标的不同特征问题。类别特征，一般用“地物类编码表”表达；而具体说明信息则用“地物属性表”说明。3939第二章地图数据结构地物类编码表：地物类码+地物名+制图符号码+属性表名等。如下表：4040第二章地图数据结构地物属性表：地物标志码+所属地物类码+具体属性等。如下表：41 41第二章地图数据结构拓扑关系：如前所讲用节点、弧段、面块相互之间的关联拓扑关系表表达出来。记录拓扑关系的编码方法有多种，常见的有：*双重独立地图编码（Dual Independent Map Encoding,DIME）：节点坐标表+弧点、面拓扑关系表+属性特征表它最早

23、是以城市街道为编码的主体最早是美国人口统计系统采用的一种编码方法。4242第二章地图数据结构多边形拓扑关系的建立多边形拓扑关系的建立如果使用DIME或者类似的编码模型，多边形拓扑关系的表达需要描述以下实体之间的关系：多边形的组成弧段；弧段左右两侧的多边形，弧段两端的节点；节点相连的弧段。图2-4中共有4个节点，以A、B、C、D表示；6条弧段，用数字表示；以及I、II、III三个多边形（图2-4-a）。首先定义以下概念：由于弧段是有方向的，算法中将弧段A的起始节点称为首节点Ns(A)，而终止节点为尾节点NE(A)；考虑到弧段的方向性，沿弧段前进方向，将其相邻的多边形分别定义为左多

24、边形和右多边形PL(A)和PR(A)。在建立拓扑之前，首先将所有弧段的左右多边形（在实现中，可以用多边形的编码表示）都设置为空；然后对每个节点计算与其相连弧段的在连接处的角度，并进行排序（图2-4-b）（注意，这个排序是循环的）。4343第二章地图数据结构建立拓扑的算法如下：（1）得到第一条弧段A，并设置为当前弧段；（2）判断PL(A)和PR(A)是否为空。如果都非空，转到第一步，当所有弧段处理完毕后，算法结束；（3）如果左多边形为空，则创建一个新的多边形P，多边形的第一条弧段为当前弧段，并设置PL(A)=P，设置搜寻起始节点为Ns(A)，搜寻当前节点为NE(A)。如果右多边形为空

25、，则创建一个新的多边形P，多边形的第一条弧段为当前弧段，并设置PR(A)=P，设置搜寻起始节点N0=NE(A)，搜寻当前节点NC=NS(A)。（4）判断N0和NC是否相等，如果是，则多边形所有弧段都已经找到，转到第一步。（5）检查与当前节点相连接的、已经排列好的弧段序列，将当前弧段的下一条弧段A作为多边形的第二条弧段。（6）如果NC=NS(A)，设置PL(A)=P，NC=NE(A)；如果NC=NE(A)，设置PR(A)=P，NC=NS(A)，转到第四步。如图2-4-c所示，如果从弧段4开始搜寻，找到节点C后，根据弧段的排序，下一条弧段是2；然后找到节点A，弧段1，整个搜寻结束，建立多边形I，其

26、组成弧段为4、2、1。按照这种算法，生成多边形的弧段从多边形内部看，是逆时针排列的。如果节点弧段排序为顺时针，则算法中用PL(A)代替PR(A)，用PR(A)代替PL(A)，生成的多边形弧段是顺时针排列的。4444第二章地图数据结构图2-4：多边形拓扑的建立过程 4545第二章地图数据结构图2-5：带“岛”的多边形建立拓扑的结果多边形拓扑的建立，要注意多边形带“岛”的情况，按照上述算法，对于带“岛”的多边形，或者称为环，其包含的弧段构成了多个闭合曲线，并且“岛”的弧段排序是顺时针的（图2-5）（实际上，从环状多边形内部看，它仍然是逆时针的）。4646第二章地图数

27、据结构记录拓扑关系的编码方法：记录拓扑关系的编码方法有多种，常见的有：*双重独立地图编码（Dual Independent Map Encoding,DIME）：节点坐标表+弧点、面拓扑关系表+属性特征表它最早是以城市街道为编码的主体最早是美国人口统计系统采用的一种编码方法。4747第二章地图数据结构点号地物类码坐标N1T101X1，Y1N2T102X2，Y2节点坐标表4848第二章地图数据结构*链状双重独立式编码：节点坐标表+弧坐标表+弧段表+多边形表+属性特征表由美国计算机图形及空间分析实验室最先采用的方法节点坐标表：标志码+地物类码+（X，Y）坐标点号地

28、物类码坐标N1T101X1，Y1N2T102X2，Y2节点坐标表4949第二章地图数据结构弧坐标表：标志码+地物类码+弧上的节点弧段表：标志码+地物类码+起点+终点+左多边形+右多边形+内点（指向中间的指针）弧坐标表、弧段表可以合并如下：5050第二章地图数据结构多边形表：标志码+地物类码+组成多边形的弧段号等51 51第二章地图数据结构综上所述，为了将空间数据存入计算机：首先，将空间数据抽象为不同的专题（或图层）；其次，将专题层抽象成不同的类型；第三，将某一类型中的地理要素或实体分解为点、线、面状目标；第四，每个目标数据由定位数据（坐标）+拓扑数据+属性

29、数据组成。这样具有相同分类码的目标组成类型；多个相关联的类型构成专题层；若干个专题层构成图幅；全部数据组成数据库。5252第二章地图数据结构5353第二章地图数据结构二、栅格数据结构1、栅格数据的概念栅格数据：是由二维平面表像对应位置上像元灰度值所组成的阵列形式的数据。对栅格数据的有关说明A、像元（像素）：将地图制图区域的二维平面按行和列作规则划分，形成一个栅格阵列，其中各栅格阵列元素就是像元（像素）。5454第二章地图数据结构B、各个像元可用不同的灰度值来表示相应的属性值。各像元内其属性是均一的。因为，在栅格数据中，地表被分割为规则排列、相互邻接的方形地块

30、，每个地块与一像元相对应。因此C、栅格数据的比例尺（分辨率）：像元（栅格）的大小与地表相应单元的大小之比。D、栅格数据记录的是属性本身，位置可由对应的行列号确定。5555第二章地图数据结构栅格数据的表示方法点用一个栅格表示；线用沿其走向的一组相邻栅格表示面用其所覆盖的相邻栅格的集合表示5656第二章地图数据结构栅格数据的一般组织方法5757第二章地图数据结构有关相邻栅格单元四方向相邻八方向相邻一般讲，四方向相邻的栅格图形线画显得粗壮，但阶梯（锯齿）明显；而八方向相邻的栅格图形显得平滑圆润。5858第二章地图数据结构2、栅格数据结构栅格数据结构是以

31、规则的像元阵列来表示地图上空间地物或现象的分布的数据结构，其阵列中的每个数据表示地物或现象的属性特征。可以说，栅格数据结构就是像元阵列，像元的行列号确定实体的空间位置，像元的值表示实体的类型、等级等属性。（1）简单栅格数据结构最简单的栅格数据结构是将栅格数据看做一个数据矩阵，逐行记录各像元代码，这种记录栅格数据的编码方法直接栅格编码栅格文件：按直接栅格编码记录栅格数据的文件。通常在文件头中还存有该栅格数据的行数和列数。5959第二章地图数据结构直接栅格编码方法：A A A AA B B BA A B BA A B B方法一：逐行从左向右AAAAABBBAABBAABBA A A A

32、A B B BA A B BA A B B方法二：奇数行从左向右，偶数行从右向左AAAABBBAAABBBBAA6060第二章地图数据结构直接栅格编码具有简单、直观、信息无压缩和处理方便的特点，但因没有压缩，占用了大量的内存空间。（2）栅格数据的压缩编码基本思想：对于一个栅格图形，常常有相邻若干栅格单元具有相同的属性代码，因此，可采用某种方法压缩那些重复的内容。常见的方法：链码（Chain Encoding)游程码(Run-length Encoding)块码(Block Encoding)四叉树码(Quadtree Encoding)61 61第二章地图数据结构链码

33、（又称Freeman码、边界码）主要用记录线状地物或面状地物的边界:由某一起点和一系列在基本方向上的单位矢量组成。单位矢量的长度默认为一个栅格单元，每个后续点可能位于其前继点的8个基本方向之一。前两个数字表示起点的行列号，从第三个数字开始是每个后续点的单位矢量方向6262第二章地图数据结构0123456701234561234563,270123456链式编码对多边形的表示具有很强的压缩能力，且具有一定的运算功能，如面积和周长计算等，且探测边界急弯部分容易，适用于存储图形数据。其缺点是对叠置运算难实施，对局部修改将改变整体结构，效率低，而且相邻边界有冗余6363第二章地图数

34、据结构游程码逐行将相邻同值的网格合并，并记录合并后网格的值及合并网格的长度。游程编码结构的建立方法ABC原始地面 ABC栅格化栅格数据矩阵6464第二章地图数据结构方法一：属性值（属性代码）+重复个数栅格数据矩阵A逐行单独编码6565第二章地图数据结构栅格数据矩阵B逐行混合编码A A，6 6A A，5 5，C C，1 1A A，4 4，C C，2 2B B，4 4，C C，2 2B B，4 4，C C，2 2B B，3 3，C C，3 3代码，个数6666第二章地图数据结构栅格数据矩阵C串行编号编码序号+属性代码+游程长 1 A 11 2 C 1 3

35、 A 4 4 C 2 5 B 4 6 C 2 7 B 4 8 C 2 9 B 3 10 C 36767第二章地图数据结构方法二：属性值（属性代码）+位置A逐行单独编码栅格数据矩阵行号属性值列号61，A，652，A，562，C，643，A，463，C，644，B，464，C，645，B，465，C，636，B，366，C，66868第二章地图数据结构栅格数据矩阵行号属性值列号属性值列号 6B逐行混合编码1，A，6562，A，5，C，6463，A，4，C，6464，B，4，C，6465，B，4，C，6366，B，3，C，66969第二章地图数据结构C

36、串行点号编码（序号）属性值 (游程终)点号10A,1011C,1115A,1517C,1721B,2123C,2327B,2729C,2932B,3235C,357070第二章地图数据结构方法三:按行的顺序存储多边形内的各个像元的列号，即在某行上从左至右存储属该多边形的始末像元的列号。71 71第二章地图数据结构块码块式编码是将游程编码扩大到二维的情况，把多边形范围分成由像元组成的正方形，然后对各个正方形进行编码。编码原则：行号、列号、边长、属性代码采用这种结构，如果一个多边形所能包含的正方形越大，边界越简单，效果越好。面积计算具有明显的优势。7272123456789

37、10111213141516123456789AAAAAA10AAAAAAAAAA11AAAAAAAAA12AAAAAAAAA13AAAAAAAAAAAA14AAAAAAAAAAAA15AAAAAAAA169,2,1,A9,3,1,A9,6,1,A9,8,1,A9,9,2,A10,1,1,A10,2,1,A10,3,4,A10,7,2,A11,1,2,A11,9,1,A12,7,2,A12,9,1,A13,9,1,A13,12,1,A13,13,1,A13,14,1,A13,15,2,A14,5,1,A14,6,1,A14,7,2,A14,9,2,A14,11,2,A14,13,2,A7373

38、第二章地图数据结构四叉树结构上面我们讨论了块式编码，现在我们反过来想一想，当我们把一幅图栅格化的时候，能不能把属性一致的区域的栅格单元作大一些，而在有细节的区域的栅格单元作小一些，从而使存储的数据少一些呢？答案是可以的。这种思路可用四叉树编码来实现。四叉树编码的基本思想:首先把一幅图像或栅格地图等分成四部分，逐块检查其格网值，如果某个格的所有值相同，则这个格就不再往下分割；否则，把它再分割成四个子区域，这样直到每个子块都只含有相同的属性值为止。7474第二章地图数据结构134569 10151618131411191227 817A1B6NWSWSENE1112CDE8

39、1097父指针父指针子指针子指针树叉树叉叶子叶子叶子不可分；树叉可再分。7575第二章地图数据结构上面称为“top-down”的从上而下的分割方法，这种方法速度较慢，且有大量重复检查才能确定划分，如图中的7、8、9区域需要检查4次。常规四叉树也可以采用“bottom-up”的方式，对栅格数据按一定顺序进行检测，如果每相邻四个格网值相同，则进行合并，逐次往上递归。这种方式，速度较快。7676第二章地图数据结构常规四叉树除了要记录叶结点外，还要记录树叉结点，结点之间的联系靠指针表达。从上图可看出每个结点需要6个量表达：父结点（前趋），四个子结点指针（后继）和本结点的属性值。

40、这就需要大量的存储空间，所以在数据压缩方面常规四叉树结构作用不大，但在数据索引和图幅索引等方面得到了很好的应用。为压缩数据人们则多采用线性四叉树方法。7777第二章地图数据结构线性四叉树基本思想：不记录中间节点，不需要指针，只存储最后叶结点信息，包括结点的位置（地址）、属性值。线性四叉树叶结点的编号需要遵照一定的规则，这种编号称为地址码，隐含了叶结点的位置信息。最常用的地址码是四进制或十进制的Morton码。7878第二章地图数据结构基于四进制的Morton码(MQ)及四叉树的建立第一步：将十进制的行列号（II，JJ）转换成二进制数（Ib,Jb）表示。JJ0123456

41、7Jb00011011100101110111IIIb00010121031141005101611071117979第二章地图数据结构第二步：Morton码MQ=2Ib+JbJJ01234567Jb00011011100101110111IIIb00000000101001110010111011110100200301201310210311211321002002103003112012113013131102202303203312212313213341002002012102113003013103115101202203212213302303312313611022

42、022123023132032133033171112222232322333223233323338080第二章地图数据结构第三步，在排好的线性表中，依次检查每四个相邻MQ码对应的属性值，如果相同则合并为一个大块，否则将这四个格网记录下来，内容包括MQ码、属性值。再依次检查每四个相邻的大块的属性值，若不同则记录下来，如果相同则合并，如此直到没有可合并的为止。81 81第二章地图数据结构JJ01234567Jb00011011100101110111IIIb000000001010011100101110111101002003012013102103112113210

43、020021030031120121130131311022023032033122123132133410020020121021130030131031151012022032122133023033123136110220221230231320321330331711122222323223332232333233301MQ属性值属性值000000100020003001000110012001300200021002200230030003100320033010001010102010308282第二章地图数据结构基于十进制的线性四叉树编码基于四进制的编码存在着一个问题

44、。大多数语言不支持四进制变量，需要用十进制的Morton码MD。因此人们逐渐提出采用十进制的Morton码作为线性四叉树的地址码。方法：设十进制表示的行、列号在计算机内的二进制分别为：8383第二章地图数据结构8484第二章地图数据结构然后再将得到的Md由二进制数转换为十进制数即可。用类似的方法，也可以由Md码反求栅格单元的行列号（大家在下面可以自己做一做）JJ01234567Jb011011100101110111IIIb00014516172021112367181922232108912132425282931110111415262730314100323336

45、3748495253510134353839505154556110404144455657606171114243464758596263Md码码行号行号列号列号8585第二章地图数据结构例如：II=5 JJ=5Ib=1 0 1 Jb=1 0 1Md=（1 1 0 0 1 1）2Md=518686第二章地图数据结构在排好的线性表中，依次检查每四个相邻Md码对应的属性值，如果相同则合并为一个大块，否则将这四个格网记录下来，内容包括Md码、属性值。再依次检查每四个相邻的大块的属性值，若不同则记录下来，如果相同则合并，如此直到没有可合并的为止。8787第二章地图数据

46、结构二维游程编码结构我们注意到，在生成的线性四叉树结构表中虽然我们对数据进行了压缩，但仍存在前后结点值相同的情况，因而可以采取进一步的压缩表达，即将属性值相同的前后结点合并成一个值，形成一个线性表列。其记录规则：先记录入口地址和格网值，依次扫描线性表，若后一格网的值与前一格网值不同，记录后一格网的地址和格网值，可直接形成线性表。这种记录方法，非常类似于传统的一维行程编码，所以也称为二维游程编码8888第二章地图数据结构*具体过程：如下第一步：确定十进制线性四叉树的Morton地址码1514111011313129810276320115410000113102011000JbJ

47、JIbII行号行号Md码码列号列号8989第二章地图数据结构第二步：确定十进制线性四叉树表0145236789121310111415属性值属性值1 014121513084第三步：二维行程编码第三步：二维行程编码14121309090第二章地图数据结构该编码方法的优点是：压缩率高，且解压方便；阵列中各部分的分辨率可变，即可减少存量，又可精确地表示图形结构，易于进行图形操作和运算。缺点是：具有相同形状和大小的多边形可得出完全不同的编码，不利于形状的分析和模式识别。014523678912131011141514121300145236789121310111415014

48、 2367 91 91第二章地图数据结构第三节矢量、栅格转换矢栅的相互转换，一直是地理信息系统的技术难题之一。一、矢量格式向栅格格式转换矢量数据转换为栅格数据也称栅格化，其目的在于方便地进行空间分析，因为栅格数据对于多要素的重叠操作运算较矢量数据容易实现。习惯上，在矢量数据中，点的坐标用（X，Y）来表示，而在栅格数据中，点的坐标用点所在栅格的行列号（I，J）来表示。1、点的栅格化将点P的矢量坐标（XP，YP）换算成栅格的行、列号（II，JJ）9292第二章地图数据结构yxoOX0Y0PYpXpII=INTII=INT（Y0-YPY0-YP）/d/d）JJ=INTJJ=

49、INT（XP-X0XP-X0）/d/d）II,JJII,JJdII=INT（Y0-YP）/d）JJ=INT（XP-X0）/d）9393第二章地图数据结构2、线段的栅格化线段栅格化步骤如下：A、两端点栅格化 B、求出这两个端点位置的行数差和列数差：行数差=II2-II1、列数差=JJ2-JJ1C、计算直线与栅格中心线的交点坐标若行数差列数差，则逐行求出本行中心线与已知直线的交点坐标9494第二章地图数据结构X1，Y1X2，Y2D、将求得的交点栅格化，并将其所在的栅格“赋值”。如图II1=INT（Y0-Y1）/d）JJ1=INT（X1-X0）/d）II1JJ1II2=IN

50、T（Y0-Y2）/d）JJ2=INT（X2-X0）/d）II2JJ2Y中心线=Y0-II1*d-3/2*dY中心线=Y0-II1*d-5/2*dY中心线=Y0-II1*d-7/2*d9595第二章地图数据结构若行数差列数差，则逐列求出本列中心线与已知直线的交点坐标：将求得的交点栅格化，并将其所在的栅格“赋值”。X1,y1X2,y29696第二章地图数据结构这里，之所以要分两种情况处理，是为了使产生的被“赋值的栅格相互连通，避免出现间断现象9797第二章地图数据结构具体编程思路如下开始开始直线两端点栅格化直线两端点栅格化II1=（Y0-Y1）/d；JJ1=（

展开阅读全文