地图数据结构

*,第二章 地 图 数 据 结 构,计算机地图制图,1,第二章 地图数据结构,21 地图数据的描述方法,地图数据：,地图诸要素的数字化表示，是以点、线、面等方式采用编码技术对地理空间物体进行特征描述及在物体间建立相互联系的数据集。,一、地图对地理空间的描述,地图是现实世界的模型，它按照一定的比例和投影原则，有选择地将复杂的三维地理空间的某些内容投影到二维平面介质上，并用符号将这些内容要素表现出来。,2,地图学中，把地理空间的实体分为点、线、面三种要素(对象)，分别用点状、线状、面状符号来表示。,点实体,点实体是有特定的位置、维数为,0,的实体。,实体点：,用来代表一个实体；,如城市,注记点：,用于定位注记；,北 京,内点：,用于记录多边形的属性，存在于多边形内；,结点：,表示线的终点和起点；,3,结点：,表示线的终点和起点；,节点：,它是两条或多条连线或链的拓扑连结点,拐点：,表示线段和弧段的内部点（特殊的节点）。,(2)线实体（亦称为线段、弧、链、环等）,线实体是维数为1的实体，由一系列坐标点表示。,特征：,实体长度：,从起点到终点的总长；,弯曲度：,用于表示如道路拐弯时弯曲的程度；,方向性：,如河流从上游到下游，公路有单双向之分；,4,(3)面(多边形)实体,面(多边形)实体是维数为2的实体，由一个封闭的坐标点序列外加内点表示，,是对湖泊、岛屿、地块等现象的描述。,具有以下特征：,周长； 面积；岛或非岛；内岛或齿状；重叠性等,内面：,不包括边界的面,广义多边形,（其他多边形覆盖面的周边以外的面，它没有外环，有一个或多个内环）,虚多边形,（以其他多边形为界的多边形）,5,二、地图数据的基本特征,地图数据具有空间特征、属性特征及时间特征。,1空间特征,(1)空间位置,空间位置用以描述事物或现象的地理位置，又称几何特征、定位特征。,通常用地理坐标系、平面直角坐标系来表示,，也称几何特征，包括空间实体的,位置、大小、形状、分布状况,等，表明“在哪里”。,(2)空间关系,地理空间实体之间存在的一些具有空间特性的关系,拓扑关系：,拓扑变化下的拓扑不变量，如邻接关系、关联关系和包含关系等；,方位关系：,实体在地理空间中的某种顺序，如左右、东南西北等；,度量关系：,用地理空间中的度量来描述的实体之间的关系，如实体之间的距离,6,2属性特征,属性特征用以描述事物或现象的特性，如事物或现象的类别、等级、数量、名称等，用来说明“是什么”。,属性特征通常分定性和定量两种：,（1）定性特征,包括名称、类型等；,（2）定量特征,包括数量、等级等。,3时间特征,时间特征用以描述地理实体随着时间而变化的特征。目前的计算机地图制图还较少考虑到地图数据的时间特征，只考虑其属性特征与空间特征的结合。由于地图数据具有时间维，过时的信息虽不具有现势性，却可以作为历史性数据保存起来，但这样做会增大计算机地图制图表示和处理数据的难度。,7,图2-1：空间数据的基本特性Jack Dangermond,1984,8,三、地图数据的基本类型,根据地图数据的特征，可以把地图数据分为,空间数据、关系数据、属性数据,三类,。,1空间数据,也称几何数据，即描述地理现象或地理实体的空间位置、形状、大小等的数据。,根据地理要素的空间分布待征和空间实体分类，可以将地理空间数据分为点、线、面三种类型。,9,(1),点类型,点类型可以描述如城乡居民地、工厂、学校、医院、机关、车站、山峰、隘口等现象。这里，“点”是一个相对的抽象概念，即从较大的空间规模上来观测这些地物，就能把它们都归结为点状分布的地理现象，因此,能用一个点的坐标(或栅格像元)来描述其空间位置,。而如果从较小的空间尺度上来观察这些地理现象，它们中的多数将可以用一个面状特征来描述。例如同一个城市，在小比例尺地图上表现为点状分布，而在大比例尺地图上则可表现为面状分布，其内部表示了十分详细的城市街道分布状况。,(2)线类型,线类型描述如河流、运河、海岸、铁路、公路、地下管网、行政边界等线状分布的地理现象。这里的“线”(有时也称“弧”)也是一个相对的抽象概念。它们的,空间位置数据是一线状坐标串(或栅格像元集合),。,(3),面类型,面类型描述如土地、水域、森林、草原、沙漠等具有大范围连续(或断续)面状分布特征的现象。这里的“面”是一个相对的抽象概念，有时实地上不一定有明显的边界。描述面状特征的,空间数据是一封闭的面坐标串(或栅格像元集合),，通常称之为多边形。,10,2,空间数据的表示方法,一般地，表示地理现象的空间数据可以细分为：,类型数据：,例如考古地点、道路线和土壤类型的分布等；,面域数据：,例如随机多边形的中心点、行政区域界线和行政单元等；,网络数据：,例如道路交点、街道和街区等；,样本数据：,例如气象站、航线和野外样方的分布区等；,曲面数据：,例如高程点、等高线和等值区域；,文本数据：,例如地名、河流名称和区域名称；,符号数据：,例如点状符号、线状符号和面状符号（晕线）等（如图2-2所示）。,11,GIS中各种数据以及其表现,12,3,关系数据,关系数据是描述空间数据之间的空间关系的数据,。,上述点、线、面空间位置数据之间存在着某种特定的拓扑关系。这类数据表达了各类地理实体空间位置之间的相互关系，如空间数据的相邻、关联、包含等。,各种地理要素的空间位置数据在地图上的关系，可以概括为点、线、多边形之间的9种形式的拓扑关系：,点点、点线、点面；,线点、线线、线面；,面与点、面与线、面与面。,最常用的空间实体关系有6种，即：,点点、点线、点面；,线线、线面；,面面。,13,它们之间的相互关系：,邻接、,关联,、相交、相离、包含、重合,L-S,P-S,S-S,L-L,P-L,相离,相交,邻接,重合,包含,P-P,14,4属性数据,属性数据是描述空间实体属性特征的数据，也称非几何数据，,即描述地理现象或地理实体的定性或定量指标，包括语义与统计数据，如类型、等级、名称、状态等。有时也把描述时间特征的数据纳入该类。,属性数据中的定性(或定量)指标通常要经编码转换才能被计算机接受。为了方便计算机存储、管理和使用这些编码，需要研究统一的分类系统和编码。有关这方面的详细内容将在本书第3章中进行介绍。,15,第二节 地图的数据结构,地图的数据结构,主要指地图数据中,空间数据,的结构，,是指几何数据以什么形式在计算机中存储和处理。,地图的数据结构,矢量数据结构,栅格数据结构,一、矢量数据结构,1、矢量数据的概念,矢量本身是数学上的概念运用到地理信息系统中。矢量数据结构是表达地图空间数据的一种常见的数据结构，,16,矢量数据它通过记录坐标值的方式尽可能精确地表示呈点、线、面状分布的地理实体。,2、矢量数据的表达,在计算机地图制图中，各地理要素在二维平面上的矢量数据表达为：,点0维矢量：由一（x，y）坐标值表示；,线1维矢量：,由一串有序的（x，y）坐标表示；,面2维矢量：由一串有序的且首尾坐标相同的（x，y）,17,其中，,一维矢量可以闭合，但不能与自身相交。如果相交，则应以交点为界将一维矢量分成几个一维矢量。,如下图：（一维矢量可能空间关系）,a b c d,18,3、矢量数据结构的表示,矢量数据结构是最早用于表达地图空间数据的一种常见的数据结构，在计算机地图制图中，,表示矢量数据的结构时应考虑以下问题：,方便存储和处理,与属性数据的联系,矢量数据之间的拓扑关系,表示矢量数据的方法有多种，但基本上相似。下面按考虑问题的多寡分别介绍矢量数据的简单结构和拓扑结构及其有关的编码方法。,19,（1）简单数据结构及编码,简单的矢量数据结构,不考虑拓扑关系，可用于矢量数据的存储、处理、显示、输出以及一般的查询和检索。,有点、线、面三种基本的矢量数据结构形式。,点数据结构形式,标志码,属性码,（x，y）,标志码,属性码,标志码,（x，y）,+,或,标志码具有唯一性，,是按某种原则进行的编码（如顺序）,属性码是与点有关的基本属性的编码，可有多个。,（x，y）是定位坐标,20,线数据结构形式,当然也可采用将属性数据单独存放的方式,标志码和属性码的含义与点的数据结构相同；,坐标对数n：构成该线的坐标对个数；,坐标串：是构成线的矢量坐标对序列，共有n对,标志码,属性码,坐标对数n,坐标串（x1，y1）,坐标串（x1，y1）,坐标对数n,标志码,属性码,标志码,+,21,面（多边形）数据结构形式,常见的两种形式,标志码,属性码,坐标对数n,坐标串（x1，y1） （x1，y1）,标志码,属性码,弧段数n,弧段标志码集,弧段标志码01,坐标对数n,坐标串（x1，y1）,弧段标志码n,坐标对数m,坐标串（x1，y1）,有N个,这种方法可能会产生大量的数据冗余,这种方法保证了多边形公共边的唯一性,22,简单数据结构的编码形式,因在矢量的简单数据结构中不考虑拓扑关系，故其编码方法仅记录空间实体的位置、标志及属性信息，而不记录拓扑关系。常见的编码方法有,独立实体法,和,点位字典法,独立实体法,在独立实体法中，每个点线面都直接跟随它的空间坐标。每个实体的坐标都独立存储，毫不顾及相邻的多边形或线或点状地物。具体形式如下：,23,对面状实体而言，最末一点的坐标与第一点相等。使用这种方法 时，除了外轮廓线以外，多边形的边界线数据均获取和存储两次，这就会产生重叠或列隙（当取值误差时），,并产生数据冗余。为了消除裂缝，需要二次编辑。,点位字典法,以公用点位字典为基础建立一些系统，这克服了独立实体编码的某些局限性 。点位字典包含地图上每一个边界点的坐标，然后建立点、线、面的边界表，它们由点位序号构成。即：,点位字典表：点号、坐标（X，Y）,点实体：标志码，地物编码，点号,线实体：标志码，地物编码，（点号1，点号n）,面实体：标志码，地物编码，（点号1，点号n，点号1）,24,下图是两种表述方法的比较：,A,1 2,3,7,C,6 3,4,5,B,1,7,6 3,5,8,20,15,10,5,0,0 5 10 15 20,A,B,C,1 2,3,4,5,6,7,8,多边形,地物编码,坐标数据项,A,T301,X,1,，Y,1,；X,2,，Y,2,；X,3,，Y,3,；X,7,，Y,7,； X,1,，Y,1,B,T302,X,1,，Y,1,；X,7,，Y,7,；X,3,，Y,3,；X,6,，Y,6,；X,5,，Y,5,；X,8,，Y,8,； X,1,，Y,1,C,T305,X,3,，Y,3,；X,4,，Y,4,；X,5,，Y,5,；X,6,，Y,6,；X,3,，Y,3,独立实体编码,25,A,B,C,1 2,3,4,5,6,7,8,点号,坐标数据项,01,X,1,，Y,1,02,X,2,，Y,2,03,X,3,，Y,3,04,X,4,，Y,4,05,X,5,，Y,5,06,X,6,，Y,6,07,X,7,，Y,7,08,X,8,，Y,8,点位字典表,多边形,地物编码,点号,A,T301,1，2，3，7,B,T302,1，7，3，6，5，8,C,T305,3，4，5，6,点位字典表编码,26,（2）拓扑数据结构及编码,地图上两点间距离或方向会随地图投影的不同而发生变化，故,仅用距离或方向不能很好地描述地图要素间的空间关系,。如果引用拓扑关系来描述地图要素间的空间关系，则不论地图投影如何变化，其拓扑关系都不改变。可见拓扑关系能从本质上描述地图要素间的空间关系。,具有拓扑关系的矢量数据结构就是拓扑数据结构。,拓扑数据结构是现代计算机地图制图系统所必需的。尽管拓扑数据结构的表示方式还没有固定的格式，也没有形成标准，但其基本原理是相同的。,拓扑元素,点,（节点）、,线,（链、弧、边）、,面,（多边形）,基本拓扑关系,邻接、关联、包含,27,邻接 ,相同拓扑元素之间的关系,如节点与节点、链与链、面与面等。邻接关系是借助于不同类型的拓扑元素描述的，如点通过链而邻接；线通过点而邻接；面通过点线而邻接,关联,是不同拓扑元素之间的关系,P1,P2,L1,L2,S1,S2,L1,L2,L3,P1,S1,S2,L1,L2,L3,包含,是面与其它拓扑元素之间的关系,如点、线、面在某面内,28,在计算机地图制图系统中，也可能用到其他关系，如层次关系即相同元素之间的等级关系。如国家由省组成，省由市组成，市由区县组成等。,拓扑关系的表示方法,如何表示拓扑关系是拓扑数据结构的关键，其中几何数据的表示可参照矢量数据的简单数据结构。目前的计算机地图制图系统中，主要表示的是拓扑元素之间的基本的拓扑关系，表示方法多种多样。下面介绍一个常用的方法：,节点、弧段、面块相互之间的所有,关联,拓扑关系都用关系表表达出来。,29,N1,N2,N3,N4,N5,N6,N7,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,B1,B2,B3,B4,B5,B1 B2 B3 B4 B5,A1 A2 A3 A4 A5 A6 A7 A8 A9 A10,N1 N2 N3 N4 N5 N6 N7,面 弧 点,30,31,“-”表示面中含有岛,32,33,虽然建立拓扑关系比较麻烦，但这种关系一旦建立，就为数据的采集、图形编辑和维护数据的一致性提供了大大的方便。反之还可利用共享数据来进行拓扑编辑。这种拓扑编辑，不但保证数字化原始数据的自动查错，而且可以自动形成封闭的多边形边界，为由各个单独存储的弧段组成所需要的各类多边形及建立空间数据库奠定基础。具体算法如下：,A、,多边形连接编辑,例如需要对多边形B1进行编辑，其算法过程为：,从（弧点、面文件）中，检索出与当前编辑的多边形B1相关的所有记录,34,35,*在检出的记录中，检查当前编辑 的多边形B1所处的位置：如果B1位在左，将之与右相交换，同时也将该记录的节点位置作相应的变换，如果B1位在右，则所有数据记录不作改变。按上要求则检出的记录应变为：,*从转换的记录中，任取一个节点为起点，按顺连接，使其能畅通并闭合。如果不能闭合或记录缺损或多余，说明文件有错，必须修改。,36,B、结点连接编辑,例如，需要对结点N1进行编辑，其过程相似。,37,如果首尾不能响应，或有缺损或多余，则表明文件有错，须改正，才能将其用于节点文件和多边形文件的自动生成以及数据库的建立。,38,拓扑数据结构的编码形式,矢量拓扑数据结构的一般编码形式：空间实体的位置+标志+属性信息+拓扑关系,空间实体位置：由“节点坐标文件”和“弧段坐标文件”来体现。,标志码：同简单数据结构的标志码。,属性信息：由属性特征表来体现。,属性特征分为两种：一种是类别特征，即它是什么；第二种是具体的说明信息，或者说统计信息，以解决两个同类目标的不同特征问题。,类别特征，一般用“地物类编码表”表达；而具体说明信息则用“地物属性表” 说明。,39,地物类编码表：,地物类码+地物名+制图符号码+属性表名等。如下表：,40,地物属性表：,地物标志码+所属地物类码+具体属性等。如下表：,41,拓扑关系：如前所讲用,节点、弧段、面块相互之间的关联拓扑关系表表达出来。,记录拓扑关系的编码方法有多种，常见的有：,*双重独立地图编码（Dual Independent Map Encoding,DIME）：节点坐标表+弧点、面拓扑关系表+属性特征表,它最早是以城市街道为编码的主体 最早是美国人口统计系统采用的一种编码方法。,42,多边形拓扑关系的建立,如果使用DIME或者类似的编码模型，多边形拓扑关系的表达需要描述以下实体之间的关系：,多边形的组成弧段；,弧段左右两侧的多边形，弧段两端的节点；,节点相连的弧段。,图2-4中共有4个节点，以A、B、C、D表示；6条弧段，用数字表示；以及I、II、III三个多边形（图2-4-a）。,首先定义以下概念：,由于弧段是有方向的，算法中将弧段,A,的起始节点称为首节点,Ns(A),，而终止节点为尾节点,NE(A),；,考虑到弧段的方向性，沿弧段前进方向，将其相邻的多边形分别定义为左多边形和右多边形,PL(A),和,PR(A),。,在建立拓扑之前，首先将所有弧段的左右多边形（在实现中，可以用多边形的编码表示）都设置为空；然后对每个节点计算与其相连弧段的在连接处的角度，并进行排序（图2-4-b）（注意，这个排序是循环的）。,43,建立拓扑的算法如下：,（1）得到第一条弧段A，并设置为当前弧段；,（2）判断,PL(A),和,PR(A),是否为空。如果都非空，转到第一步，当所有弧段处理完毕后，算法结束；,（3）如果左多边形为空，则创建一个新的多边形,P,，多边形的第一条弧段为当前弧段，并设置,PL(A)=P,，设置搜寻起始节点为,Ns(A),，搜寻当前节点为,NE(A),。如果右多边形为空，则创建一个新的多边形,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，其组成弧段为4、2、1。,按照这种算法，生成多边形的弧段从多边形内部看，是逆时针排列的。如果节点弧段排序为顺时针，则算法中用,PL(A),代替,PR(A),，用,PR(A),代替,PL(A),，生成的多边形弧段是顺时针排列的。,44,图2-4：多边形拓扑的建立过程,45,图2-5：带“岛”的多边形建立拓扑的结果,多边形拓扑的建立，要注意多边形带“岛”的情况，按照上述算法，对于带“岛”的多边形，或者称为环，其包含的弧段构成了多个闭合曲线，并且“岛”的弧段排序是顺时针的（图2-5）（实际上，从环状多边形内部看，它仍然是逆时针的）。,46,记录拓扑关系的编码方法：,记录拓扑关系的编码方法有多种，常见的有：,*双重独立地图编码（Dual Independent Map Encoding,DIME）：节点坐标表+弧点、面拓扑关系表+属性特征表,它最早是以城市街道为编码的主体 最早是美国人口统计系统采用的一种编码方法。,47,点号,地物类码,坐标,N1,T101,X,1,，Y,1,N2,T102,X,2,，Y,2,节点坐标表,48,*,链状双重独立式编码：节点坐标表+弧坐标表+弧段表+多边形表+属性特征表,由美国计算机图形及空间分析实验室最先采用的方法,节点坐标表：标志码+地物类码+（X，Y）坐标,点号,地物类码,坐标,N1,T101,X,1,，Y,1,N2,T102,X,2,，Y,2,节点坐标表,49,弧坐标表：标志码+地物类码+弧上的节点,弧段表：标志码+地物类码+起点+终点+左多边形+右多边形+内点（指向中间的指针）,弧坐标表、弧段表可以合并 如下：,50,多边形表：标志码+地物类码+组成多边形的弧段号等,51,综上所述，为了将空间数据存入计算机：,首先，将空间数据抽象为不同的专题（或图层）；其次，将专题层抽象成不同的类型；第三，将某一类型中的地理要素或实体分解为点、线、面状目标；第四，每个目标数据由定位数据（坐标）+拓扑数据+属性数据组成。这样具有相同分类码的目标组成类型；多个相关联的类型构成专题层；若干个专题层构成图幅；全部数据组成数据库。,52,53,二、栅格数据结构,1、栅格数据的概念,栅格数据：是由二维平面表像对应位置上像元灰度值所组成的阵列形式的数据。,对栅格数据的有关说明,A、像元（像素）：将地图制图区域的二维平面按行和列作规则划分，形成一个栅格阵列，其中各栅格阵列元素就是像元（像素）。,54,B、各个像元可用不同的灰度值来表示相应的属性值。各像元内其属性是均一的。,因为，在栅格数据中，地表被分割为规则排列、相互邻接的方形地块，每个地块与一像元相对应。因此,C、栅格数据的比例尺（分辨率）：像元（栅格）的大小与地表相应单元的大小之比。,D、栅格数据记录的是属性本身，位置可由对应的行列号确定。,55,栅格数据的表示方法,点用一个栅格表示；,线用沿其走向的一组相邻栅格表示,面用其所覆盖的相邻栅格的集合表示,56,栅格数据的一般组织方法,57,有关相邻栅格单元,四方向相邻,八方向相邻,一般讲，四方向相邻的栅格图形线画显得粗壮，但阶梯（锯齿）明显；而八方向相邻的栅格图形显得平滑圆润。,58,2、栅格数据结构,栅格数据结构是以规则的像元阵列来表示地图上空间地物或现象的分布的数据结构，其阵列中的每个数据表示地物或现象的属性特征。可以说，栅格数据结构就是像元阵列，像元的行列号确定实体的空间位置，像元的值表示实体的类型、等级等属性。,（1）简单栅格数据结构,最简单的栅格数据结构是将栅格数据看做一个数据矩阵，逐行记录各像元代码，这种记录栅格数据的编码方法,直接栅格编码,栅格文件：,按直接栅格编码记录栅格数据的文件。,通常在文件头中还存有该栅格数据的行数和列数。,59,直接栅格编码方法：,A,A,A,A,A,B,B,B,A,A,B,B,A,A,B,B,方法一：逐行从左向右,AAAA,ABBB,AABB,AABB,A,A,A,A,A,B,B,B,A,A,B,B,A,A,B,B,方法二：奇数行从左向右，偶数行从右向左,AAAA,BBBA,AABB,BBAA,60,直接栅格编码具有简单、直观、信息无压缩和处理方便的特点，但因没有压缩，占用了大量的内存空间。,（2）栅格数据的压缩编码,基本思想：对于一个栅格图形，常常有相邻若干栅格单元具有相同的属性代码，因此，可采用某种方法压缩那些重复的内容。,常见的方法：,链码（Chain Encoding),游程码(Run-length Encoding),块码 (Block Encoding),四叉树码(Quadtree Encoding),61,链码（又称Freeman码、边界码）,主要用记录线状地物或面状地物的边界:,由某一起点和一系列在基本方向上的单位矢量组成。单位矢量的长度默认为一个栅格单元，每个后续点可能位于其前继点的8个基本方向之一。前两个数字表示起点的行列号，从第三个数字开始是每个后续点的单位矢量方向,62,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,1,2,3,4,5,6,3,2,7,0,1,2,3,4,5,6,链式编码对多边形的表示具有很强的压缩能力，且具有一定的运算功能，如面积和周长计算等，且探测边界急弯部分容易，适用于存储图形数据。其缺点是对叠置运算难实施，对局部修改将改变整体结构，效率低，而且相邻边界有冗余,63,游程码,逐行将相邻同值的网格合并，并记录合并后网格的值及合并网格的长度。,游程编码结构的建立方法,A,B,C,原始地面,A,B,C,栅格化,栅格数据矩阵,64,方法一：,属性值,（属性代码）,+重复个数,栅格数据矩阵,A逐行单独编码,65,栅格数据矩阵,B,逐行混合编码,A，6,A，5，C，1,A，4，C，2,B，4，C，2,B，4，C，2,B，3，C，3,代码，个数,66,栅格数据矩阵,C串行编号编码,序号+属性代码+游程长,1 A 11,2 C 1,3 A 4,4 C 2,5 B 4,6 C 2,7 B 4,8 C 2,9 B 3,10 C 3,67,方法二：属性值,（属性代码）,+位置,A逐行单独编码,栅格数据矩阵,行号 属性值 列号,6,1， A ， 6,5,2， A ， 5,6,2， C ， 6,4,3， A ， 4,6,3， C ， 6,4,4， B ， 4,6,4， C ， 6,4,5， B ， 4,6,5， C ， 6,3,6， B ， 3,6,6， C ， 6,68,栅格数据矩阵,行号 属性值 列号 属性值 列号 ,6,B,逐行混合编码,1， A ， 6,5,6,2， A ， 5， C， 6,4,6,3， A ， 4， C， 6,4,6,4， B ， 4， C， 6,4,6,5， B ， 4， C， 6,3,6,6， B ， 3， C， 6,69,C,串行点号编码,（序号）属性值 (游程终)点号,10,A, 10,11,C, 11,15,A, 15,17,C, 17,21,B, 21,23,C, 23,27,B, 27,29,C, 29,32,B, 32,35,C, 35,70,方法三: 按行的顺序存储多边形内的各个像元的列号，即在某行上从左至右存储属该多边形的始末像元的列号。,71,块码,块式编码是将游程编码扩大到二维的情况，把多边形范围分成由像元组成的正方形，然后对各个正方形进行编码。编码原则：,行号、列号、边长、属性代码,采用这种结构，如果一个多边形所能包含的正方形越大，边界越简单，效果越好。面积计算具有明显的优势。,72,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,1,2,3,4,5,6,7,8,9,A,A,A,A,A,A,10,A,A,A,A,A,A,A,A,A,A,11,A,A,A,A,A,A,A,A,A,12,A,A,A,A,A,A,A,A,A,13,A,A,A,A,A,A,A,A,A,A,A,A,14,A,A,A,A,A,A,A,A,A,A,A,A,15,A,A,A,A,A,A,A,A,16,9,2,1,A,9,3,1,A,9,6,1,A,9,8,1,A,9,9,2,A,10,1,1,A,10,2,1,A,10,3,4,A,10,7,2,A,11,1,2,A,11,9,1,A,12,7,2,A,12,9,1,A,13,9,1,A,13,12,1,A,13,13,1,A,13,14,1,A,13,15,2,A,14, 5,1,A,14, 6,1,A,14, 7,2,A,14, 9,2,A,14,11,2,A,14,13,2,A,73,四叉树结构,上面我们讨论了块式编码，现在我们反过来想一想，当我们把一幅图栅格化的时候，能不能把属性一致的区域的栅格单元作大一些，而在有细节的区域的栅格单元作小一些，从而使存储的数据少一些呢？答案是可以的。这种思路可用四叉树编码来实现。,四叉树编码的基本思想:,首先把一幅图像或栅格地图等分成四部分，逐块检查其格网值，如果某个格的所有值相同，则这个格就不再往下分割；否则，把它再分割成四个子区域，这样直到每个子块都只含有相同的属性值为止。,74,1,3,4,5,6,9,10,15,16,18,13,14,11,19,12,2,7 8,17,A,1,B,6,NW,SW,SE,NE,11,12,C,D,E,8,10,9,7,父指针,子指针,树叉,叶子,叶子不可分； 树叉可再分。,75,上面称为,“top-down”的从上而下的分割方法，这种方法速度较慢，且有大量重复检查才能确定划分，如图中的7、8、9区域需要检查4次。,常规四叉树也可以采用“bottom-up”的方式，对栅格数据按一定顺序进行检测，如果每相邻四个格网值相同，则进行合并，逐次往上递归。这种方式，速度较快。,76,常规四叉树,除了要记录叶结点外，还要记录树叉结点，结点之间的联系靠指针表达。从,上图,可看出每个结点需要,6个量表达：父结点（前趋），四个子结点指针（后继）和本结点的属性值。,这就需要大量的存储空间，所以在数据压缩方面常规四叉树结构作用不大，但在数据索引和图幅索引等方面得到了很好的应用。,为压缩数据人们则多采用线性四叉树方法。,77,线性四叉树,基本思想：不记录中间节点，不需要指针，只存储最后叶结点信息，包括结点的,位置（地址）、属性值。,线性四叉树叶结点的编号需要遵照一定的规则，这种编号称为地址码，隐含了叶结点的位置信息。最常用的地址码是四进制或十进制的Morton码。,78,基于四进制的Morton码(M,Q,)及四叉树的建立,第一步：将十进制的行列号（II，JJ）转换成二进制数（Ib,Jb）表示。,JJ,0,1,2,3,4,5,6,7,Jb,00,01,10,11,100,101,110,111,II,Ib,0,00,1,01,2,10,3,11,4,100,5,101,6,110,7,111,79,第二步：Morton码MQ=2Ib+Jb,JJ,0,1,2,3,4,5,6,7,Jb,00,01,10,11,100,101,110,111,II,Ib,0,00,000,001,010,011,100,101,110,111,1,01,002,003,012,013,102,103,112,113,2,10,020,021,030,031,120,121,130,131,3,11,022,023,032,033,122,123,132,133,4,100,200,201,210,211,300,301,310,311,5,101,202,203,212,213,302,303,312,313,6,110,220,221,230,231,320,321,330,331,7,111,222,223,232,233,322,323,332,333,80,第三步，在排好的线性表中，依次检查每四个相邻MQ码对应的属性值，如果相同则合并为一个大块，否则将这四个格网记录下来，内容包括MQ码、属性值。再依次检查每四个相邻的大块的属性值，若不同则记录下来，如果相同则合并，如此直到没有可合并的为止。,81,JJ,0,1,2,3,4,5,6,7,Jb,00,01,10,11,100,101,110,111,II,Ib,0,00,000,001,010,011,100,101,110,111,1,01,002,003,012,013,102,103,112,113,2,10,020,021,030,031,120,121,130,131,3,11,022,023,032,033,122,123,132,133,4,100,200,201,210,211,300,301,310,311,5,101,202,203,212,213,302,303,312,313,6,110,220,221,230,231,320,321,330,331,7,111,222,223,232,233,322,323,332,333,0,1,MQ,属性值,000,0,001,0,002,0,003,0,010,0,011,0,012,0,013,0,020,0,021,0,022,0,023,0,030,0,031,0,032,0,033,0,100,0,101,0,102,0,103,0,82,基于十进制的线性四叉树编码,基于四进制的编码存在着一个问题。大多数语言不支持四进制变量，需要用十进制的Morton码M,D,。因此人们逐渐提出采用十进制的Morton码作为线性四叉树的地址码。,方法：,设十进制表示的行、列号在计算机内的二进制分别为：,83,84,然后再将得到的Md由二进制数转换为十进制数即可。用类似的方法，也可以由Md码反求栅格单元的行列号（大家在下面可以自己做一做）,JJ,0,1,2,3,4,5,6,7,Jb,0,1,10,11,100,101,110,111,II,Ib,0,0,0,1,4,5,16,17,20,21,1,1,2,3,6,7,18,19,22,23,2,10,8,9,12,13,24,25,28,29,3,11,10,11,14,15,26,27,30,31,4,100,32,33,36,37,48,49,52,53,5,101,34,35,38,39,50,51,54,55,6,110,40,41,44,45,56,57,60,61,7,111,42,43,46,47,58,59,62,63,M,d,码,行号,列号,85,例如：,II=5 JJ=5,Ib=1 0 1 Jb=1 0 1,Md= （1 1 0 0 1 1）,2,Md=51,86,在排好的线性表中，依次检查每四个相邻Md码对应的属性值，如果相同则合并为一个大块，否则将这四个格网记录下来，内容包括Md码、属性值。再依次检查每四个相邻的大块的属性值，若不同则记录下来，如果相同则合并，如此直到没有可合并的为止。,87,二维游程编码结构,我们注意到，在生成的线性四叉树结构表中虽然我们对数据进行了压缩，但仍存在前后结点值相同的情况，因而可以采取进一步的压缩表达，即将属性值相同的前后结点合并成一个值，形成一个线性表列。,其记录规则：先记录入口地址和格网值，依次扫描线性表，若后一格网的值与前一格网值不同，记录后一格网的地址和格网值，可直接形成线性表。这种记录方法，非常类似于传统的一维行程编码，所以也称为二维游程编码,88,*具体过程：如下,第一步：确定十进制线性四叉树的Morton地址码,15,14,11,10,11,3,13,12,9,8,10,2,7,6,3,2,01,1,5,4,1,0,00,0,11,3,10,2,01,1,00,0,Jb,JJ,Ib,II,行号,Md码,列号,89,第二步：确定十进制线性四叉树表,0,1,4,5,2,3,6,7,8,9,12,13,10,11,14,15,属性值,1 0,14,12,15,13,0,8,4,第三步：二维行程编码,14,12,13,0,90,该编码方法的优点是：压缩率高，且解压方便；阵列中各部分的分辨率可变，即可减少存量，又可精确地表示图形结构，易于进行图形操作和运算。,缺点是：具有相同形状和大小的多边形可得出完全不同的编码，不利于形状的分析和模式识别。,0,1,4,5,2,3,6,7,8,9,12,13,10,11,14,15,14,12,13,0,0,1,4,5,2,3,6,7,8,9,12,13,10,11,14,15,0,1,4,2,3,6,7,91,第三节 矢量、栅格转换,矢栅的相互转换，一直是地理信息系统的技术难题之一。,一、矢量格式向栅格格式转换,矢量数据转换为栅格数据也,称栅格化，,其目的在于方便地进行空间分析，因为栅格数据对于多要素的重叠操作运算较矢量数据容易实现。,习惯上，在矢量数据中，点的坐标用（X，Y）来表示，而在栅格数据中，点的坐标用点所在栅格的行列号（I，J）来表示。,1、点的栅格化,将点P的矢量坐标（X,P,，Y,P,）换算成栅格的行、列号（II，JJ）,92,y,x,o,O,X,0,Y,0,P,Y,p,X,p,II=INT（Y0-YP）/d）,JJ=INT（XP-X0）/d）,II,JJ,d,II=INT（Y,0,-Y,P,）/d）,JJ=INT（X,P,-X,0,）/d）,93,2、线段的栅格化,线段栅格化步骤如下：,A、两端点栅格化,B、求出这两个端点位置的行数差和列数差：,行数差= II,2,- II,1,、 列数差= JJ,2,- JJ,1,C、计算直线与栅格中心线的交点坐标,若,行数差列数差,，则逐行求出本行中心线与已知直线的交点坐标,94,X,1,，Y,1,X,2,，Y,2,D、将求得的交点栅格化，并将其所在的栅格“赋值”。如图,II,1,=INT（Y,0,-Y,1,）/d）,JJ,1,=INT（X,1,-X,0,）/d）,II,1,JJ,1,II,2,=INT（Y,0,-Y,2,）/d）,JJ,2,=INT（X,2,-X,0,）/d）,II,2,JJ,2,Y中心线=Y,0,-II,1,*d-3/2*d,Y中心线=Y,0,-II,1,*d-5/2*d,Y中心线=Y,0,-II,1,*d-7/2*d,95,若,行数差列数差,，则逐列求出本列中心线与已知直线的交点坐标：,将求得的交点栅格化，并将其所在的栅格“赋值”。,X,1,y,1,X,2,y,2,96,这里，之所以要分两种情况处理，是为了使产生的被“赋值的栅格相互连通，避免出现间断现象,97,具体编程思路如下,开始,直线两端点栅格化,II,1,=（Y,0,-Y,1,）/d；JJ,1,=（X,0,-X,1,）/d,II,2,=（Y,0,-Y,2,）/d；JJ,2,=（X,0,-X,2,）/d,计算两端点的行数差和列数差,行数差R=II,2,-II,1,；列数差C=JJ,2,-JJ,1,Y=Y,1,+（X-X,1,）*（Y,2,-Y,1,）/（X,2,-X,1,）,建立直线方程：,RC？,Y,N,逐行处理,逐列处理,98,扫描线开始扫描，当K=1时，为第一条扫描线,其方程为：,逐列扫描,X=X,C,=X,0,+JJ,1,*d+3/2*d,kJJ,2,-JJ,1,-1？,结束,N,Y,求当前扫描线的直线方程,：X=X,C,求扫描线与直线的交点坐标：X=X,C,；,Y=Y,1,+（X,C,-X,1,）*（Y,2,-Y,1,）/（X,2,-X,1,）,对交点进行栅格化：II,=（,Y,0,-Y,）/,d,；,JJ=,（,X-X,0,）/,d,递进扫描：K=K+1；X,C,=X,C,+d,99,扫描线开始扫描，当K=1时，为第一条扫描线,其方程为：,逐行扫描,Y=Y,C,=Y,0,-II,1,*d-3/2*d,kII,2,-II,1,-1？,结束,N,Y,求当前扫描线的直线方程,：Y=Y,C,求扫描线与直线的交点坐标：Y=Y,C,；,X=X,1,+（Y,C,-Y,1,）*（X,2,-X,1,）/（Y,2,-Y,1,）,对交点进行栅格化：II,=（,Y,0,-Y,）/,d,；,JJ=,（,X-X,0,）/,d,递进扫描：K=K+1；Y,C,=Y,C,-d,100,3、面的栅格化,面域的栅格化可分以下几步进行：,第一步 将面域的边界栅格化,用前面介绍的线段栅格化的方法对组成面域的每条边进行栅格化，如图：,101,R,R,N,R,R,R,N,R,N,N,N,R,N,N,N,L,N,N,R,N,R,N,N,N,N,N,N,N,N,N,N,N,N,L,L,N,L,L,L,L,L,第二步 对各个栅格像元加标记,上升像元标上,“L”,，下降像元被标上,“R”,，平坦处或升降变换处的像元被标上,“N”,，为了反映面域的拓扑关系，可约定，面域的,外廓按顺时针,方向组织数据，,内廓按逆时针,方向组织数据。,102,第三步 配对填充,逐行扫描栅格数据，从左到右，将每行中的L和R配对，并在每对,L-R,之间填上代表该多边形面域的特定色度值。在配对时，可,不顾“N”的存在,，但在配对填充结束后，应将,剩余的N或R（L）置换成面域灰度值,。,103,L,L,L,L,L,N,L,L,N,N,N,N,N,N,N,N,R,N,R,N,N,N,N,N,N,L,N,N,N,R,N,N,N,R,N,R,R,R,N,R,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,104,下面介绍几种矢量向栅格转换的算法：,（多边形填充）,*内部点扩散算法,该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界点，则新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋予多边形的编号。重复上述过程，直到所有种子点填满多边形为止。,扩散算法程序设计比较复杂，需要在栅格阵列中进行搜索，占用内存大。,105,106,*扫描线法：,根据行（或列）中心线与面边界的交点，排序，配对，填充。,1,2,3,4,5,6,当中心扫描线与多边形相切时，要把切点分成两个点；当扫描线与某一边有部分重合时，只记录重合的起点和终点。以利于配对。图中有可能成为切点的拐点是,大家看一看它们有什么特点？,107,*边界代数算法（,Boundary Algebra Filling,BAF,)：,是一种基于积分思想的矢量格式向栅格格式转换的算法。,基本思想：,先将边界进行栅格化；,对每幅地图的全部具有左右多边形编号的边界弧段，沿其前进方向逐个搜索，,当边界,上行时，将边界线位置与左图框之间的网格加上一个值=（左多边形编号）-（右多边形编号）,；当边界,下行时，将边界线位置与左图框之间的网格加上一个值=（右多边形编号）-（左多边形编号）,；而不管边界线的排列顺序。,108,该算法简单可靠，而且仅采用加减运算，又不考虑边界的顺序，故运算速度快。*举一例说明：,下行线的左边为：右多边形号-左多边形号,上行线的左边为：左多边形号-右多边形号,2,2,2,5,5,2,2,5,5,5,5,2,5,5,5,5,2,5,5,5,5,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,0,0,0,0,3,3,3,3,0,0,0,0,3,3,3,