空间数据结构

, , , , , ,#,第二章,空间数据结构,1,第二章 空间数据结构,空间数据结构,就是指空间数据的编排方式和组织关系，是指空间数据适合于计算机存储、管理、处理的逻辑结构。换句话说，是指空间数据以什么形式在计算机中存储和处理。,空间数据编码,是空间数据结构的实现，目的是将不同的空间实体按一定的数据结构转换为适用于计算机存储和处理的过程，不同的对象，其数据结构相差很大，同一对象，也可以用许多方式来组织数据，按不同的数据结构去处理，会得到截然不同的内容。,2,一种高效的数据结构应具备几方面的要求：,1,、组织的数据能够表示要素之间的层次关系，便于不同数据联接和覆盖；,2,、正确反映地理实体的空间排列方式和各实体间相互关系；,3,、便于存取和检索；,4,、节省存储空间，减少数据冗余；,5,、存取速度快，在运算速度较慢的微机上要达到快速响应；,6,、具有足够的灵活性，数据组织应具有插入新的数据、删除或修改部分数据的基本功能。,第二章 空间数据结构,3,1,、现实世界的认知过程,一、空间认知模型,现实世界,数字世界,观察、抽象,综合取舍,定义、编码,模型化,概念世界,以实体表达,第二章 空间数据结构,4,2,、空间实体（地理实体）的概念,一、空间认知模型,指自然界现象和社会经济事件中,不能再分割的单元,，它是一个,具体的、有概括性，复杂性，相对意义的,概念。是一种在现实世界中不能再划分为同类现象的现象。,如：城市、湖泊、道路，甚至是某种现象的度量结果，如高温区，干旱区等。,（,1,）定义,第二章 空间数据结构,5,2,、空间实体（地理实体）的概念,一、空间认知模型,地理实体类别及实体内容的确定是从,具体需要,出发的，例如，在全国地图上由于比例尺很小，武汉就是一个点，这个点不能再分割，可以把武汉定为一个空间实体，而在大比例尺的武汉市地图上，武汉的许多房屋，街道都要表达出来，所以武汉必须再分割，不能作为一个空间实体，应将房屋，街道等作为研究的地理实体，由此可见，,GIS,中的空间实体是一个概括，复杂，相对的概念。,（,2,）理解,第二章 空间数据结构,6,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,属性特征（非定位数据）：,用以描述事物或现象的特性，即用来说明“是什么”，如事物或现象的类别、等级、数量、名称等。,属性数据（非几何数据）,（,1,）基本特征,第二章 空间数据结构,7,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,空间特征（定位数据）：,用以描述事物或现象的地理位置以及空间相互关系，又称为几何特征和拓扑特征，前者如界桩的经纬度，后者如中国、印度接壤。,位置数据、定位数据（几何数据），如用,X,Y,坐标来表示。 关系数据，如空间实体的邻接、关联、包含等，主要是指拓扑关系。,（,1,）基本特征,第二章 空间数据结构,8,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,时间特征（时间尺度）：,用以描述事物或现象随时间的变化，例如人口数的逐年变化。,时态数据,（,1,）基本特征,第二章 空间数据结构,9,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,2,）实体类型,5,、复杂实体,1,、点状实体,2,、线状实体,3,、面状实体,4,、体状实体,第二章 空间数据结构,10,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,2,）实体类型,4,）角点、节点,Vertex,：,表示线段和弧段上的连接点。,1,）实体点,：,用来代表一个实体。,2,）注记点,：,用于定位注记。,3,）内点：,用于负载多边形的属性，存在于多边形内。,点实体,表示有特定位置的,0,维空间实体。,第二章 空间数据结构,11,线状实体包括,：线段,，边界、链、弧段、网络等。,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,2,）实体类型,线实体,表示,1,维空间实体，具有相同属性的点的轨迹，线或折线，由一系列的有序坐标表示，并有如下,特性,：,1,）,实体长度,：,从,起点到终点的总长,2,）,弯曲度,：,用于,表示像道路拐弯时弯曲的程度。,3,）,方向性：,如：水流方向，上游,下游，,公路，单、双向之分。,第二章 空间数据结构,12,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,2,）实体类型,面实体,表示,2,维空间实体，表示平面区域大范围连续分布的特征，是对湖泊、岛屿、地块等一类现象的描述。在数据库中由一封闭曲线加内点来表示。,特征：,1,）,面积范围,2,）,周长,3,）,独立性或与其它地物相邻,如中国及其周边国家,4,）,内岛屿或锯齿状外形：,如岛屿的海岸线封闭所围成的区域。,5,）,重叠性与非重叠性：,如,学校的分区，菜市场的服务范围等都有可能出现交叉重叠现象，而一个城市的各个城区一般说来不会出现重叠。,第二章 空间数据结构,13,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,2,）实体类型,体实体,立体状实体用于描述三维空间中的现象与物体，它具有长度、宽度及高度等属性，立体状实体一般具有以下一些,空间特征,：,1,）,体积,，如工程开控和填充的土方量。,2,）每个二维平面的,面积,。,3,）,周长,。,4,）,内岛,。,5,）含有,弧立块或相邻块,。,6,）,断面图与剖面图,。,第二章 空间数据结构,14,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,2,）实体类型,维数,实体类型,代表地物,零维,点,水井、污染源等。,一维,线、弧、链,道路、公共设施网等。,二维,面、多边形,土壤、植被、岩石分类区、行政区划等。,三维,体,地形，温度,第二章 空间数据结构,15,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,2,）实体类型,实体类型组合,线,-,面：,1,、区域包含线：计算区域内线的密度，某省的水系分布情况。,2,、线通过区域：公路上否通过某县。,3,、线环绕区域：区域边界，搜索左右区域名称，中国与哪些国家接壤。,4,、线与区域分离：距离。,第二章 空间数据结构,16,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,2,）实体类型,实体类型组合,面,-,面：,1,、 包含：岛,某省的湖泊分布。,2,、 相合：重叠，学校服务范围与菜场服务范围重叠区。,3,、 相交：划分子区。,4,、 相邻：计算相邻边界性质和长度，公共连接边界。,分离：计算距离。,Fe,Cu,第二章 空间数据结构,17,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,3,）空间关系,空间关系的类型,1,）拓扑空间,关系：,2,）顺序空间关系：,（,方向空间关系,）,用,上下左右、前后、东南西北等方向性名称来描述空间实体的顺序关系，算法复杂，至今没有很好的解决方法,。,第二章 空间数据结构,18,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,3,）空间关系,空间关系的类型,3,）度量空间关系，,主要指实体间的距离关系，远近。,在,地理空间中两点间的距离有,两种度量方法,。,a,、沿真实的地球表面进行,除与两点的地理坐标有关外，还与所通过路径的地形起伏有关，复杂,引入第二种。,b,、沿地球旋转椭球体的距离量算。,距离,类别,：,欧氏距离（笛卡尔坐标系）、曼哈顿（出租车）距离、时间距离（纬度差）、大地测量距离（大地线）（沿地球大圆经过两个城市中心的距离）。,第二章 空间数据结构,19,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,3,）空间关系,拓扑关系,1,）定义：,指,图形保持连续状态下变形，,但图形关系不变的性质。,将橡皮任意拉伸，压缩，但不能扭转或折叠。,拓扑变换,（橡皮变换）,第二章 空间数据结构,20,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,3,）空间关系,拓扑关系,第二章 空间数据结构,非拓扑属性,（几何）,拓扑属性（,没发生变化的属性）,两点间距离,一点指向另一点的方向,弧段长度、区域周长、面积,等,一个点在一条弧段的端点,一条弧是一简单弧段（自身不相交）,一个点在一个区域的边界上,一个点在一个区域的内部,/,外部,一个点在一个环的内,/,外部,一个面是一个简单面,一个面的连通性,面内任两点从一点可在面的内部走向另一点,21,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,3,）空间关系,拓扑关系,2,）种类：,第二章 空间数据结构,a,）,关联性：,（,不同类,要素之间）结点与弧段：如,V9,与,L5,L6,L3,多边形与弧段：,P2,与,L3,L5,L2,b,）,邻接性：,(,同类,元素之间,),多边形之间、结点之间。,邻接矩阵,重叠：,-,邻接,：,1,不,邻接：,0,22,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,3,）空间关系,拓扑关系,2,）种类：,第二章 空间数据结构,c,）连通性：,与邻接性相类似，指对弧段连接的判别，如用于网络分析中确定路径、 街道是否相通。,连通矩阵,：,重叠：,-,连通：,1,不连通：,0,23,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,3,）空间关系,拓扑关系,2,）种类：,第二章 空间数据结构,d,）方向性：,一条弧段的起点、终点确定了弧段的方向。用于表达现实中的有向弧段，如城市道路单向，河流的流向等。,e,）包含性：,指面状实体包含了哪些线、点或面状实体。,f,）区域定义：,多边形由一组封闭的线来定义。,g,）层次关系：,相同元素之间的等级关系，武汉市有各个区组成。,主要的拓扑关系：,拓扑邻接、拓扑关联、拓扑包含,。,24,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,3,）空间关系,拓扑关系,3,）表达：,第二章 空间数据结构,拓扑关系具体可由,4,个关系表来表示：,（,1,）面,-,链关系： 面 构成面的弧段,（,2,）链,-,结点关系：链 链两端的结点,（,3,）结点,-,链关系：结点 通过该结点的链,（,4,）链,面关系：链 左面 右面,25,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,（,3,）空间关系,拓扑关系,4,）意义：,第二章 空间数据结构,对于数据处理和,GIS,空间分析具有重要的意义，因为：,1,）拓扑关系能,清楚地反映,实体之间的,逻辑结构关系,，它比几何关系具有更大的稳定性，不随地图投影而变化。,2,）,有助于空间要素的查询,，利用拓扑关系可以解决许多实际问题。,如某县的邻接县，,-,面面相邻问题。又如供水管网系统中某段水管破裂找关闭它的阀门，就需要查询该线（管道）与哪些点（阀门）关联。,3,）根据拓扑关系可,重建地理实体,。,26,3,、空间实体（地理实体）的描述,空间数据,一、空间认知模型,第二章 空间数据结构,1,、描述的内容,3,、,数据类型,4,、数据结构,几何数据（空间数据、图形数据）,关系数据,实体间的邻接、关联包含等相互关系,属性数据,各种属性特征和时间,元数据,矢量、栅格、,TIN,（专用于地表或特殊造型）,RDBMS,属性表,-,采用,MIS,较成熟,空间元数据,位置,、形状、尺寸,、关系,识别码,（名称）实体的角色、功能、行为、实体的衍生信息,时间,测量方法、编码方法、空间参考系等,空间,特征：地理位置和空间关系,属性,特征,名称、等级、类别等,时间,特征,2,、,基本特征,27,4,、空间认知三层模型,一、空间认知模型,第二章 空间数据结构,空间概念模型,空间逻辑模型,物理模型,现实世界,矢量数据模型,栅格数据模型,矢,-,栅一体化数据模型,层次模型,网络模型,关系模型,面向对象模型,物理表示组织,空间数据存取,关于实体和实体间联系的抽象概念集。,表达概念模型中数据实体（或记录）及其间的关系。,描述数据在计算机中的物理组织、存储路径和数据库结构。,28,1,、栅格数据的基本概念,二、栅格数据结构,第二章 空间数据结构,栅格结构用密集正方形（或三角形，多边形）将地理区域,划分,为网格阵列（,像元阵列,）。,位置由行，列号定义，属性为栅格单元的值。,点：由,单个栅格,表达。,线：由沿线走向有相同属性取值的,一组相邻栅格,表达。,面：由沿线走向有相同属性取值的,一片栅格,表达。,栅格数据表示的是二维表面上的地理数据的,离散化,数值。在栅格数据中，地表被分割为相互邻接、规则排列的地块，每个地块与一个象元相对应。因此，栅格数据的,比例尺,就是,栅格,(,象元,),的大小与地表相应单元的大小之比,，当象元所表示的面积较大时，对长度、面积等的量测有较大影响。每个象元的属性是地表相应区域内地理数据的近似值，因而有可能产生,属性方面的偏差,。,29,1,、栅格数据的基本概念,二、栅格数据结构,第二章 空间数据结构,将工作区域的平面表象按一定分解力作行和列的规则划分，形成许多格网，,每个网格单元称为象素(,pixel,),。根据所表示实体的表象信息差异，各象元可用不同的“灰度值”来表示 。,若每个象元规定,N,比特，则其灰度值范围可在,0到2,N,1,之间；把白灰色黑的连续变化量化成8比特（,bit），,其灰度值范围就允许在0255之间；若每个象元只规定1比特，则灰度值仅为0和1，这就是所谓二值图像。,点实体在栅格数据中表示为一个像元；线实体则表示为在一定方向上连接成串的相邻像元集合；面实体由聚集在一起的相邻像元集合表示。,栅格数据结构实际上就是象元阵列,，即象元按矩阵形式的集合(二维数组）,，,栅格中的每个象元是栅格数据中最基本的信息存储单元，其坐标位置可以用行号和列号确定。,30,1,、栅格数据的基本概念,二、栅格数据结构,第二章 空间数据结构,点实体,面实体,线实体,点实体,线实体,线实体,面实体,面实体,31,2,、栅格数据层的概念,二、栅格数据结构,第二章 空间数据结构,在栅格数据结构中，物体的,空间位置,就用其在笛卡尔平面网格中的,行号,和,列号,坐标表示，物体的,属性,用,像元的取值,表示，每个像元在一个网格中只能取值一次，同一像元要表示多重属性的事物就要用多个笛卡尔平面网格，每个笛卡尔平面网格表示一种属性或同一属性的不同特征。,要表示多种专题属性，必须分层存储属性数据,栅格数据层,32,3,、栅格数据的组织方法,二、栅格数据结构,第二章 空间数据结构,方法,c,：,以层为基础，每层内以多边形为序记录多边形的属性值和多边形内各象元的坐标,。节约用于存储属性的空间。将同一属性的制图单元的,n,个象元的属性只记录一次，便于地图分析和制图处理。,方法,a,：,以象元为记录序列，不同层上同一象元位置上的各属性值表示为一个列数组。,N,层中只记录一层的象元位置，,节约大量存储空间，栅格个数很多。,方法,b,：,每层每个象元的位置、属性一一记录，,结构最简单，但浪费存储。,假设：每层的每个像元在数据库中都是独立单元，即数据值、像元和位置之间存在一对一的关系。,33,4,、栅格数据的获取,二、栅格数据结构,第二章 空间数据结构,（,1,）获取方式,1,、,手工获取,，专题图上划分均匀网格，逐个决定其网格代码。,2,、,扫描仪扫描,专题图的图像数据,行、列、颜色（灰度）,，定义颜色与属性对应表，用相应属性代替相应颜色，得到（行、列、属性）再进行栅格编码、存贮，即得该专题图的栅格数据。,3,、,由矢量数据转换而来,。,4,、,遥感影像数据，,对地面景象的辐射和反射能量的扫描抽样，并按不同的光谱段量化后，以数字形式记录下来的象素值序列。,5,、,格网,DEM,数据,，当属性值为地面高程，则为格网,DEM,，通过,DEM,内插得到。,34,4,、栅格数据的获取,二、栅格数据结构,第二章 空间数据结构,（,2,）栅格系统的确定,坐标系统的确定,表示,具有空间分布特征的地理要素，不论采用什么编码系统，什么数据结构,(,矢、栅,),都应在统一的坐标系统下，而坐标系的确定实质是坐标系原点和坐标轴的确定。,由于,栅格编码一般用于区域性,GIS,，原点的选择常具有局部性质，但为了便于区域的拼接，栅格系统的,起始坐标应与国家基本比例尺地形图公里网的交点相一致,，并分别采用,公里网的纵横坐标轴作为栅格系统的坐标轴,。,35,4,、栅格数据的获取,二、栅格数据结构,第二章 空间数据结构,（,2,）栅格系统的确定,栅格单元的尺寸,分辩率,（,resolution）,Resolution is dependent on the grid cell size.,Changing the resolution affects classification, area, perimeter, accuracy , etc.,1,2,3,3,1,1,2,2,1,1,2,3,1,1,3,3,3,3,3,2,Real world Very Fine grid,Medium grid Coarse grid,36,4,、栅格数据的获取,二、栅格数据结构,第二章 空间数据结构,（,2,）栅格系统的确定,栅格单元的尺寸,1,）原则,：应能,有效地逼近空间对象的分布特征，又减少数据的冗余度,。,格网太大，忽略较小图斑，信息丢失。,一般讲实体特征愈复杂，栅格尺寸越小，分辨率愈高，然而栅格数据量愈大（按分辨率的平方指数增加）计算机成本就越高，处理速度越慢。,2,）方法,：用保证最小多边形的精度标准来确定尺寸经验公式：,h,为栅格单元,边长，,Ai,为区域所有多边形的面积。,37,4,、栅格数据的获取,二、栅格数据结构,第二章 空间数据结构,（,3,）栅格代码（属性值）的确定,中心归属法：,每个栅格单元的值以,网格中心点对应的面域属性值确定。,面积占优法：,每个栅格单元的值以在该网格单元中占据最大面积的属性,38,4,、栅格数据的获取,二、栅格数据结构,第二章 空间数据结构,（,3,）栅格代码（属性值）的确定,长度占优法：,每个栅格单元的值,以网格,中线的大部分长度所对应的,面域,的属性值来确定。,重要性法：,根据栅格内不同地物的,重要性程度,，选取特别重要的空间实体决定,对应的,栅格单元,值。,39,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,1,）直接栅格编码,直接栅格编码是最简单最直观而又非常重要的一种栅格结构编码方法，通常称这种编码为,图像文件,或,栅格文件,。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码。,1,1,1,1,2,2,2,1,1,1,3,1,1,1,2,2,2,2,1,1,3,3,1,1,2,2,2,2,2,2,3,3,3,1,2,2,2,4,4,4,4,3,3,3,1,2,2,2,4,4,4,4,3,3,3,1,2,2,2,2,4,4,4,4,3,3,1,1,1,1,2,2,4,4,4,3,3,1,1,1,1,2,2,2,1,1,1,3,1,1,1,2,2,2,2,1,1,3,3,1,1,2,2,2,2,2,2,3,3,3,1,2,2,2,4,4,4,4,3,3,3,1,2,2,2,4,4,4,4,3,3,3,1,2,2,2,2,4,4,4,4,3,3,1,1,1,1,2,2,4,4,4,3,3,40,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,1,）直接栅格编码,直接栅格编码,也可以,奇数行从左到右而偶数行由右向左记录,，为了特定目的还可以采用其他特殊的顺序,。,特点,：,（,1,）最直观、最基本的网格存贮结构，数据存储简单，没有进行任何压缩数据处理。,（,2,）数据存储量大，如果每个像元用一个字节表示，存储空间为：,m(,行,) n(,列,) 1(,字节,),。,41,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,1,）直接栅格编码,栅格数据量大，格网数多，由于地理数据往往有较强的相关性，即相邻象元的值往往是相同的。所以，出现了各种,栅格数据压缩方法,。,数据压缩,是将数据表示成更紧凑的格式以减少存储空间的一项技术,。分为：,无损,压缩,：在编码过程中信息没有丢失，经过解码可恢复原有的信息,-,信息保持,编码,。,有损压缩,：为最大限度压缩数据，在编码中损失一些认为不太重要的信息，解码后，这部分信息无法恢复。,-,信息不保持编码,。,无压缩编码,42,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,链式编码,行程编码,块式编码,四叉树编码,压缩编码,43,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,链式编码,弗里曼链码（,Freeman,链码）、边界链码,将栅格数据（线状地物面域边界）表示为,矢量链,的,记录。,1,）首先定义一个,3x3,窗口，中间栅格的走向有,8,种可能，并将这,8,种可能,0,7,进行编码。,2,）记下地物属性码和起点行、列后，进行追踪，得到矢量链,.,44,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,链式编码,弗里曼链码（,Freeman,链码）、边界链码,将栅格数据（线状地物面域边界）表示为,矢量链,的,记录。,a,a,a,a,a,a,b,a,链式编码表,属性码,起点行,起点列,链码,a,1,4,556656,b,3,7,576654323,45,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,链式编码,弗里曼链码（,Freeman,链码）、边界链码,将栅格数据（线状地物面域边界）表示为,矢量链,的,记录。,优点：,链码可有效地存贮压缩栅格数据，便于面积、长度、转折方向和边界、线段凹凸度的计算。,缺点：,不易做边界合并，插入操作、编辑较困难（对局部修改将改变整体结构）。区域空间分析困难，相邻区域边界被重复存储。,46,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,行程编码,有相同属性值的邻近像元被合并在一起称为一个行程，行程用一对数字表达,：,1,）属性码，长度,(A,5),(B,3),(A,2),(B,2),(A,2),(B,2),2,）属性码，点位,(A,1,1),(B,2,2),(A,3,1),(B,3,3),(A,4,1),(B,4,3),A A A A,A B B B,A A B B,A A B B,47,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,行程编码,按行（或列）记录相同代码的始末象元的列号（或行号）和相应的代码，即按（起位、止位、属性值）编码，下图可沿行方向进行行程编码,：,1,5,6,48,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,行程编码,只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重重的个数。即按（属性值和重复个数）编码。,5,3,49,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,行程编码,逐个记录各行（或列）代码发生变化的位置和相应的代码，即按（位置，属性值）编码。,50,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,行程编码,特点：,对于行程长度编码，区域越大，数据的相关性越强，则压缩越大，,适用于类型区域面积较大的专题图,，而不适合于类型连续变化或类别区域分散的分类图（压缩比与图的复杂程度成反比）。,这种编码在,栅格加密时，数据量不会明显增加,，,压缩率高，并最大限度地保留原始栅格结构，编码解码运算简单，且易于检索，叠加，合并等操作,，这种编码应用广泛。,51,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,块式编码,行程编码向二维扩展,把,多边形范围划分成由象元组成的,正方形,，然后对各个正方形进行编码。块式编码数据结构中,包括3个数字,：块的初始位置（行、列号）和块的大小（块包括的象元数），再加上记录单元的代码组成。,采用,正方形区域,作为记录单元，每个记录单元包括相邻的若干栅格。,数据,对组成,：,（初始行、列，,半径,/,大小，,属性值）,52,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,块式编码,行程编码向二维扩展,1 2 3 4 5 6 7 8,1 0 4 4 7 7 7 7 7,2 4 4 4 4 4 7 7 7,3 4 4 4 4 8 8 7 7,4 0 0 4 8 8 8 7 7,5 0 0 8 8 8 8 7 8,6 0 0 0 8 8 8 8 8,7 0 0 0 0 8 8 8 8,8 0 0 0 0 0 8 8 8,如：（,1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7,),依次扫描，编过的不重复。,特点,：,具有,可变分辨率,，即当属性变化小时图块大，对于大块图斑记录单元大，分辨率低，压缩比高。,小块图斑记录单元小，分辨率高，压缩比低，所以，与行程编码类似，随图形复杂程度的提高,而提高分辨率,。,53,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,一种,可变分辨率,的,非均匀网格,系统。,是最有效的栅格数据压缩,编码方法之一,。,1,）基本,思想,：,将,2,n,2,n,象元组成的图像,(,不足的用背景补上,),按四个象限进行递归分割,，并,判断属性是否单一,，单一,：不分,。,不单一：递归分割,。,A,A,A,B,A,B,B,B,A,A,B,B,A,A,B,B,0,1,2,3,54,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,2,）四,叉树的树形,表示：,用一棵倒立树表示这种分割和分割结果。,树根结点：,代表整个区域；,叶,结点（叶）：,树的每个结点有四棵子树，为空的结点为叶结点，对应于区域分割时数值单调的子象限,，即不能再分割的块，图,斑大小取决于它在树中的层数；,结点（树叉）：,对应于区域分割时数值不单调的子象限,。,每个树叉均有,4,个分叉，叫四叉树。,55,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,1,6,2,3,4,5,11,12,13,7,8,9,10,1,6,2,3,4,5,11,13,12,7,8,10,9,7,第,3,层,第,2,层,第,1,层,第,0,层,根结点,叶结点,结点,（,a,）顺序分解表示,（,b,）树形结构表示,56,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,3,）建立,四叉树结构的方式,自上而下,方式,(top-down),从顶层开始，即先检测全区域，其值不单一时再四划分，直到数值或内容单一为止。,自下而上,方式,(bottom-up,),从底层开始，即以像元大小为结点，每记录四个结点时，即生成父结点,。,57,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,4,）四,叉树结构类型,根据四叉树存储结构的不同，可以将四叉树结构类型分为,:,指针,四叉树,线性,四叉树,58,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法：,a,、常规四叉树（指针四叉树）,记录,这棵树的叶结点外，中间结点，结点之间的联系用指针联系，,每个结点需要,6,个变量,：,父结点指针、四个子结点的指针和本结点的属性值,。,59,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法,a,、常规四叉树（指针四叉树）,SW,2,SE,3,NE,1,NW,0,根结点,结点,叶结点,0,1,2,3,10,11,12,13,120,121,122,123,指针四叉树的分解过程及编码,88,0,2,3,1,121,10,11,12,13,60,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法：,a,、常规四叉树（指针四叉树）,特点,：,指针不仅,增加了数据的存储量,，还增加了操作的,复杂性,：如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。所以，,常规四叉树并不广泛用于存储数据,，其价值在于建立索引文件，进行数据检索。,61,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法：,b,、线性四叉树,线性,四叉,树编码为美国马里兰大学地理信息系统中采用的编码方式，具有,四叉树的形式，用指针四叉树方式组织数据，但不用指针四叉树方式存储数据,。,基本思想：,它,不记录中间节点和使用指针，仅,记录叶节点,，并用,地址码,表示叶节点的位置,。因此，其编码包括叶节点的地址码和本节点的属性或灰度值，并且地址码隐含了叶节点的位置和深度信息。,62,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法：,b,、线性四叉树,最,常见的地址码是,四进制,或,十进制的,Morton,码,。,基于深度和层次的线性四叉树编码：,记录每个叶节点的地址和属性值。其中地址包括两部分，以,32,位二进制数表示：,0 0 0 00 0 0 1 0 0 1 0 0 0 1 1,深度（,4,位）,路径（,28,位）,从叶节点到根节点的路径,0,2,3,1,路径：,011SE,000SW,102NW,深度：,00113,第三层,63,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法：,b,、线性四叉树,四进制地址码,(M,Q,码,),M,Q,码是一串数字组成，每分割一次增加一位数，其中每位数字都是不大于,3,的四进制数,。,A,、分割一次，增加一位数字，大分割在前，小分割在后。所以，,码的位数表示分割的次数,。,B,、,每一个位均是不大于,3,的四进制数，表达位置。,0,1,2,3,A,A,A,A,A,B,B,B,A,A,B,B,A,A,A,B,B,03,B,A,64,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法：,b,、线性四叉树,四进制地址码,(M,Q,码,),320,？,1,3,2,0,自上而下,65,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法：,b,、线性四叉树,四进制地址码,(M,Q,码,),M,Q,码计算公式：,M,Q,= 2,I,b,+,J,b,公式,中,I,b,、,J,b,分别为栅格单元行列号的,二进制数，,I,b,、,J,b,位数看即编码的位数，要看分割的次数，不足的前面补,0.,66,(a),区域栅格表示,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法：,b,、线性四叉树,四进制地址码,(M,Q,码,),M,Q,编码,过程：,图,(a),所示为,88,列图，即栅格单元,2,3,2,3,，其位置码的最长位数是,3,位（即分割三次）。,现对图,(a),按,M,Q,码的计算公式进行编码，得到图,(b),所示编码表，最后进行排序归并得到图,(c) M,Q,码。,(b),编码表,(c)M,Q,码,自下而上,67,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法：,b,、线性四叉树,十进制,地址码,(,M,D,码,),四,进制,Morton,码直观上切合四叉树分割，但许多语言不支持四进制变量，需用十进制表示,Morton,码。线性四叉树的,十进制编码简称,M,D,编码,，它同线性四叉树的四进制编码主要不同在于,编码值是十进制自然数,，其合并过程可直接按自然数顺序进行,。,68,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,5,）编码方法：,b,、线性四叉树,十进制,地址码,(,M,D,码,),A 0,A 1,A 4,A 5,A 2,B 3,B 6,B 7,A 8,A 9,B 12,B 13,A 10,A 11,B 14,B 15,如行为,2,、列为,3,的栅格的,M,D,步骤：,(1),行、列号为二进制,I,b,= 1 0 J,b,= 1 1,(2)I,行,J,列交叉,1 1 0 1 = 13,(3),再化为十进制,.,实质上是按左上、右上、左下、右下的顺序，从零开始对每个栅格进行自然编码。,69,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,(a),区域栅格表示,70,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,M,Q,编码例证,1,：,第一行、第五列的栅格单元，求它的,M,Q,码,首先将十进制第一行、第五列转成二进制形式，得到,行,I,b,=(001),列,J,b,=(101),其地址码为,: M,Q,= 2,I,b,+,J,b,= 21+101 = 103,？,提示：,M,Q,= 2,I,b,+,J,b,71,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,M,Q,编码例证,2,：求,四叉树中四进制位置码的解码，即已知,M,Q,码为,103,，求其,行列号,。算法如下：,？,若,该位编码值为,0,，,1,，对行号贡献值为,0,若该位编码值为,2,，,3,，对行号贡献值为,1,若该位编码值为,0,，,2,，对列号贡献值为,0,若该位编码值为,1,，,3,，对列号贡献值为,l,M,Q,1 0 3,表示,M,Q,码为,103,的单元,二进制行值,0 0 1,表示第一行,二进制列值,1 0 1,表示第五,列,72,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,M,Q,1,0 3,表示,M,Q,码为,103,的单元,二进制行值,0 0 1,表示第一行,二进制列值,1 0 1,表示第五列,这表示,M,Q,码为,103,的单元处于第一行、第五列。最后，线性四叉树的每个叶接点可用三元组的线性表来表示。,三元组结构为,(M,，,D,，,V),其中,M,为叶结点的地址码；,D,为叶结点的深度；,V,为叶结点的格网属性,.,73,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,M,D,编码例证：,把一幅,2,n,2,n,的图像压缩成线性四叉树的过程,1,按,Morton,码把图象读入一维数组。,2,相邻的四个象元比较，一致的合并，只记录第一个象元,的,Morton,码。循环比较所形成的大块，相同的再合并，直到不能合并为止。,3,进一步用游程长度编码压缩。压缩时只记录第一个象元的,Morton,码。,74,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,M,D,编码例证：,把一幅,2,n,2,n,的图像压缩成线性四叉树的过程,A 0,A 1,A 4,A 5,A 2,B 3,B 6,B 7,A 8,A 9,B 12,B 13,A 10,A 11,B 14,B 15,处理过程为：,1,按,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,2,四相邻象元合并，只记录第一个象元的,Morton,码。,0 1 2 3 4 5 6 7 8 12,A A A B A A B B A B,3,由于不能进一步合并，可用行程长度编码压缩。,0 3 4 6 8 12,A B A B A B,75,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,优缺点,（,1,）,易于计算,多边形的数量特征；,（,2,）四叉树表示法基本上是一种,非冗余表示法，,可用较少的存储量精确的表示复杂的图形；,（,3,）四叉树具有,可变率或多重分辩率,的特点使得它有很好的应用前景，适用于处理凝聚性或呈块状分布的空间数据，特别,适用于处理分布不均匀的块状空间数据,，但,不适用于连续表面（如地形）或线状地物,。,（,3,）栅格到四叉树,及四,叉树到简单栅格结构的,转换,比其他压缩方法,容易,。,（,4,）便于在多边形中,嵌套多边形,，如表示“岛”,。,优点,76,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,优缺点,（,1,）矢,/,栅正反变换还不理想。,（,2,）建立四叉树耗费机时很多。,（,3,）四叉树虽可修改，但很费事,（具体的数据结构中会提到）。,（,4,）未能表示物体间的,拓扑关系,。,（,5,）数据,结构复杂,，当同时提供多种四叉树结构时，不利于分析。,缺点,77,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,优缺点,（,6,）与非树表示法比较，四叉树表示法的缺点在于转换的不稳定性或叫,滑动变异。,例如，两个图像的差异仅由于平移，就会构成极为不同的四叉树，因而很难根据四叉树来判断这两个图像是否全同，故不利于做形状分析和模式识别。,缺点,78,5,、栅格数据编码方法,二、栅格数据结构,第二章 空间数据结构,（,2,）压缩编码,四叉树编码,优缺点,（,7,）一个物体的图像在构成四叉树时会被分割到若干个象限中，使它,失去了内在的相关性,。,缺点,A 0,A 1,A 4,A 5,A 2,B 3,B 6,B 7,A 8,A 9,B 12,B 13,A 10,A 11,B 14,B 15,79,6,、栅格数据的优缺点,二、栅格数据结构,第二章 空间数据结构,栅格数据的优点,地理要素表达比较直观，直接记录空间实体的属性值，数据存储结构简单，并容易实现叠加分析、数据统计等操作,栅格数据的缺点,数据冗余度大，造成存储空间的浪费,像元大小的变化，对长度、面积等的度量有较大影响,不宜进行某些空间查询和网络分析,？,80,三、矢量数据结构,第二章 空间数据结构,矢量是具有一定大小和方向的量。,线段长度表示大小，线段端点的顺序表示方向。,有向线段用一系列有序特征点表示，矢量数据就是代表地图图形的各离散点平面坐标（,x,y,）的有序集合。,矢量数据结构主要用于表示地图图形元素几何数据之间及其与属性数据之间的相互关系。,矢量数据结构是通过坐标值来精确地表示点、线、面等地理实体的。,81,三、矢量数据结构,第二章 空间数据结构,1,、图形表示,82,2,、矢量数据的获取方式,三、矢量数据结构,第二章 空间数据结构,1),由外业测量获得,可,利用测量仪器自动记录测量成果,(,常称为电子手薄,),，然后转到地理数据库中。,2,),由,栅格数据转换获得,利用,栅格数据矢量化技术，把栅格数据转换为矢量数据。,3,),跟踪数字化,用,跟踪数字化的方法，把地图变成离散的矢量数据,。,83,3,、矢量数据组织,三、矢量数据结构,第二章 空间数据结构,矢量数据表示时,应考虑以下问题,：,矢量数据自身的存贮和处理。,与属性数据的联系。,矢量数据之间的空间关系,(,拓扑关系,),。,点：坐标对（,x,y,）,+,识别符,线：坐标对系列,(x1,y1).(xn,yn),及,有关属性、其它属性,面：首尾相同的坐标串,关系表,几何位置坐标文件,连接,84,第二章 空间数据结构,标识码,属性码,空间对象编码,唯一,连接空间和属性数据,数据库,独立编码,点:,(,x ,y,),线: (,x,1, y,1,) , (,x,2, y,2,) , (,x,n, y,n,),面: (,x,1, y,1,) , (,x,2, y,2,) , (,x,1, y,1,),点位字典,点: 点号,文件,线: 点号串,面: 点号串,点号,X,Y,1,11,22,2,33,44,n,55,66,存储方法,85,4,、矢量数据编码方式,三、矢量数据结构,第二章 空间数据结构,（,1,）实体式,（,spaghetti,）,-,面条,模型,:,以实体为单位记录其,坐标。,点实体,线实体,面实体,86,方向,字体,排列,指针,与线相交的角度,如果是简单点,符号,符号,字符大小,简单点,文字说明,结点,唯一识别符,比例尺,方向,x,，,y,坐标,其它有关的属性,点实体,类型,序列号,有关的属性,如果是文字说明,如果是结点,点实体,87,线实体,唯一标识码,线标识码,起始点,终止点,坐标对序列,显示信息,非几何属性,线实体,与线表非常相似，但它的最后一个结点坐标值与第一个结点坐标值相同。,对于多边形中的“岛”，处理方法是在每个多边形头记录中增加一条“岛”的属性来表示优先级，低优先级的多边形先绘置先充填，高优先级的多边形后绘置，这样岛多边形就覆盖了原先的多边形。,面实体,88,4,、矢量数据编码方式,三、矢量数据结构,第二章 空间数据结构,（,1,）实体式,优点,结构,简单、直观、易实现以实体为单位的运算和显示,。,缺点,1,、,相邻多边形的公共边界被数字化并存储两次，造成数据冗余和碎屑多边形,数据不一致，浪费空间，导致双重边界不能精确匹配。,2,、,自成体系，,缺少多边形的邻接信息，无拓扑关系,，难以进行邻域处理，如消除多边形公共边界，合并多边形。,3,、,岛作为一个单个图形，没有与外界多边形联系。不易检查拓扑错误。,所以，这种结构只用于简单的制图系统中，显示图形。,89,4,、矢量数据编码方式,三、矢量数据结构,第二章 空间数据结构,（,2,）索引式,对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,P,P,P,Map,1,）点文件：,点号,坐标,1,x1,y1,索引文件：,面号,弧段号,P1,A,B,C,3,）面文件：,2,）弧段文件,:,弧段号,起点,终点,点号,A,5,2,7,8,9,10,90,4,、矢量数据编码方式,三、矢量数据结构,第二章 空间数据结构,（,2,）索引式,与实体式相比,：,优点：,用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。,缺点：,表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。,91,4,、矢量数据编码方式,三、矢量数据结构,第二章 空间数据结构,（,3,）双重独立式编码,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,P,P,P,Map,简称,DIME(Dual Independent Map Encoding),，是美国人口统计系统采用的一种编码方式，是一种,拓扑,编码结构。,1,）点文件：,点号,坐标,1,x1,y1,2,）线文件,:,线文件是以,线段,为记录单位,线号,左多边形,右多边形,起点,终点,L210,P1,P2,2,10,关联,邻接,关联,连通,拓扑关系明确,92,4,、矢量数据编码方式,三、矢量数据结构,第二章 空间数据结构,（,3,）双重独立式编码,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,P,P,P,Map,简称,DIME(Dual Independent Map Encoding),，是美国人口统计系统采用的一种编码方式，是一种,拓扑,编码结构。,3,）面,文件,面号,线号,P1,L210,L109,在,DIME,中做如下改进：,将以,线段,为记录单位改为以,弧段,为单位,链状双重独立式编码,93,4,、矢量数据编码方式,三、矢量数据结构,第二章 空间数据结构,（,4,）链式双重独立式编码,拓扑数据结构,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,P,P,P,Map,1,）弧,段坐标文件,：,弧段号,坐标系列（串,),A,x2,y2,X10,y10,2,）弧,段文件：链,面，链,结点关系,弧段号,左多边形,右多边形,起点,终点,A,P1,P2,2,5,3,）面,文件,面号,弧段号,P1,A,B,-C,94,4,、矢量数据编码方式,三、矢量数据结构,第二章 空间数据结构,（,4,）链式双重独立式编码,拓扑数据结构,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,P,P,P,Map,4,）点,拓扑文件,： 结点,链关系,点号,弧段号,2,A,B,D,在拓扑结构中，多边形（面）的边界被分割成一系列的线（弧、链、边）和点（结点）等拓扑要素，点、线、面之间的拓扑关系在属性表中定义，多边形边界不重复。,95,4,、矢量数据编码方式,三、矢量数据结构,第二章 空间数据结构,（,4,）链式双重独立式编码,拓扑数据结构,特点：,拓扑,关系明确，也能表达岛信息，而且,以弧段为记录单位,，满足实际应用需要。因为一般数字化一条街道时，必然有许多中间点，但我们在做空间分析是却没有必要以这些中间点所组成的折线为研究对象，而应以整条弧段（某条街道）为研究对象,.,被,一些成熟的商品化软件采用，如,ARC/INFO,软件,。,例：,ARC,文件,：二进制文件,:,弧段号 点数 坐标,串,在,GIS,数据输入中，,建拓扑,是指给图形数据（点、线、面）增加拓扑结构,，,INFO,：属性表,如,AAT,（,Arc Attribute Table,）,用户标识码，表明地物类型,当,图形数据修改,、删除、增加点、线、面要素后，其拓扑关系也发生改