空间数据结构

1、第二章 空间数据结构1第二章 空间数据结构 空间数据结构就是指空间数据的编排方式和组织关系，是指空间数据适合于计算机存储、管理、处理的逻辑结构。换句话说，是指空间数据以什么形式在计算机中存储和处理。 空间数据编码是空间数据结构的实现，目的是将不同的空间实体按一定的数据结构转换为适用于计算机存储和处理的过程，不同的对象，其数据结构相差很大，同一对象，也可以用许多方式来组织数据，按不同的数据结构去处理，会得到截然不同的内容。2一种高效的数据结构应具备几方面的要求：1、组织的数据能够表示要素之间的层次关系，便于不同数据联接和覆盖；2、正确反映地理实体的空间排列方式和各实体间相互关系；3、便于存取和检

2、索；4、节省存储空间，减少数据冗余；5、存取速度快，在运算速度较慢的微机上要达到快速响应；6、具有足够的灵活性，数据组织应具有插入新的数据、删除或修改部分数据的基本功能。第二章 空间数据结构31、现实世界的认知过程一、空间认知模型现实世界数字世界观察、抽象综合取舍定义、编码模型化概念世界以实体表达第二章 空间数据结构42、空间实体（地理实体）的概念一、空间认知模型 指自然界现象和社会经济事件中不能再分割的单元，它是一个具体的、有概括性，复杂性，相对意义的概念。是一种在现实世界中不能再划分为同类现象的现象。 如：城市、湖泊、道路，甚至是某种现象的度量结果，如高温区，干旱区等。（1）定义第二章 空

3、间数据结构52、空间实体（地理实体）的概念一、空间认知模型 地理实体类别及实体内容的确定是从具体需要出发的，例如，在全国地图上由于比例尺很小，武汉就是一个点，这个点不能再分割，可以把武汉定为一个空间实体，而在大比例尺的武汉市地图上，武汉的许多房屋，街道都要表达出来，所以武汉必须再分割，不能作为一个空间实体，应将房屋，街道等作为研究的地理实体，由此可见，GIS中的空间实体是一个概括，复杂，相对的概念。（2）理解第二章 空间数据结构63、空间实体（地理实体）的描述空间数据一、空间认知模型 属性特征（非定位数据）：用以描述事物或现象的特性，即用来说明“是什么”，如事物或现象的类别、等级、数量、名称等

4、。属性数据（非几何数据）（1）基本特征第二章 空间数据结构73、空间实体（地理实体）的描述空间数据一、空间认知模型 空间特征（定位数据）：用以描述事物或现象的地理位置以及空间相互关系，又称为几何特征和拓扑特征，前者如界桩的经纬度，后者如中国、印度接壤。位置数据、定位数据（几何数据），如用X,Y坐标来表示。 关系数据，如空间实体的邻接、关联、包含等，主要是指拓扑关系。（1）基本特征第二章 空间数据结构83、空间实体（地理实体）的描述空间数据一、空间认知模型 时间特征（时间尺度）：用以描述事物或现象随时间的变化，例如人口数的逐年变化。时态数据（1）基本特征第二章 空间数据结构93、空间实体（地理实

5、体）的描述空间数据一、空间认知模型（2）实体类型5、复杂实体1、点状实体2、线状实体3、面状实体4、体状实体第二章 空间数据结构103、空间实体（地理实体）的描述空间数据一、空间认知模型（2）实体类型4）角点、节点Vertex：表示线段和弧段上的连接点。 1）实体点：用来代表一个实体。2）注记点：用于定位注记。3）内点：用于负载多边形的属性，存在于多边形内。点实体 表示有特定位置的0维空间实体。第二章 空间数据结构11线状实体包括：线段，边界、链、弧段、网络等。3、空间实体（地理实体）的描述空间数据一、空间认知模型（2）实体类型线实体 表示1维空间实体，具有相同属性的点的轨迹，线或折线，由一系

6、列的有序坐标表示，并有如下特性：1）实体长度：从起点到终点的总长2）弯曲度：用于表示像道路拐弯时弯曲的程度。3）方向性：如：水流方向，上游下游， 公路，单、双向之分。第二章 空间数据结构123、空间实体（地理实体）的描述空间数据一、空间认知模型（2）实体类型面实体 表示2维空间实体，表示平面区域大范围连续分布的特征，是对湖泊、岛屿、地块等一类现象的描述。在数据库中由一封闭曲线加内点来表示。特征：1）面积范围 2）周长3）独立性或与其它地物相邻如中国及其周边国家4）内岛屿或锯齿状外形：如岛屿的海岸线封闭所围成的区域。5）重叠性与非重叠性：如学校的分区，菜市场的服务范围等都有可能出现交叉重叠现象，

7、而一个城市的各个城区一般说来不会出现重叠。 第二章 空间数据结构133、空间实体（地理实体）的描述空间数据一、空间认知模型（2）实体类型体实体 立体状实体用于描述三维空间中的现象与物体，它具有长度、宽度及高度等属性，立体状实体一般具有以下一些空间特征：1）体积，如工程开控和填充的土方量。2）每个二维平面的面积。3）周长。4）内岛。5）含有弧立块或相邻块。6）断面图与剖面图。第二章 空间数据结构143、空间实体（地理实体）的描述空间数据一、空间认知模型（2）实体类型维数实体类型代表地物零维点水井、污染源等。一维线、弧、链道路、公共设施网等。二维面、多边形土壤、植被、岩石分类区、行政区划等。三维体

8、地形，温度第二章 空间数据结构153、空间实体（地理实体）的描述空间数据一、空间认知模型（2）实体类型实体类型组合 线-面：1、区域包含线：计算区域内线的密度，某省的水系分布情况。2、线通过区域：公路上否通过某县。3、线环绕区域：区域边界，搜索左右区域名称，中国与哪些国家接壤。4、线与区域分离：距离。 第二章 空间数据结构163、空间实体（地理实体）的描述空间数据一、空间认知模型（2）实体类型实体类型组合 面-面：1、 包含：岛,某省的湖泊分布。2、 相合：重叠，学校服务范围与菜场服务范围重叠区。3、 相交：划分子区。4、 相邻：计算相邻边界性质和长度，公共连接边界。分离：计算距离。 FeCu

9、第二章 空间数据结构173、空间实体（地理实体）的描述空间数据一、空间认知模型（3）空间关系 空间关系的类型1）拓扑空间关系： 2）顺序空间关系： （方向空间关系） 用上下左右、前后、东南西北等方向性名称来描述空间实体的顺序关系，算法复杂，至今没有很好的解决方法。第二章 空间数据结构183、空间实体（地理实体）的描述空间数据一、空间认知模型（3）空间关系 空间关系的类型3）度量空间关系，主要指实体间的距离关系，远近。 在地理空间中两点间的距离有两种度量方法。a、沿真实的地球表面进行,除与两点的地理坐标有关外，还与所通过路径的地形起伏有关，复杂,引入第二种。b、沿地球旋转椭球体的距离量算。 距离

10、类别：欧氏距离（笛卡尔坐标系）、曼哈顿（出租车）距离、时间距离（纬度差）、大地测量距离（大地线）（沿地球大圆经过两个城市中心的距离）。 第二章 空间数据结构193、空间实体（地理实体）的描述空间数据一、空间认知模型（3）空间关系 拓扑关系1）定义：指图形保持连续状态下变形，但图形关系不变的性质。将橡皮任意拉伸，压缩，但不能扭转或折叠。 拓扑变换（橡皮变换）第二章 空间数据结构203、空间实体（地理实体）的描述空间数据一、空间认知模型（3）空间关系 拓扑关系第二章 空间数据结构非拓扑属性（几何）拓扑属性（没发生变化的属性）两点间距离一点指向另一点的方向弧段长度、区域周长、面积 等一个点在一条弧段

11、的端点一条弧是一简单弧段（自身不相交）一个点在一个区域的边界上一个点在一个区域的内部/外部一个点在一个环的内/外部一个面是一个简单面一个面的连通性 面内任两点从一点可在面的内部走向另一点213、空间实体（地理实体）的描述空间数据一、空间认知模型（3）空间关系 拓扑关系2）种类：第二章 空间数据结构a）关联性： （不同类要素之间）结点与弧段：如V9与L5,L6,L3多边形与弧段：P2与L3,L5,L2b）邻接性： (同类元素之间)多边形之间、结点之间。邻接矩阵 重叠：- 邻接：1 不邻接：0223、空间实体（地理实体）的描述空间数据一、空间认知模型（3）空间关系 拓扑关系2）种类：第二章 空间数

12、据结构c）连通性：与邻接性相类似，指对弧段连接的判别，如用于网络分析中确定路径、 街道是否相通。连通矩阵：重叠：- 连通：1不连通：0 233、空间实体（地理实体）的描述空间数据一、空间认知模型（3）空间关系 拓扑关系2）种类：第二章 空间数据结构d）方向性：一条弧段的起点、终点确定了弧段的方向。用于表达现实中的有向弧段，如城市道路单向，河流的流向等。e）包含性：指面状实体包含了哪些线、点或面状实体。f）区域定义：多边形由一组封闭的线来定义。g）层次关系：相同元素之间的等级关系，武汉市有各个区组成。主要的拓扑关系：拓扑邻接、拓扑关联、拓扑包含。243、空间实体（地理实体）的描述空间数据一、空间

13、认知模型（3）空间关系 拓扑关系3）表达：第二章 空间数据结构拓扑关系具体可由4个关系表来表示：（1）面-链关系： 面 构成面的弧段（2）链-结点关系：链 链两端的结点（3）结点-链关系：结点 通过该结点的链（4）链面关系：链 左面 右面253、空间实体（地理实体）的描述空间数据一、空间认知模型（3）空间关系 拓扑关系4）意义：第二章 空间数据结构对于数据处理和GIS空间分析具有重要的意义，因为：1）拓扑关系能清楚地反映实体之间的逻辑结构关系，它比几何关系具有更大的稳定性，不随地图投影而变化。2）有助于空间要素的查询，利用拓扑关系可以解决许多实际问题。如某县的邻接县，-面面相邻问题。又如供水管

14、网系统中某段水管破裂找关闭它的阀门，就需要查询该线（管道）与哪些点（阀门）关联。3）根据拓扑关系可重建地理实体。263、空间实体（地理实体）的描述空间数据一、空间认知模型第二章 空间数据结构1、描述的内容 3、数据类型 4、数据结构几何数据（空间数据、图形数据） 关系数据实体间的邻接、关联包含等相互关系 属性数据各种属性特征和时间元数据 矢量、栅格、TIN（专用于地表或特殊造型） RDBMS属性表-采用MIS较成熟 空间元数据位置、形状、尺寸 、关系识别码（名称）实体的角色、功能、行为、实体的衍生信息时间测量方法、编码方法、空间参考系等 空间特征：地理位置和空间关系属性特征名称、等级、类别等时

15、间特征2、基本特征 274、空间认知三层模型一、空间认知模型第二章 空间数据结构空间概念模型空间逻辑模型物理模型现实世界矢量数据模型栅格数据模型矢-栅一体化数据模型层次模型网络模型关系模型面向对象模型物理表示组织空间数据存取关于实体和实体间联系的抽象概念集。表达概念模型中数据实体（或记录）及其间的关系。描述数据在计算机中的物理组织、存储路径和数据库结构。281、栅格数据的基本概念二、栅格数据结构第二章 空间数据结构栅格结构用密集正方形（或三角形，多边形）将地理区域划分为网格阵列（像元阵列）。位置由行，列号定义，属性为栅格单元的值。点：由单个栅格表达。线：由沿线走向有相同属性取值的一组相邻栅格表

16、达。面：由沿线走向有相同属性取值的一片栅格表达。 栅格数据表示的是二维表面上的地理数据的离散化数值。在栅格数据中，地表被分割为相互邻接、规则排列的地块，每个地块与一个象元相对应。因此，栅格数据的比例尺就是栅格(象元)的大小与地表相应单元的大小之比，当象元所表示的面积较大时，对长度、面积等的量测有较大影响。每个象元的属性是地表相应区域内地理数据的近似值，因而有可能产生属性方面的偏差。291、栅格数据的基本概念二、栅格数据结构第二章 空间数据结构将工作区域的平面表象按一定分解力作行和列的规则划分，形成许多格网，每个网格单元称为象素(pixel)。根据所表示实体的表象信息差异，各象元可用不同的“灰度

17、值”来表示 。若每个象元规定N比特，则其灰度值范围可在0到2N1之间；把白灰色黑的连续变化量化成8比特（bit），其灰度值范围就允许在0255之间；若每个象元只规定1比特，则灰度值仅为0和1，这就是所谓二值图像。点实体在栅格数据中表示为一个像元；线实体则表示为在一定方向上连接成串的相邻像元集合；面实体由聚集在一起的相邻像元集合表示。栅格数据结构实际上就是象元阵列，即象元按矩阵形式的集合(二维数组），栅格中的每个象元是栅格数据中最基本的信息存储单元，其坐标位置可以用行号和列号确定。301、栅格数据的基本概念二、栅格数据结构第二章 空间数据结构点实体面实体线实体点实体线实体线实体面实体面实体312

18、、栅格数据层的概念二、栅格数据结构第二章 空间数据结构在栅格数据结构中，物体的空间位置就用其在笛卡尔平面网格中的行号和列号坐标表示，物体的属性用像元的取值表示，每个像元在一个网格中只能取值一次，同一像元要表示多重属性的事物就要用多个笛卡尔平面网格，每个笛卡尔平面网格表示一种属性或同一属性的不同特征。要表示多种专题属性，必须分层存储属性数据栅格数据层323、栅格数据的组织方法二、栅格数据结构第二章 空间数据结构方法c：以层为基础，每层内以多边形为序记录多边形的属性值和多边形内各象元的坐标。节约用于存储属性的空间。将同一属性的制图单元的n个象元的属性只记录一次，便于地图分析和制图处理。 方法a：以

19、象元为记录序列，不同层上同一象元位置上的各属性值表示为一个列数组。N层中只记录一层的象元位置，节约大量存储空间，栅格个数很多。方法b：每层每个象元的位置、属性一一记录，结构最简单，但浪费存储。假设：每层的每个像元在数据库中都是独立单元，即数据值、像元和位置之间存在一对一的关系。334、栅格数据的获取二、栅格数据结构第二章 空间数据结构（1）获取方式1、手工获取，专题图上划分均匀网格，逐个决定其网格代码。2、扫描仪扫描专题图的图像数据行、列、颜色（灰度），定义颜色与属性对应表，用相应属性代替相应颜色，得到（行、列、属性）再进行栅格编码、存贮，即得该专题图的栅格数据。3、由矢量数据转换而来。4、遥

20、感影像数据，对地面景象的辐射和反射能量的扫描抽样，并按不同的光谱段量化后，以数字形式记录下来的象素值序列。5、格网DEM数据，当属性值为地面高程，则为格网DEM，通过DEM内插得到。344、栅格数据的获取二、栅格数据结构第二章 空间数据结构（2）栅格系统的确定 坐标系统的确定 表示具有空间分布特征的地理要素，不论采用什么编码系统，什么数据结构(矢、栅)都应在统一的坐标系统下，而坐标系的确定实质是坐标系原点和坐标轴的确定。 由于栅格编码一般用于区域性GIS，原点的选择常具有局部性质，但为了便于区域的拼接，栅格系统的起始坐标应与国家基本比例尺地形图公里网的交点相一致，并分别采用公里网的纵横坐标轴作

21、为栅格系统的坐标轴。354、栅格数据的获取二、栅格数据结构第二章 空间数据结构（2）栅格系统的确定 栅格单元的尺寸分辩率（resolution）Resolution is dependent on the grid cell size. Changing the resolution affects classification, area, perimeter, accuracy , etc. 12331122112311333332Real world Very Fine gridMedium grid Coarse grid364、栅格数据的获取二、栅格数据结构第二章 空间数据结构（2）

22、栅格系统的确定 栅格单元的尺寸1）原则：应能有效地逼近空间对象的分布特征，又减少数据的冗余度。格网太大，忽略较小图斑，信息丢失。一般讲实体特征愈复杂，栅格尺寸越小，分辨率愈高，然而栅格数据量愈大（按分辨率的平方指数增加）计算机成本就越高，处理速度越慢。2）方法：用保证最小多边形的精度标准来确定尺寸经验公式： h为栅格单元边长，Ai为区域所有多边形的面积。374、栅格数据的获取二、栅格数据结构第二章 空间数据结构（3）栅格代码（属性值）的确定中心归属法：每个栅格单元的值以网格中心点对应的面域属性值确定。面积占优法：每个栅格单元的值以在该网格单元中占据最大面积的属性384、栅格数据的获取二、栅格数

23、据结构第二章 空间数据结构（3）栅格代码（属性值）的确定长度占优法：每个栅格单元的值以网格中线的大部分长度所对应的面域的属性值来确定。重要性法：根据栅格内不同地物的重要性程度，选取特别重要的空间实体决定对应的栅格单元值。395、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（1）直接栅格编码直接栅格编码是最简单最直观而又非常重要的一种栅格结构编码方法，通常称这种编码为图像文件或栅格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码。11112221113111222211331122222233312224444333122244443331222244443311

24、11224443311112221113111222211331122222233312224444333122244443331222244443311112244433405、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（1）直接栅格编码 直接栅格编码也可以奇数行从左到右而偶数行由右向左记录，为了特定目的还可以采用其他特殊的顺序。 特点：（1）最直观、最基本的网格存贮结构，数据存储简单，没有进行任何压缩数据处理。（2）数据存储量大，如果每个像元用一个字节表示，存储空间为：m(行) n(列) 1(字节)。 415、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（1）直接栅格编码

25、栅格数据量大，格网数多，由于地理数据往往有较强的相关性，即相邻象元的值往往是相同的。所以，出现了各种栅格数据压缩方法。数据压缩是将数据表示成更紧凑的格式以减少存储空间的一项技术。分为： 无损压缩：在编码过程中信息没有丢失，经过解码可恢复原有的信息-信息保持编码。 有损压缩：为最大限度压缩数据，在编码中损失一些认为不太重要的信息，解码后，这部分信息无法恢复。-信息不保持编码。 无压缩编码425、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码链式编码行程编码块式编码四叉树编码压缩编码435、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 链式编码弗里曼链码（

26、Freeman链码）、边界链码将栅格数据（线状地物面域边界）表示为矢量链的记录。1）首先定义一个3x3窗口，中间栅格的走向有8种可能，并将这8种可能0 7进行编码。2）记下地物属性码和起点行、列后，进行追踪，得到矢量链.445、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 链式编码弗里曼链码（Freeman链码）、边界链码将栅格数据（线状地物面域边界）表示为矢量链的记录。aaaaaaba链式编码表属性码起点行起点列链码a14556656b37576654323455、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 链式编码弗里曼链码（Freeman链码

27、）、边界链码将栅格数据（线状地物面域边界）表示为矢量链的记录。 优点：链码可有效地存贮压缩栅格数据，便于面积、长度、转折方向和边界、线段凹凸度的计算。 缺点：不易做边界合并，插入操作、编辑较困难（对局部修改将改变整体结构）。区域空间分析困难，相邻区域边界被重复存储。 465、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（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,

28、1),(B,4,3) A A A A A B B B A A B B A A B B 475、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 行程编码按行（或列）记录相同代码的始末象元的列号（或行号）和相应的代码，即按（起位、止位、属性值）编码，下图可沿行方向进行行程编码：156485、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 行程编码只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重重的个数。即按（属性值和重复个数）编码。53495、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 行程编码逐个记录各行（或列）代码

29、发生变化的位置和相应的代码，即按（位置，属性值）编码。505、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 行程编码特点： 对于行程长度编码，区域越大，数据的相关性越强，则压缩越大，适用于类型区域面积较大的专题图，而不适合于类型连续变化或类别区域分散的分类图（压缩比与图的复杂程度成反比）。 这种编码在栅格加密时，数据量不会明显增加，压缩率高，并最大限度地保留原始栅格结构，编码解码运算简单，且易于检索，叠加，合并等操作，这种编码应用广泛。515、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 块式编码行程编码向二维扩展把多边形范围划分成由象元组成的正方形

30、，然后对各个正方形进行编码。块式编码数据结构中包括3个数字：块的初始位置（行、列号）和块的大小（块包括的象元数），再加上记录单元的代码组成。 采用正方形区域作为记录单元，每个记录单元包括相邻的若干栅格。 数据对组成：（初始行、列，半径/大小，属性值）525、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 块式编码行程编码向二维扩展 1 2 3 4 5 6 7 8 1 0 4 4 7 7 7 7 72 4 4 4 4 4 7 7 73 4 4 4 4 8 8 7 7 4 0 0 4 8 8 8 7 75 0 0 8 8 8 8 7 86 0 0 0 8 8 8 8 87 0

31、0 0 0 8 8 8 88 0 0 0 0 0 8 8 8如：（1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7)依次扫描，编过的不重复。特点： 具有可变分辨率，即当属性变化小时图块大，对于大块图斑记录单元大，分辨率低，压缩比高。 小块图斑记录单元小，分辨率高，压缩比低，所以，与行程编码类似，随图形复杂程度的提高而提高分辨率。535、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码一种可变分辨率的非均匀网格系统。是最有效的栅格数据压缩编码方法之一 。1）基本思想：将2n2n象元组成的图像(不足的用背景补上) 按四个象限进行递归分割，并判

32、断属性是否单一，单一：不分。 不单一：递归分割。AAABABBBAABBAABB0123545、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码2）四叉树的树形表示：用一棵倒立树表示这种分割和分割结果。树根结点：代表整个区域；叶结点（叶）：树的每个结点有四棵子树，为空的结点为叶结点，对应于区域分割时数值单调的子象限，即不能再分割的块，图斑大小取决于它在树中的层数；结点（树叉）：对应于区域分割时数值不单调的子象限。 每个树叉均有4个分叉，叫四叉树。555、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码16234511121378910

33、162345111312781097第3层第2层第1层第0层根结点叶结点结点（a）顺序分解表示（b）树形结构表示565、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码3）建立四叉树结构的方式 自上而下方式(top-down) 从顶层开始，即先检测全区域，其值不单一时再四划分，直到数值或内容单一为止。 自下而上方式(bottom-up) 从底层开始，即以像元大小为结点，每记录四个结点时，即生成父结点。575、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码4）四叉树结构类型根据四叉树存储结构的不同，可以将四叉树结构类型分为: 指针四叉

34、树 线性四叉树585、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码5）编码方法：a、常规四叉树（指针四叉树）记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系，每个结点需要6个变量：父结点指针、四个子结点的指针和本结点的属性值。595、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码5）编码方法a、常规四叉树（指针四叉树）SW2SE3NE1NW0根结点结点叶结点012310111213120121122123指针四叉树的分解过程及编码88023112110111213605、栅格数据编码方法二、栅格数据结构第二章 空间数据结

35、构（2）压缩编码 四叉树编码5）编码方法：a、常规四叉树（指针四叉树）特点：指针不仅增加了数据的存储量，还增加了操作的复杂性：如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。所以，常规四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检索。615、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码5）编码方法：b、线性四叉树线性四叉树编码为美国马里兰大学地理信息系统中采用的编码方式，具有四叉树的形式，用指针四叉树方式组织数据，但不用指针四叉树方式存储数据。基本思想：它不记录中间节点和使用指针，仅记

36、录叶节点，并用地址码表示叶节点的位置。因此，其编码包括叶节点的地址码和本节点的属性或灰度值，并且地址码隐含了叶节点的位置和深度信息。625、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码5）编码方法：b、线性四叉树最常见的地址码是四进制或十进制的Morton码。基于深度和层次的线性四叉树编码：记录每个叶节点的地址和属性值。其中地址包括两部分，以32位二进制数表示： 0 0 0 00 0 0 1 0 0 1 0 0 0 1 1深度（4位）路径（28位）从叶节点到根节点的路径0231路径：011SE 000SW 102NW深度：00113第三层635、栅格数据编码方

37、法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码5）编码方法：b、线性四叉树四进制地址码(MQ码) MQ码是一串数字组成，每分割一次增加一位数，其中每位数字都是不大于3的四进制数。 A、分割一次，增加一位数字，大分割在前，小分割在后。所以，码的位数表示分割的次数。 B、每一个位均是不大于3的四进制数，表达位置。0123AAAAA BBBAABBA AABB03BA645、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码5）编码方法：b、线性四叉树四进制地址码(MQ码)320？1320自上而下655、栅格数据编码方法二、栅格数据结构第二章 空间数据结

38、构（2）压缩编码 四叉树编码5）编码方法：b、线性四叉树四进制地址码(MQ码)MQ码计算公式：MQ = 2Ib+Jb 公式中Ib、Jb分别为栅格单元行列号的二进制数， Ib、Jb位数看即编码的位数，要看分割的次数，不足的前面补0.66(a)区域栅格表示5、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码5）编码方法：b、线性四叉树四进制地址码(MQ码)MQ编码过程：图(a)所示为88列图，即栅格单元2323，其位置码的最长位数是3位（即分割三次）。现对图 (a)按MQ码的计算公式进行编码，得到图 (b)所示编码表，最后进行排序归并得到图 (c) MQ码。(b)编码

39、表(c)MQ码自下而上675、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码5）编码方法：b、线性四叉树十进制地址码(MD码) 四进制Morton码直观上切合四叉树分割，但许多语言不支持四进制变量，需用十进制表示Morton码。线性四叉树的十进制编码简称MD编码，它同线性四叉树的四进制编码主要不同在于编码值是十进制自然数，其合并过程可直接按自然数顺序进行。685、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码5）编码方法：b、线性四叉树十进制地址码(MD码)A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B

40、13A 10A 11B 14B 15如行为2、列为3的栅格的MD步骤：(1)行、列号为二进制 Ib= 1 0 Jb= 1 1(2)I行J列交叉 1 1 0 1 = 13(3)再化为十进制. 实质上是按左上、右上、左下、右下的顺序，从零开始对每个栅格进行自然编码。 695、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码(a)区域栅格表示705、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码MQ编码例证1：第一行、第五列的栅格单元，求它的MQ码首先将十进制第一行、第五列转成二进制形式，得到 行Ib =(001) 列Jb =(101)其

41、地址码为: MQ = 2Ib+Jb = 21+101 = 103？提示：MQ = 2Ib+Jb715、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码MQ编码例证2：求四叉树中四进制位置码的解码，即已知MQ码为103，求其行列号。算法如下：？ 若该位编码值为0，1，对行号贡献值为0 若该位编码值为2，3，对行号贡献值为1 若该位编码值为0，2，对列号贡献值为0 若该位编码值为1，3，对列号贡献值为l MQ 1 0 3 表示MQ码为103的单元 二进制行值 0 0 1 表示第一行 二进制列值 1 0 1 表示第五列725、栅格数据编码方法二、栅格数据结构第二章 空间

42、数据结构（2）压缩编码 四叉树编码 MQ 1 0 3 表示MQ码为103的单元 二进制行值 0 0 1 表示第一行 二进制列值 1 0 1 表示第五列 这表示MQ码为103的单元处于第一行、第五列。最后，线性四叉树的每个叶接点可用三元组的线性表来表示。 三元组结构为 (M，D，V) 其中M为叶结点的地址码；D为叶结点的深度；V为叶结点的格网属性.735、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码MD编码例证：把一幅2n2n的图像压缩成线性四叉树的过程 1按Morton码把图象读入一维数组。 2相邻的四个象元比较，一致的合并，只记录第一个象元的Morton码。

43、循环比较所形成的大块，相同的再合并，直到不能合并为止。 3进一步用游程长度编码压缩。压缩时只记录第一个象元的Morton码。745、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码MD编码例证：把一幅2n2n的图像压缩成线性四叉树的过程A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 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 B2四相邻象元

44、合并，只记录第一个象元的Morton码。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B3由于不能进一步合并，可用行程长度编码压缩。 0 3 4 6 8 12 A B A B A B 755、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码优缺点（1）易于计算多边形的数量特征；（2）四叉树表示法基本上是一种非冗余表示法，可用较少的存储量精确的表示复杂的图形；（3）四叉树具有可变率或多重分辩率的特点使得它有很好的应用前景，适用于处理凝聚性或呈块状分布的空间数据，特别适用于处理分布不均匀的块状空间数据，但不适用于连续表面（如地形）或线

45、状地物。（3）栅格到四叉树及四叉树到简单栅格结构的转换比其他压缩方法容易 。（4）便于在多边形中嵌套多边形，如表示“岛” 。优点765、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码优缺点（1）矢/栅正反变换还不理想。（2）建立四叉树耗费机时很多。（3）四叉树虽可修改，但很费事（具体的数据结构中会提到）。（4）未能表示物体间的拓扑关系。（5）数据结构复杂，当同时提供多种四叉树结构时，不利于分析。缺点775、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码优缺点（6）与非树表示法比较，四叉树表示法的缺点在于转换的不稳定性或叫滑动变异。

46、例如，两个图像的差异仅由于平移，就会构成极为不同的四叉树，因而很难根据四叉树来判断这两个图像是否全同，故不利于做形状分析和模式识别。缺点785、栅格数据编码方法二、栅格数据结构第二章 空间数据结构（2）压缩编码 四叉树编码优缺点（7）一个物体的图像在构成四叉树时会被分割到若干个象限中，使它失去了内在的相关性。缺点A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15796、栅格数据的优缺点二、栅格数据结构第二章 空间数据结构栅格数据的优点 地理要素表达比较直观，直接记录空间实体的属性值，数据存储结构简单，并容易实现叠加分析、数据统计等操作

47、栅格数据的缺点数据冗余度大，造成存储空间的浪费像元大小的变化，对长度、面积等的度量有较大影响不宜进行某些空间查询和网络分析？80三、矢量数据结构第二章 空间数据结构 矢量是具有一定大小和方向的量。 线段长度表示大小，线段端点的顺序表示方向。 有向线段用一系列有序特征点表示，矢量数据就是代表地图图形的各离散点平面坐标（x,y）的有序集合。 矢量数据结构主要用于表示地图图形元素几何数据之间及其与属性数据之间的相互关系。矢量数据结构是通过坐标值来精确地表示点、线、面等地理实体的。81三、矢量数据结构第二章 空间数据结构1、图形表示822、矢量数据的获取方式三、矢量数据结构第二章 空间数据结构1) 由

48、外业测量获得 可利用测量仪器自动记录测量成果(常称为电子手薄)，然后转到地理数据库中。2) 由栅格数据转换获得 利用栅格数据矢量化技术，把栅格数据转换为矢量数据。3) 跟踪数字化 用跟踪数字化的方法，把地图变成离散的矢量数据。833、矢量数据组织三、矢量数据结构第二章 空间数据结构矢量数据表示时应考虑以下问题：矢量数据自身的存贮和处理。与属性数据的联系。矢量数据之间的空间关系(拓扑关系)。点：坐标对（x,y） +识别符线：坐标对系列(x1,y1).(xn,yn) 及有关属性、其它属性面：首尾相同的坐标串关系表几何位置坐标文件连接84第二章 空间数据结构标识码属性码空间对象编码唯一连接空间和属性

49、数据数据库独立编码点: ( x ,y )线: ( x1 , y1 ) , (x2 , y2 ) , , ( xn , yn )面: ( x1 , y1 ) , (x2 , y2 ) , , ( x1 , y1 )点位字典点: 点号文件线: 点号串面: 点号串点号XY1112223344n5566存储方法854、矢量数据编码方式三、矢量数据结构第二章 空间数据结构（1）实体式（spaghetti）- 面条模型:以实体为单位记录其坐标。 点实体 线实体 面实体86方向字体排列指针与线相交的角度如果是简单点符号符号字符大小简单点文字说明结点唯一识别符比例尺方向x，y 坐标其它有关的属性点实体类型序列

50、号有关的属性如果是文字说明如果是结点点实体87线实体唯一标识码线标识码起始点终止点坐标对序列显示信息非几何属性线实体 与线表非常相似，但它的最后一个结点坐标值与第一个结点坐标值相同。 对于多边形中的“岛”，处理方法是在每个多边形头记录中增加一条“岛”的属性来表示优先级，低优先级的多边形先绘置先充填，高优先级的多边形后绘置，这样岛多边形就覆盖了原先的多边形。面实体884、矢量数据编码方式三、矢量数据结构第二章 空间数据结构（1）实体式 优点 结构简单、直观、易实现以实体为单位的运算和显示。 缺点 1、相邻多边形的公共边界被数字化并存储两次，造成数据冗余和碎屑多边形数据不一致，浪费空间，导致双重边

51、界不能精确匹配。 2、自成体系，缺少多边形的邻接信息，无拓扑关系，难以进行邻域处理，如消除多边形公共边界，合并多边形。 3、岛作为一个单个图形，没有与外界多边形联系。不易检查拓扑错误。 所以，这种结构只用于简单的制图系统中，显示图形。894、矢量数据编码方式三、矢量数据结构第二章 空间数据结构（2）索引式对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件。1234567891011 1213 1415PPPMap1）点文件：点号坐标1x1,y1索引文件：面号弧段号P1A,B,C3）面文件：2）弧段文件:弧段号起点终点点号A527,8,9,10904、矢量数据编码方式三、矢量

52、数据结构第二章 空间数据结构（2）索引式与实体式相比：优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。缺点：表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。914、矢量数据编码方式三、矢量数据结构第二章 空间数据结构（3）双重独立式编码1234567891011 1213 1415PPPMap简称DIME(Dual Independent Map Encoding)，是美国人口统计系统采用的一种编码方式，是一种拓扑编码结构。1）点文件：点号坐标1x1,y12）

53、线文件:线文件是以线段为记录单位 线号左多边形 右多边形 起点终点L210P1P2210关联邻接关联连通拓扑关系明确924、矢量数据编码方式三、矢量数据结构第二章 空间数据结构（3）双重独立式编码1234567891011 1213 1415PPPMap简称DIME(Dual Independent Map Encoding)，是美国人口统计系统采用的一种编码方式，是一种拓扑编码结构。3）面文件面号线号P1L210,L109在DIME中做如下改进： 将以线段为记录单位改为以弧段为单位链状双重独立式编码934、矢量数据编码方式三、矢量数据结构第二章 空间数据结构（4）链式双重独立式编码拓扑数据结

54、构1234567891011 1213 1415PPPMap1）弧段坐标文件：弧段号坐标系列（串)Ax2,y2,X10,y102）弧段文件：链面，链结点关系 弧段号 左多边形 右多边形 起点终点AP1P2253）面文件面号弧段号 P1A,B,-C944、矢量数据编码方式三、矢量数据结构第二章 空间数据结构（4）链式双重独立式编码拓扑数据结构1234567891011 1213 1415PPPMap4）点拓扑文件： 结点链关系 点号 弧段号 2A,B,D在拓扑结构中，多边形（面）的边界被分割成一系列的线（弧、链、边）和点（结点）等拓扑要素，点、线、面之间的拓扑关系在属性表中定义，多边形边界不重复

55、。 954、矢量数据编码方式三、矢量数据结构第二章 空间数据结构（4）链式双重独立式编码拓扑数据结构特点：拓扑关系明确，也能表达岛信息，而且以弧段为记录单位，满足实际应用需要。因为一般数字化一条街道时，必然有许多中间点，但我们在做空间分析是却没有必要以这些中间点所组成的折线为研究对象，而应以整条弧段（某条街道）为研究对象. 被一些成熟的商品化软件采用，如ARC/INFO软件。例：ARC文件：二进制文件: 弧段号 点数 坐标串 在GIS数据输入中，建拓扑是指给图形数据（点、线、面）增加拓扑结构， INFO：属性表如AAT（Arc Attribute Table）用户标识码，表明地物类型当图形数据

56、修改、删除、增加点、线、面要素后，其拓扑关系也发生改变，所以，需重新建拓扑。弧段号USER_IDLPOLYRPOLYFROM_NODETO_NODE其它属性:（名称)96三、矢量与栅格数据结构的比较第二章 空间数据结构97第二章 空间数据结构98第二章 空间数据结构99第二章 空间数据结构100四、矢量、栅格数据结构的选择第二章 空间数据结构 在GIS建立过程中，应根据应用目的和应用特点、可能获得的数据精度以及地理信息系统软件和硬件配置情况，选择合适的数据结构。 栅格结构:大范围小比例尺的自然资源、环境、农林业等区域问题的研究。是一种影像数据结构，适用于遥感图像的处理。 矢量结构：城市分区或详

57、细规划、土地管理、公用事业管理等方面的应用，便于网络分析、制图应用。101五、矢量、栅格数据一体化第二章 空间数据结构1、基本概念 将矢量面对目标的方法和栅格元子充填的方法结合起来，具体采用填满线状目标路径和充填面状目标空间的方法作为一体化数据结构的基础。 线状地物：除记录原始取样点外，还记录路径所通过的栅格。 面状地物：除记录它的多边形周边以外，还包括中间的面域栅格。102五、矢量、栅格数据一体化第二章 空间数据结构1、基本概念 一方面，它保留了矢量的全部性质，以目标为单元直接聚集所有的位置信息，并能建立拓扑关系； 另一方面，它建立了栅格与地物的关系，即路径上的任一点都直接与目标建立了联系。

58、从原理上说，这是一种以矢量的方式来组织栅格数据的数据结构。103五、矢量、栅格数据一体化第二章 空间数据结构2、三个约定为了便于组织数据，首先作如下约定；（1）地面上的点状地物是地球表面上的点，它仅有空间位置，没有形状和面积。在计算机内部只需要表示该点的一个位置数据及与结点关联的弧段信息。（2）地面上的线状地物是地球表面的空间曲线，它有形状但没有面积，它在平面上的投影是一连续不间断的直线或曲线。在计算机内部需要用一组元子填满整个路径，并表示该弧段相关的拓扑信息。 （3）地面上的面状地物是地球表面的空间曲面，并具有形状和面积，它在平面上的投影是由边界包围的紧致空间和一组填满路径的元子表达的边界组

59、成。在计算机内部需表示由元子填满路径的一组边界和由边界组成的空间。104五、矢量、栅格数据一体化第二章 空间数据结构3、细分格网法 由于栅格数据结构的精度低,通常用细分格网的方法来提高点、线、面状目标边界线数据的表达精度，即在有点、线目标通过的基本格网内，再细分成16 16或256 256 个细格网，以提高精度。 将一对X,Y坐标用两个Morton码代替：前一M1表示该点（采样点或附加的交叉点）所在基本格网的地址码，后者M2 表示该点对应的细分格网的Morton码，既顾全整体定位，又保证精度。 x,yM1 M2105五、矢量、栅格数据一体化第二章 空间数据结构4、一体化数据结构设计 线性四叉树

60、(Morton)是基本数据格式，三个约定设计点、线、面数据结构的基本依据，细分格网法保证足够精度。（1）点状地物和结点的数据结构约定1，点仅有位置、没有形状和面积，只要将点的坐标转化为地址码M1和M2 ,结构简单灵活，便于点的插入和删除，还能处理一个栅格内包含多个点状目标的情况。点状目标及其数据结构结点及其数据结构坐标点的地址码106五、矢量、栅格数据一体化第二章 空间数据结构4、一体化数据结构设计（2）线状地物和弧段的数据结构约定2，线状地物有形状但没有面积，没有面积意味着只要用一串数据表达每个线状地物的路径即可，将该线状地物经过的所有栅格的地址全部记录下来。仿照矢量数据组织的链状双重独立式