空间数据结构

1、2022-5-41第二章 空间数据结构教师：杨勇华中农业大学 资源与环境学院22022-5-4一、地理实体（空间实体）一、地理实体（空间实体）定义定义： 指自然界现象和社会经济事件中不能再分指自然界现象和社会经济事件中不能再分割的单元割的单元，它是一个具体有，它是一个具体有概括性，复杂概括性，复杂性，相对意义性，相对意义的概念。的概念。32022-5-4理解地理实体理解地理实体n抽象抽象：地理现象 抽象成 地理实体n抽象的程度与研究区域的大小、规模不同而有所不同，也和研究尺度相关。42022-5-452022-5-4概括性概括性n地理实体概括了所表示地理现象的内容和属性，包括空间属性、类型属性

2、、性质属性等内容。62022-5-4复杂性复杂性n地理实体内容复杂，包含的属性众多n地理实体相互间关系复杂n地理实体表达方式复杂72022-5-4二、地理实体的描述空间数据 1 1、描述的内容、描述的内容 3 3、数据类型、数据类型 4 4、数据结构、数据结构几何数据（空间几何数据（空间数据、图形数据）数据、图形数据） 关系数据关系数据实体实体间的邻接、关联间的邻接、关联包含等相互关系包含等相互关系 属性数据属性数据各种各种属性特征和时间属性特征和时间元数据元数据 矢量、栅格、矢量、栅格、TINTIN（专用于地（专用于地表或特殊造型）表或特殊造型） RDBMSRDBMS属性表属性表- -采用采

3、用MISMIS较成熟较成熟 空间元数据空间元数据位置、形状、尺位置、形状、尺寸寸 、识别码（名称）识别码（名称）实体的角色、功实体的角色、功能、行为、实体能、行为、实体的衍生信息的衍生信息时间时间测量方法、编码测量方法、编码方法、空间参考方法、空间参考系等系等 空间特征：地理空间特征：地理位置和空间关系位置和空间关系属性特征属性特征名称、名称、等级、类别等等级、类别等时间特征时间特征2 2、基本特征、基本特征 82022-5-4空间数据的基本特征空间数据的基本特征92022-5-4三、实体的空间特征n点状实体n线状实体n面状实体n体状实体102022-5-4三、实体的空间特征1、点状实体点或节

4、点、点状实体。点：有特定位置，维数为点或节点、点状实体。点：有特定位置，维数为0 0的物体。的物体。 4 4）角点、节点）角点、节点VertexVertex：表示线段和弧段上的连接点。表示线段和弧段上的连接点。 1）实体点）实体点：用来代表一个实体。：用来代表一个实体。2）注记点）注记点：用于定位注记。：用于定位注记。3）内点：）内点：用于负载多边形的属性，用于负载多边形的属性，存在于多边形内。存在于多边形内。112022-5-4三、实体的空间特征2、线状实体1）实体长度）实体长度：从起点到终点的总长从起点到终点的总长2）弯曲度）弯曲度：用于表示像道路拐弯时弯曲的程度。用于表示像道路拐弯时弯曲

5、的程度。3）方向性）方向性：如：水流方向，上游如：水流方向，上游下游，下游， 公路，单、双向之分。公路，单、双向之分。具有相同属性的点的轨迹，线或折线，由一系列的有序坐标表示，并有如下具有相同属性的点的轨迹，线或折线，由一系列的有序坐标表示，并有如下特性特性：线状实体包括线状实体包括：线段，边界、链、弧段、网络等。线段，边界、链、弧段、网络等。122022-5-4三、实体的空间特征3、面状实体（多边形）面状实体的如下面状实体的如下特征特征：1 1）面积范围面积范围 2 2）周长周长3 3）独立性或与其它地物相邻独立性或与其它地物相邻如中国及其周边国家如中国及其周边国家4 4）内岛屿或锯齿状外形

6、内岛屿或锯齿状外形：如岛屿的海岸线封闭所围成的区域。如岛屿的海岸线封闭所围成的区域。5 5）重叠性与非重叠性）重叠性与非重叠性： 如学校的分区，菜市场的服务范围等如学校的分区，菜市场的服务范围等都有可能出现交叉重叠现象，而一个城都有可能出现交叉重叠现象，而一个城市的各个城区一般说来不会出现重叠。市的各个城区一般说来不会出现重叠。 是对湖泊、岛屿、地块等一类现象的描述。是对湖泊、岛屿、地块等一类现象的描述。在数据库中由在数据库中由一封闭曲线加内点一封闭曲线加内点来表示。来表示。132022-5-4什么是空间数据结构什么是空间数据结构n描述地理实体的数据的组织方法，称为内部数据结构。空间数据结构空

7、间数据结构是指适合于计算机系统存储、管理和处理的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述。n它是对数据的一种理解和解释，不说明数据结构的数据是毫无用处的，不仅用户无法理解，计算机程序也不能正确处理。n对同一组数据，按不同的数据结构去处理，得到的可能是截然不同的内容。（矢量，栅格）n空间数据结构是GIS沟通信息的桥梁，只有充分理解GIS所采用的特定数据结构，才能正确地使用系统。(数据输出，操作)142022-5-4什么样的数据结构才是好的数据结构什么样的数据结构才是好的数据结构n组织的数据能够表示要素之间的层次关系，便于不同数据连接和覆盖n能正确反映地理实体的空间排列方式

8、和各实体间的相互关系n便于存储和检索n节省存储空间，减少数据冗余n存取速度快n足够的灵活性，数据组织应具有插入新的数据、删除或修改部分数据的基本功能152022-5-4162022-5-42.1 栅格数据结构栅格数据结构 栅格结构用密集正方形（或三角形，多边形）栅格结构用密集正方形（或三角形，多边形）将地理区域将地理区域划分划分为网格阵列。为网格阵列。位置由行，列号定义，属性为栅格单元的值。位置由行，列号定义，属性为栅格单元的值。点点：由：由单个栅格单个栅格表达。表达。线线：由沿线走向有相同属性取值的：由沿线走向有相同属性取值的一组相邻栅格一组相邻栅格表达。表达。面面：由沿线走向有相同属性取值

9、的：由沿线走向有相同属性取值的一片栅格一片栅格表达。表达。 栅格数据表示的是二维表面上的地理数据的离散化栅格数据表示的是二维表面上的地理数据的离散化数值。在栅格数据中，地表被分割为相互邻接、规则数值。在栅格数据中，地表被分割为相互邻接、规则排列的地块，每个地块与一个象元相对应。因此，栅排列的地块，每个地块与一个象元相对应。因此，栅格数据的格数据的比例尺比例尺就是就是栅格栅格( (象元象元) )的大小与地表相应单的大小与地表相应单元的大小之比元的大小之比，当象元所表示的面积较大时，对长度、，当象元所表示的面积较大时，对长度、面积等的量测有较大影响。每个象元的属性是地表相面积等的量测有较大影响。每

10、个象元的属性是地表相应区域内地理数据的近似值，因而有可能产生应区域内地理数据的近似值，因而有可能产生属性方属性方面的偏差面的偏差。22122332333233323332333172022-5-4栅格数据结构栅格数据结构SPOT XS 20m*20m 牡丹水庫band G, R, IR182022-5-4栅格数据层栅格数据层2 222 2aaaaa2 2土壤土壤植被植被组织方法组织方法空间数据库空间数据库192022-5-4202022-5-4栅格数据层组织方法栅格数据层组织方法方法方法c c：以层为基础，以层为基础，每层内以多边形为序每层内以多边形为序记录多边形的属性值记录多边形的属性值和多

11、边形内各象元的和多边形内各象元的坐标坐标。节约用于存储。节约用于存储属性的空间。将同一属性的空间。将同一属性的制图单元的属性的制图单元的n n个个象元的属性只记录一象元的属性只记录一次，便于地图分析和次，便于地图分析和制图处理。制图处理。 方法方法a a：以象元为记录序列，不同层上同一象元位置上的各以象元为记录序列，不同层上同一象元位置上的各属性值表示为一个列数组。属性值表示为一个列数组。N层中层中只记录一层的象元位置，只记录一层的象元位置，节约大量存储空间，节约大量存储空间，栅格个数很多。栅格个数很多。方法方法b b：每层每个象元的位置、属性一一记录，每层每个象元的位置、属性一一记录，结构最

12、简单，但浪费存储。结构最简单，但浪费存储。212022-5-4栅格数据的建立栅格数据的建立1、 手工获取手工获取，专题图上划分均匀网格，专题图上划分均匀网格，逐个决定其网格代码。逐个决定其网格代码。2、扫描仪扫描扫描仪扫描专题图的图像数据专题图的图像数据行、行、列、颜色（灰度）列、颜色（灰度），定义颜色与属性，定义颜色与属性对应表，用相应属性代替相应颜色，得对应表，用相应属性代替相应颜色，得到（行、列、属性）再进行栅格编码、到（行、列、属性）再进行栅格编码、存贮，即得该专题图的栅格数据。存贮，即得该专题图的栅格数据。3、 由矢量数据转换而来由矢量数据转换而来。4、 遥感影像数据，遥感影像数据，

13、对地面景象的辐射对地面景象的辐射和反射能量的扫描抽样，并按不同的光和反射能量的扫描抽样，并按不同的光谱段量化后，以数字形式记录下来的象谱段量化后，以数字形式记录下来的象素值序列。素值序列。5、 格网格网DEM数据数据，当属性值为地面高，当属性值为地面高程，则为格网程，则为格网DEM，通过，通过DEM内插得内插得到。到。（一）建立途径（一）建立途径（二）栅格系统的确定（二）栅格系统的确定(三三)栅格代码的确定栅格代码的确定222022-5-4栅格数据的建立栅格数据的建立（一）建立途径（一）建立途径（二）栅格系统的确定（二）栅格系统的确定(三三)栅格代码的确定栅格代码的确定1 1、 栅格坐标系的确

14、定栅格坐标系的确定表示具有空间分布特征的地理要素，不论采用什么编码系统，什么表示具有空间分布特征的地理要素，不论采用什么编码系统，什么数据结构数据结构( (矢、栅矢、栅) )都应在统一的坐标系统下，而坐标系的确定实质都应在统一的坐标系统下，而坐标系的确定实质是坐标系原点和坐标轴的确定。是坐标系原点和坐标轴的确定。 由于栅格编码一般用于区域性由于栅格编码一般用于区域性GISGIS，原点的选择常具有局部性，原点的选择常具有局部性质，但为了便于区域的拼接，栅格系统的质，但为了便于区域的拼接，栅格系统的起始坐标应与国家基本比起始坐标应与国家基本比例尺地形图公里网的交点相一致例尺地形图公里网的交点相一致

15、，并分别采用，并分别采用公里网的纵横坐标轴公里网的纵横坐标轴作为栅格系统的坐标轴作为栅格系统的坐标轴。22122332333233323332232022-5-4栅格数据的建立栅格数据的建立2 2、 栅格单元的尺寸栅格单元的尺寸1）原则）原则：应能：应能有效地逼近空间对象的分有效地逼近空间对象的分布特征，又减少数据的冗余度布特征，又减少数据的冗余度。格网太大，忽略较小图斑，信息丢失。格网太大，忽略较小图斑，信息丢失。一般讲实体特征愈复杂，栅格尺寸越小，一般讲实体特征愈复杂，栅格尺寸越小，分辨率愈高，然而栅格数据量愈大（按分辨率愈高，然而栅格数据量愈大（按分辨率的平方指数增加）计算机成本就分辨率

16、的平方指数增加）计算机成本就越高，处理速度越慢。越高，处理速度越慢。2）方法）方法：用保证最小多边形的精度标准：用保证最小多边形的精度标准来确定尺寸经验公式：来确定尺寸经验公式： h h为栅格单元边长为栅格单元边长 AiAi为区域所有多边形的面积。为区域所有多边形的面积。（一）建立途径（一）建立途径（二）栅格系统的确定（二）栅格系统的确定(三三)栅格代码的确定栅格代码的确定242022-5-4栅格结构精度偏差栅格结构精度偏差252022-5-4栅格数据的建立栅格数据的建立 当一个栅格单元内有多个可选属性值时，按一当一个栅格单元内有多个可选属性值时，按一定方法来确定栅格属性值。定方法来确定栅格属

17、性值。1、中心点法、中心点法：取位于栅格中心的属性值为该栅格：取位于栅格中心的属性值为该栅格的属性值。的属性值。 2、面积占优法、面积占优法：栅格单元属性值为面积最大者，：栅格单元属性值为面积最大者，常用于分类较细，地理类别图斑较小时。常用于分类较细，地理类别图斑较小时。 3、 重要性法重要性法：定义属性类型的重要级别，取重要：定义属性类型的重要级别，取重要的属性值为栅格属性值，常用于有重要意义而面积的属性值为栅格属性值，常用于有重要意义而面积较小的要素，特别是点、线地理要素。较小的要素，特别是点、线地理要素。 4、百分比法百分比法：根据格网中各地理要素所占面积的根据格网中各地理要素所占面积的

18、百分比确定栅格单元的代码参与。百分比确定栅格单元的代码参与。（一）建立途径（一）建立途径（二）栅格系统的确定（二）栅格系统的确定(三三)栅格代码的确定栅格代码的确定262022-5-4栅格数据取值方法栅格数据取值方法272022-5-4栅格数据存储的压缩编码栅格数据存储的压缩编码直接栅格编码直接栅格编码：将栅格数据看作一个数据矩阵，将栅格数据看作一个数据矩阵，逐行记录代码数据。逐行记录代码数据。1）每行都从左到右记录；）每行都从左到右记录； AAAAABBBAABBAABB2）奇数行从左到右，偶数行从右到左；）奇数行从左到右，偶数行从右到左；特点特点：最直观、最基本的网格存贮结构，没有进行任最

19、直观、最基本的网格存贮结构，没有进行任何压缩数据处理何压缩数据处理。AAAAABBBAABBAABB栅格数据量大，格网数多，由于地理数据往往有较强的相关性，即相邻象元栅格数据量大，格网数多，由于地理数据往往有较强的相关性，即相邻象元的值往往是相同的。的值往往是相同的。因此该文件存在大量的数据冗余。当栅格越小，表示的因此该文件存在大量的数据冗余。当栅格越小，表示的空间精度越高时，这种冗余越严重，因此，对栅格数据进行压缩编码非常重空间精度越高时，这种冗余越严重，因此，对栅格数据进行压缩编码非常重要。要。所以，出现了各种栅格数据压缩方法。所以，出现了各种栅格数据压缩方法。数据压缩是将数据表示成更紧凑

20、的格式以减少存储空间的一项技术数据压缩是将数据表示成更紧凑的格式以减少存储空间的一项技术。数据压缩要求数据压缩要求：不失真，变换简单，压缩、解压迅速可靠：不失真，变换简单，压缩、解压迅速可靠282022-5-4栅格数据存储的压缩编码栅格数据存储的压缩编码1、链式编码、链式编码、Freeman 链码、边界链码链码、边界链码返回返回1）首先定义一个）首先定义一个3x3窗口，中间栅格的走向有窗口，中间栅格的走向有8种可能，并将这种可能，并将这8种可能种可能07进行编码。进行编码。2）记下地物属性码和起点行、列后，进行追）记下地物属性码和起点行、列后，进行追踪，得到矢量链踪，得到矢量链.将栅格数据（线

21、状地物面域边界）表示为将栅格数据（线状地物面域边界）表示为矢量链矢量链的记录的记录链式编码表链式编码表aaaaaaab属性码起点行起点列链码链码a14556656b37576654323 优点优点：链码可有效地存贮压缩栅格数据，便于面积、长度、转折方向和：链码可有效地存贮压缩栅格数据，便于面积、长度、转折方向和边界、线段凹凸度的计算。边界、线段凹凸度的计算。 缺点缺点：不易做边界合并，插入操作、编辑较困难（对局部修改将改变整：不易做边界合并，插入操作、编辑较困难（对局部修改将改变整体结构）。区域空间分析困难，相邻区域边界被重复存储。体结构）。区域空间分析困难，相邻区域边界被重复存储。 2920

22、22-5-4链码编码链码编码： 2，2 ，6 ，7，6，0，6，5123450760 5 0 0 0 0 0 00 0 5 0 0 0 0 00 0 0 0 0 0 0 00 5 0 0 0 0 0 00 0 5 5 0 0 0 00 0 0 5 0 0 0 00 0 5 0 0 0 0 00 0 0 0 0 0 0 0链码编码示例链码编码示例 链式编码的前两个数字链式编码的前两个数字表示起点的行、列数，从第表示起点的行、列数，从第三个数字开始的每个数字表三个数字开始的每个数字表示单位矢量的方向，八个方示单位矢量的方向，八个方向以向以0 07 7的整数代表。的整数代表。 302022-5-4链

23、式编码示例链式编码示例76543012007 0 121 07 7 0312022-5-4栅格数据存储的压缩编码栅格数据存储的压缩编码2、行程编码、行程编码将原图表示的数据矩阵变为将原图表示的数据矩阵变为数据对数据对方法一：只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数。3334444433334444133344421133322211113222111122221111122211111222第一行：（3，3）（4，5）第二行：（3，4）（4，4）第三行：（1，1）（3，3） （4，3）（2，1）第四行：（1，2）（3，3）（2，3）第五行：（1，4）（3，1）（

24、2，3）322022-5-4栅格数据存储的压缩编码栅格数据存储的压缩编码2、行程编码、行程编码方法二：逐个记录各行（或列）代码发生变化的位置和相应代码，即按（位置，属性值）编码3 3 3 4 4 4 4 43 3 3 3 4 4 4 41 3 3 3 4 4 4 21 1 3 3 3 2 2 21 1 1 1 3 2 2 21 1 1 1 2 2 2 21 1 1 1 1 2 2 21 1 1 1 1 2 2 2第一列：（1，3）（3，1）第二列：（1，3）（4，1）第三列：（1，3）（5，1）第四列：（1，4）（2，3）（5，1）第五列：（1，4）（4，3）（6，2） （7，1）332022

25、-5-4栅格数据存储的压缩编码栅格数据存储的压缩编码2、行程编码、行程编码方法三：按行（或列）记录相同代码的始末像元的列号（或行号）和相应代码，即按（起位，止位，属性值）编码3 3 3 4 4 4 4 43 3 3 3 4 4 4 41 3 3 3 4 4 4 21 1 3 3 3 2 2 21 1 1 1 3 2 2 21 1 1 1 2 2 2 21 1 1 1 1 2 2 21 1 1 1 1 2 2 2第一行：（1，3，3）（4，8，4）第二行：（1，3，3）（5，8，4）第三行：（1，1，1）（2，4，3） （5，7，4）（8，8，2）第四行：（1，2，1）（3，5，3） （6，8，

26、2）第五行：（1，4，1）（5，5，3） （6，8，2）342022-5-4栅格数据存储的压缩编码栅格数据存储的压缩编码特点：特点： 对于游程长度编码，区域越大，数据的相关性越强，则对于游程长度编码，区域越大，数据的相关性越强，则压缩越大，压缩越大，适用于类型区域面积较大的专题图适用于类型区域面积较大的专题图，而不适合，而不适合于类型连续变化或类别区域分散的分类图（压缩比与图的于类型连续变化或类别区域分散的分类图（压缩比与图的复杂程度成反比）。复杂程度成反比）。 这种编码在这种编码在栅格加密时，数据量不会明显增加栅格加密时，数据量不会明显增加，压缩率压缩率高，并最大限度地保留原始栅格结构，编码

27、解码运算简单，高，并最大限度地保留原始栅格结构，编码解码运算简单，且易于检索，叠加，合并等操作且易于检索，叠加，合并等操作，这种编码应用广泛。，这种编码应用广泛。2、行程编码、行程编码352022-5-4栅格数据存储的压缩编码栅格数据存储的压缩编码3、块式编码、块式编码采用采用方形区域方形区域作为记录单元，每个记录单元包括相邻的若干栅格作为记录单元，每个记录单元包括相邻的若干栅格。数据对组成数据对组成：（初始行、列，半径，属性值）：（初始行、列，半径，属性值）特点特点： 具有具有可变分辨率可变分辨率，即当属性变化小时图块大，即当属性变化小时图块大，对于大块图斑记录单元大，分辨率低，压缩比高。对

28、于大块图斑记录单元大，分辨率低，压缩比高。 小块图斑记录单元小，分辨率高，压缩比低小块图斑记录单元小，分辨率高，压缩比低所以，与行程编码类似，随图形复杂程度的提高所以，与行程编码类似，随图形复杂程度的提高而降低分辩率。而降低分辩率。依次扫描，编过的不重复。依次扫描，编过的不重复。如：如：（1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7)1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7) 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

29、8 8 7 75 0 0 8 8 8 8 7 86 0 0 0 8 8 8 8 87 0 0 0 0 8 8 8 88 0 0 0 0 0 8 8 8362022-5-4块式编码示例块式编码示例0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3（1 1，1 1，1 1，0 0），（），（1 1，2 2，2 2，2 2），），（1 1，4 4，1 1，5 5），（），（1 1，5 5，1 1，5 5），），（

30、1 1，6 6，2 2，5 5），（），（1 1，8 8，1 1，5 5）；）；（2 2，1 1，1 1，2 2），（），（2 2，4 4，1 1，2 2），），（2 2，5 5，1 1，2 2），（），（2 2，8 8，1 1，5 5）；）；（3 3，3 3，1 1，2 2），（），（3 3，4 4，1 1，2 2），），（3 3，5 5，2 2，3 3），（），（3 3，7 7，2 2，5 5）；）；（4 4，1 1，2 2，0 0），（），（4 4，3 3，1 1，2 2），），（4 4，4 4，1 1，3 3）；（）；（5 5，3 3，1 1，3 3），），（5 5，4 4，2 2，3

31、 3），（），（5 5，6 6，1 1，3 3），），（5 5，7 7，1 1，5 5），（），（5 5，8 8，1 1，3 3）；）；（6 6，1 1，3 3，0 0），（），（6 6，6 6，3 3，3 3）；）；（7 7，4 4，1 1，0 0），（），（7 7，5 5，1 1，3 3）；）；（8 8，4 4，1 1，0 0），（），（8 8，5 5，1 1，0 0）。）。372022-5-4栅格数据存储的压缩编码栅格数据存储的压缩编码返回返回1、 基本思想基本思想：将将2 2n n2 2n n象元组成的图像象元组成的图像( (不足的用背景补上不足的用背景补上) ) 按四个象限进行递归分

32、割，按四个象限进行递归分割，并判断属性是否单一，并判断属性是否单一， 单一：不分。单一：不分。 不单一：递归分割。不单一：递归分割。最后得到一颗四分叉的倒向树。最后得到一颗四分叉的倒向树。2 2、 四叉树的树形表示四叉树的树形表示： 用一倒立树表示这种分割和分割结果。用一倒立树表示这种分割和分割结果。根根：整个区域：整个区域高高：深度、分几级，几次分割：深度、分几级，几次分割叶叶：不能再分割的块：不能再分割的块树叉树叉：还需分割的块：还需分割的块 每个树叉均有每个树叉均有4 4个分叉，叫四叉树。个分叉，叫四叉树。四叉树四叉树： 一种一种可变分率可变分率的的非均匀网格非均匀网格系统。系统。是最有

33、效的栅格数据压缩编码方法之一是最有效的栅格数据压缩编码方法之一 AAAAABBBAABBAABB0123382022-5-4栅格数据存储的压缩编码栅格数据存储的压缩编码3、 编码方法1 1）常规四叉树）常规四叉树 记录这棵树的叶结点外，中记录这棵树的叶结点外，中间结点，结点之间的联系用指间结点，结点之间的联系用指针联系，针联系，每个结点需要每个结点需要6 6个变量：个变量：父结点指针、四个子结点的指父结点指针、四个子结点的指针和本结点的属性值针和本结点的属性值。指针不仅指针不仅增加了数据的存储量增加了数据的存储量，还增加了操作的，还增加了操作的复杂性复杂性：如层次数（分割次数）由：如层次数（分

34、割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。所以，逐步推算下来。所以，常规四叉树并不广泛用于存储数据常规四叉树并不广泛用于存储数据，其价值在于建立索引文，其价值在于建立索引文件，进行数据检索。件，进行数据检索。392022-5-4四叉树编码示例四叉树编码示例402022-5-4四叉树编码示例四叉树编码示例0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3

35、3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3 1112131415161718192021222324252627282930313233363738393435400 0 00 3 3 3 0 3 3 33 3 5 3 0 0 2 2 2 3 2 2 2 2 0 22 2 2 5 2 5 5 53 33 5 5西南东南西北东北 412022-5-4n四叉树四叉树( (也称四分树也称四分树) )数据结构常常先把地数据结构常常先把地图看成是一个正方形的单元如图所示（这图看成是一个正方形的单元如图所示（这是个简单的例子，在实际使用中，一幅地是个简单的例子，在实际使用中，一

36、幅地图上总有很多多边形图上总有很多多边形 ）：）：如果该单元内有不同性质的多边形，则将如果该单元内有不同性质的多边形，则将单元分成四个大小相同的二级单元，然后单元分成四个大小相同的二级单元，然后再分别判断这四个二级单元中是否还有不再分别判断这四个二级单元中是否还有不同性质的多边形，若其中某个二级单元中同性质的多边形，若其中某个二级单元中有不同性质的多边形，则再划分成四个大有不同性质的多边形，则再划分成四个大小相同的三级单元。这种逐级小相同的三级单元。这种逐级一分为四一分为四的的方法，一直分到预定的最高分辨率为止。方法，一直分到预定的最高分辨率为止。 422022-5-4四叉树(也称四分树)数据

37、结构常常先把地图看成是一个正方形的单元如图所示（这是个简单的例子，在实际使用中，一幅地图上总有很多多边形 ）： 如果该单元内有不同性如果该单元内有不同性质的多边形，则将单元分成质的多边形，则将单元分成四个大小相同的二级单元，四个大小相同的二级单元，然后再分别判断这四个二级然后再分别判断这四个二级单元中是否还有不同性质的单元中是否还有不同性质的多边形，若其中某个二级单多边形，若其中某个二级单元中有不同性质的多边形，元中有不同性质的多边形，则再划分成四个大小相同的则再划分成四个大小相同的三级单元。这种逐级一分为三级单元。这种逐级一分为四的方法，一直分到预定的四的方法，一直分到预定的最高分辨率为止。

38、最高分辨率为止。 432022-5-4442022-5-4编码方式比较编码方式比较n直接栅格编码：简单直观，是压缩编码方法的逻直接栅格编码：简单直观，是压缩编码方法的逻辑原型（栅格文件）；辑原型（栅格文件）；n链码：压缩效率较高，已接近矢量结构，对边界链码：压缩效率较高，已接近矢量结构，对边界的运算比较方便，但不具有区域性质，区域运算的运算比较方便，但不具有区域性质，区域运算较难；较难；n游程长度编码：在很大程度上压缩数据，又最大游程长度编码：在很大程度上压缩数据，又最大限度的保留了原始栅格结构，编码解码十分容易，限度的保留了原始栅格结构，编码解码十分容易，十分适合于微机地理信息系统采用；十分

39、适合于微机地理信息系统采用；n块码和四叉树编码：具有区域性质，又具有可变块码和四叉树编码：具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图象运算，效率较高，是很有直接进行大量图形图象运算，效率较高，是很有前途的编码方法。前途的编码方法。452022-5-42.2 矢量数据结构矢量数据结构n矢量数据结构是通过记录坐标的方式，尽可能精确地表示点、线、面等地理实体。其坐标空间假定为连续空间，允许任意位置、长度和面积的精确定义，事实上，其精度仅受数字化设备的精度和数值记录字长的限制，在一般情况下，比栅格数据结构精度高得多。4

40、62022-5-4矢量数据结构编码的基本内容矢量数据结构通过记录空间对象的坐标及空间关系来表达空间对象的位置。q点：空间的一个坐标点；q线：多个点组成的弧段；q面：多个弧段组成的封闭多边形；472022-5-4矢量数据结构编码的基本内容标识码标识码属性码属性码空间对象编码唯一连接空间和属性数据数据库独立编码点: ( x ,y )线: ( x1 , y1 ) , (x2 , y2 ) , , ( xn , yn )面: ( x1 , y1 ) , (x2 , y2 ) , , ( x1 , y1 )点位字典点: 点号文件线: 点号串面: 点号串点号XY1112223344n5566存储方法存储方

41、法482022-5-42.2 矢量数据结构矢量数据结构492022-5-42.2 矢量数据结构矢量数据结构n一、矢量数据结构编码的基本内容n1、点实体点实体点实体惟一标识符惟一标识符类型类型简单点简单点文字说明文字说明节点节点序列号序列号（x,y）坐标）坐标有关的属性有关的属性如果是简单点（符号）如果是简单点（符号）比例尺比例尺方向方向如果是文字说明（字符）如果是文字说明（字符）大小大小方向方向字体字体字型字型排列排列如果是节点（符号）如果是节点（符号）到线状目标的指针到线状目标的指针与线相交的角度与线相交的角度其他有关属性其他有关属性502022-5-42.2 矢量数据结构矢量数据结构n一、

42、矢量数据结构编码的基本内容n2、线实体线实体线实体惟一标识码惟一标识码线标识码线标识码起始点起始点终止点终止点坐标对序列坐标对序列显示信息显示信息非几何属性非几何属性对于同一条线，坐标序列对越多，则越逼近原始曲线对于同一条线，坐标序列对越多，则越逼近原始曲线512022-5-42.2 矢量数据结构矢量数据结构n一、矢量数据结构编码的基本内容n3、面实体面实体面实体惟一标识码惟一标识码面标识码面标识码点数点数坐标对序列坐标对序列拓扑特征拓扑特征显示信息显示信息非几何属性非几何属性522022-5-4拓扑关系拓扑关系 拓扑关系是明确定义空间结构关系的拓扑关系是明确定义空间结构关系的一种数学方法；在

43、一种数学方法；在GISGIS中，用于空间数据的中，用于空间数据的组织、分析和应用。组织、分析和应用。 在在GISGIS中，为了真实反映地物，不仅包中，为了真实反映地物，不仅包括实体的大小、形状及属性，而且要反映括实体的大小、形状及属性，而且要反映出实体之间的相互关系。出实体之间的相互关系。 例如：自然与行政的分区，各种空间例如：自然与行政的分区，各种空间类型的分布及交通网等，都存在结点、弧类型的分布及交通网等，都存在结点、弧段和多边形之间的拓扑关系。段和多边形之间的拓扑关系。 532022-5-42.2 矢量数据结构矢量数据结构n拓扑关系： 指网结构元素节点、弧段、面域之间的空间关系（1）拓扑

44、邻接：存在于空间图形的同类元素之间的拓扑关系结点邻接关系结点邻接关系N1/N4，N1/N2，；多边形邻接关系多边形邻接关系P1/P3，P2/P3， 542022-5-42.2 矢量数据结构矢量数据结构n（2）拓扑关联：n 指存在于空间图形的不同元素之间的拓扑关系 结点与弧段的关联关系结点与弧段的关联关系N1/C1、C3、C6；多边形与弧段的关联关系多边形与弧段的关联关系P1/C1、C5、C6。 552022-5-42.2 矢量数据结构矢量数据结构n（3）拓扑包含：面与其他拓扑元素之间的关系。如果点、线、面在该面内，则称被该面包含。P1包含包含P2,P3和和P4562022-5-42.2 矢量数

45、据结构矢量数据结构n（4）拓扑连通：拓扑元素之间的通达关系，如点连通，面的连通。n（5）层次关系：相同拓扑元素之间的等级关系。n欧拉公式： L+2=A+P572022-5-4拓扑关系的表示拓扑关系的表示n面链关系：n链结点关系：n结点链关系：n链面关系：面构成面的链链链两端点的结点结点通过该结点的链链左面右面582022-5-4592022-5-4602022-5-4拓扑结构的优缺点拓扑结构的优缺点n和简单矢量结构相比，拓扑型空间数据结和简单矢量结构相比，拓扑型空间数据结构的主要优点有四条：构的主要优点有四条：n(1)描述点、线、面的空间关系不完全依赖描述点、线、面的空间关系不完全依赖于具体坐

46、标位置。于具体坐标位置。n(2)用拓扑表所表达的空间关系信息丰富、用拓扑表所表达的空间关系信息丰富、简洁，若采用其他办法会出现大量的重复简洁，若采用其他办法会出现大量的重复数据数据(冗余冗余)。n(3)便于作多边形和多边形的叠合。便于作多边形和多边形的叠合。n(4)便于检查数据输入过程中的错误。便于检查数据输入过程中的错误。612022-5-4拓扑型空间数据结构的主要缺点有两条：拓扑型空间数据结构的主要缺点有两条：(1)(1)拓扑关系的建立比较复杂。拓扑关系的建立比较复杂。(2)(2)数据结构本身比较复杂。数据结构本身比较复杂。622022-5-4拓扑关系的意义 显然，含有拓扑关系的空间数据有

47、利于显然，含有拓扑关系的空间数据有利于GIS的的拓扑查询和空间分析。拓扑查询和空间分析。ARCINFO是典型的以是典型的以拓扑型数据结构组织空间数据的拓扑型数据结构组织空间数据的GIS软件，这软件，这也是为什么也是为什么ARCINFO具有强大空间分析功能具有强大空间分析功能的原因。的原因。 不需要利用坐标或距离，可以确定空间实体的位不需要利用坐标或距离，可以确定空间实体的位置关系置关系 利用拓扑关系便于空间要素的查询利用拓扑关系便于空间要素的查询 根据拓扑关系可以重建地理实体，例如利用弧根据拓扑关系可以重建地理实体，例如利用弧段构建多边形，最佳路径的选择的等。段构建多边形，最佳路径的选择的等。

48、632022-5-4空间关系n度量关系：空间对象之间的距离关系，一般度量关系：空间对象之间的距离关系，一般用欧式距离表示用欧式距离表示n顺序关系：空间实体在空间上的的排列次序顺序关系：空间实体在空间上的的排列次序n拓扑关系：拓扑变换下保持不变的关系拓扑关系：拓扑变换下保持不变的关系642022-5-4点、线、面之间的空间关系拓扑属性拓扑属性一个点在一个弧段的端点一个点在一个弧段的端点一个弧段是一个简单弧段一个弧段是一个简单弧段（自身不相交）（自身不相交）一个点在一个区域的边界上一个点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的内部一个点在一个区域的外部一个点在一个区域的外部一个点

49、在一个环的内部一个点在一个环的内部一个面是一个简单面一个面是一个简单面（面上没有岛）（面上没有岛）一个面的连接性一个面的连接性（给定面上任意两点，从一点可以完（给定面上任意两点，从一点可以完全在面的内部沿任意路径走向另一点）全在面的内部沿任意路径走向另一点）非拓扑属性非拓扑属性两点之间的距离两点之间的距离一个点指向另一个点的方向一个点指向另一个点的方向弧段的长度弧段的长度一个区域的周长一个区域的周长一个区域的面积一个区域的面积652022-5-4662022-5-4空间关系的应用点点点点点点线线点点面面住宅住宅学校学校海岸线海岸线码头码头肺癌病例肺癌病例区域区域学校和住宅接近吗？学校和住宅接近

50、吗？码头在海岸线上吗？码头在海岸线上吗？肺癌病在区内分布肺癌病在区内分布672022-5-4空间关系的应用线线点点线线线线线线面面镇镇乘车线路乘车线路河流河流小路小路这条线路过镇上吗？这条线路过镇上吗？小路穿过河流吗？小路穿过河流吗？河流在区域内吗？河流在区域内吗？682022-5-4空间关系的应用面面点点面面线线面面面面该邮政区包括学校吗？该邮政区包括学校吗？该区域包括铁路吗？该区域包括铁路吗？区域彼此影响吗？区域彼此影响吗？区域重叠吗？区域重叠吗？692022-5-4矢量数据结构矢量数据结构新山水庫10821816589111道道2道道A1道路河流地質植被702022-5-42.2 矢量数

51、据结构矢量数据结构n3、几种矢量数据结构n（1）实体式数据结构（面条结构）712022-5-4只记录空间对象的位置坐标和属性信息，不记录拓扑关系。0存储：q独立存储：空间对象位置直接跟随空间对象；q点位字典：点坐标独立存储，线、面由点号组成0特征l无拓扑关系，主要用于显示、输出及一般查询l公共边重复存储，存在数据冗余，难以保证数据独立性和一致性l多边形分解和合并不易进行，邻域处理较复杂；l处理嵌套多边形比较麻烦0适用范围：制图及一般查询，不适合复杂的空间分析722022-5-412345678910111213141516171819202122232425262728293031732022

52、-5-4实体式数据结构实体式数据结构 优缺点优缺点实体式数据结构实体式数据结构简单，易于实现以多边形为单位的运算和显示。这种方法的缺点是： 1、 多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形； 2、每个多边形自成体系而缺少邻域处理，如消除两个多边形之间的共同边界； 3、岛只作为一个单个的图形建造，没有与外包多边形的联系；4、不易检查拓扑错误，这种方法可用于简单的粗精度制图系统中。 742022-5-42.2 矢量数据结构矢量数据结构n3、几种矢量数据结构（2）树状索引编码法 该法采用树状索引以减少数据冗余并间接增加邻域信息，方法是对所有边界点进行数字化，将坐标对以顺序方式存

53、储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。 752022-5-4树状索引编码法树状索引编码法762022-5-4树状索引编码法树状索引编码法772022-5-42.2 矢量数据结构矢量数据结构（3）双重独立地图编码n简称DIME结构（Dual Independent Map Encoding）。它是由美国人口调查局建立起来的为人口调查目的而设计的一种拓扑编码方法，是一种把几何量度信息（直角坐标）与拓扑逻辑信息结合起来的系统。DIME文件的基本元素是连接两个端点（结点）的一条线段两个端点（结点）的一条线段（街段）、线段始结点和终结点标识符、伴有这两个结点的（街段）

54、、线段始结点和终结点标识符、伴有这两个结点的坐标及线段两侧的区域代码（左区号和右区号）坐标及线段两侧的区域代码（左区号和右区号）。根据结点标识符和结点坐标建立结点坐标文件结点坐标文件。根据结点、线段、多边形间的拓扑关系建立拓扑结构文件拓扑结构文件。在这种结构中，线段通常被认为是直线型的，复杂的曲线由一系列逼近曲线的直线段来表示。结点与结点或者面域与面域之间为邻接关系邻接关系，而结点与线段或面域与线段之间为关联关系。关联关系。 782022-5-4双重独立地图编码双重独立地图编码拓扑结构文件节点坐标文件792022-5-4802022-5-42.2 矢量数据结构矢量数据结构n4、链状双重独立式数

55、据结构n链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。812022-5-4链状双重独立式数据结构链状双重独立式数据结构 在链状双重独立数据结构中，主要有四个文件：多边多边形文件、弧段文件、弧段坐标文件、结点文件形文件、弧段文件、弧段坐标文件、结点文件。 多边形文件主要由多边形记录组成，包括多边形号、包括多边形号、组成多边形的弧段号组成多边形的弧段号以及周长、面积、中心点坐标及有关“洞”的信息等，多边形文件也可以通过软件自动检索各有关弧段生成，并同

56、时计算出多边形的周长和面积以及中心点的坐标，当多边形中含 有“洞”时则此“洞”的面积为负，并在总面积中减去，其组成的弧段号前也冠以负号； 弧段文件主要有弧记录组成，存储弧段的起止结点号和弧段左右多边形号； 822022-5-4链状双重独立式数据结构链状双重独立式数据结构 弧段坐标文件由一系列点的位置坐标组成，一般从数字化过程获取，数字化的顺序确定了这条链段的方向。结点文件由结点记录组成，存储每个结点的结点号、结点坐标及与该结点连接的弧段。 结点文件一般通过软件自动生成，因为在数字化的过程中，由于数字化操作的误差，各弧段在同一结点处的坐标不可能完全一致，需要进行匹配处理。当其偏差在允许范围内时，可取同名结点的坐标平均值。如果偏差过大，则弧段需要重新数字化。832022-5-412345678910111213141516171819202122232425262728293031842022-5-412345678910111213141516171819202122232425262728293031852022-5-4123456789101112131415161718192021