地理信息系统原理及方法 - Chapter 1 空间数据结构

阅读量：3950 次

发布时间：2019-05-24

本文共 19119 字，大约阅读时间需要 63 分钟。

1 什么叫信息、数据？信息和数据有何区别？信息有何特性？

信息：客观事物的存在及演变情况的反映。

数据：输入到计算机并能成为计算机进行处理的一切现象，如数字、文本、符号、影像等，在计算机环境中，数据是描述实体或对象的唯一工具。

区别：数据是用以载荷信息的物理符号，没有任何实际意义，只是一种数学符号的集合，只有对其加上某种特定的含义，它才代表某一实体或现象，这时数据才变成信息。

信息的特性：客观性、实用性、传输性、共享性。

2 什么是空间数据、地图？

空间数据：采用编程技术，对空间物体以点、线、面的形式进行特征描述和关系建立的数据集。

地图：表达客观事物的地理分布及其相互联系的空间模型，是反应地理实体的图形，是对地理实体的简化和再现。

3 空间数据有几种类型？举例说明

空间数据有三种类型：点、线、面。

例如，地图上的点可以是矿点、采样点、高程点、地物点和城镇等，线可以是地质界线、铁路、公路、河流等，面可以是土壤类型、水体、岩石类型等。

4 什么是空间认知三层模型？

GIS 空间数据模型（空间认知三层模型）由概念数据模型、逻辑数据模型和物理数据模型三个不同的层次组成。

空间认知三层模型

概念数据模型：（语义数据模型）是由于不同人所关心的问题、研究的对象、期望的结果等方面存在着差异，对同一客观现象的抽象和描述会形成不同的用户视图，称为外模式。概念数据模型是考虑用户需求的共性，用统一的语言描述、综合、集成的用户视图，主要包括有矢量数据模型、栅格数据模型和矢量-栅格一体化数据模型。

逻辑数据模型：将概念数据模型所确定的空间数据库内容(空间实体和空间关系)，具体地表达为记录，主要包括有层次模型（反应隶属关系）、网络模型（反应读哦对多关系）和关系模型（二维表表示关系）。

物理数据模型：要完成物理表示组织、空间数据的存取方法和数据库总体存储结构等。

5 什么是空间实体？有几种基本空间实体类型？

空间实体：在空间数据中不可再分的最小单元现象。

基本的空间试题类型：4 种，point、line、surface、solid(体)

6 什么是网络要素？简述网络要素有几种类型？

网络要素：参与几何网络中的要素，具有保护连通性并自动更新网络元素的行为。

网络要素的 4 种类型：网络简单边要素，网络简单点要素、网络复杂边要素、网络复杂点要素。
- 网络简单边要素：网络简单边要素类对应于简单要素模型中的简单线要素类，而且其简单线要素不包含多线要素类型的简单线要素。简单边要素和边线元素是一对一的对应关系。
- 网络简单点要素：网络简单点要素类对应于简单要素模型中的简单点要素类，而简单点要素不包含多点要素类型的简单点要素。简单点要素和结点元素是一对一的对应关系。
- 网络复杂边要素：网络复杂边要素类对应于简单要素模型中的简单线要素类，而且其简单线要素不包含多线要素类型的简单线要素。网络复杂边要素允许沿着边要素的线性方向放置多个简单点要素，将一个复杂边与多个边线元素相对应，即一对多的对应关系。例如，在模拟一个城市交通网时，一个城市的主干道，可能被一些街道分割成多段，在几何网络中，城市的主干道最好用一个边要素来表示，而在逻辑网络中，就需要将主干道拆分成多个边线元素。
- 网络复杂点要素：网络复杂点要素类对应于简单要素模型中的简单点要素类，而且其简单点要素不包含多点要素类型的简单点要素。复杂点要素没有生成对应的网络元素，所以复杂点要素不参与任何网络分析。网络复杂点要素与其所属网络中的其他网络简单点要素、网络简单边要素、网络复杂边要素的辖属关系通过关系类管理实现。一个复杂点要素类对应一个关系类，网络复杂点要素类与其关系类共生共灭。网络复杂点要素和网络简单点要素、网络简单边要素、网络复杂边要素为一对多的一般对应关系；网络简单点要素、网络简单边要素、网络复杂边要素可以分别隶属于不同网络复杂点要素类中的一个网络复杂点要素。复杂点要素之间没有任何辖属关系。

7 简述什么是网络权？

网络权：指从某个结点元素出发然后经过某个边线元素到达某个结点元素或从某个边线元素出发经过某个结点元素到达另外某个边线元素所需要克服的阻碍。
- 网络权正值表示阻碍度，负值表示不连通。
- 一个几何网络只有一个默认网络权，但可以有多个绑定字段网络权。
- 根据网络权数据类型不同，可以分为 5 种：short 型、long 型、float 型、double 型、byte 型，默认网络权的数据类型为 double 型。
- 在几何网络中可以有多个网络权，分为两种，一种是可以直接指定网络元素的网络权值，一个几何网络只有一个默认网络权；另一种是用户通过修改网络要素的网络权绑定字段的属性值去改变网络元素的网络权值，称为绑定字段网络权，一个几何网络可以用多个绑定字段。根据网络权字段属性值拆分策略不同，可以分为比例网络权和绝对网络权两种类型。

8 简述什么是网络需求？

网络需求：指从某个结点元素出发经过某个边线元素到达某个结点元素时对资源的消耗或对资源的补给。
- 网络需求正值表示资源消耗，负值表示资源补给。
- 一个几何网络只有一个默认网络需求，并且也只有一个绑定字段网络需求。
- 默认网络需求和绑定字段网络需求的数据类型为双精度型。

9 简述什么是几何网络？

几何网络：是边要素和点要素组成的集合。
- 几何网络的边要素和点要素相互联系，一条边连接两个点，一个点可以连接大量的边。边要素可以在二维空间中交叉而不相交，如立交桥。几何网络中的要素表示网络地理实体，如道路、车站、航线等。
- 几何网络主要包括：网络要素的几何信息和属性信息；网络要素类信息；网络权信息；网络权字段绑定信息；网络需求字段绑定信息；使能状态字段绑定信息；指示方向字段绑定信息；连接规则。

10 简述什么是逻辑网络？

逻辑网络：是由边和结点组成的纯粹的网络元素集合，是一种数据表组织（与几何网络对应），一种连接关系（存储边线和交点），以及一些附加信息（用于网络分析）。
- 网络元素：当生成一个几何网络后，系统将自动产生和维护一个逻辑网络。一般而言，网络分析功能只涉及逻辑网络。逻辑网络中的边和结点没有几何信息，所以它们被称为网络元素。逻辑网络是网络元素的集合，是由结点元素和边线元素相连构成的系统。网络元素没有几何特征，因此称为元素，区别于要素。
- 逻辑网络包括：逻辑网络属性信息；连通信息；使能状态信息；权值信息；默认网络权值信息；网络需求信息；默认网络需求信息；指示方向信息和流向信息。
一个几何网络总对应一个逻辑网络，几何网络的要素和逻辑网络的元素是一对一或者一对多的关联关系。逻辑网络依附于几何网络，当编辑几何网络的要素时，相应的逻辑网络元素会自动更新。逻辑网络中的元素没有空间特性，即没有坐标值。逻辑网络存储网络的连通信息，是网络分析的基础。

11 简述逻辑网络由哪些网络元素组成？

逻辑网络的网络元素组成：5 个，边线元素、结点元素、中心元素、站点元素及沿线元素组成。

边线元素：即边线元素的网络流向，若网络类型为设备网，其含义是作为资源沿线的边线元素的资源分配方向；若网络类型为交通网，其含义是网络分析后边线元素的网络流向。

结点元素：逻辑网络的基本网络元素之一。

中心元素：担任资源中心的结点元素称中心元素。

站点元素：网络分析资源分配中担任资源站点的结点元素称站点元素。

沿线元素：网络分析资源分配中担任资源沿线的边线元素称沿线元素。

12 GIS中的有效性规则主要有几种类型？

5种，属性规则、空间规则、拓扑规则、关系规则和连接规则。

属性规则：用于约定某个字段的缺省值，限定取值范围，设置合并和拆分策略。属性规则通过“定义域”来表达，取值范围分连续型和离散型，相应地把定义域分为范围域和编码域。

空间规则：作用于要素类或要素类之间，用于限定要素在某个空间参照系中的相互关系。空间规则如：要素类中每条弧段只能作为两个多边形的边界；要素类中多边形之间不能重叠；要素类中多边形之间不能有缝隙；“城镇”要素必须落在“行政区”要素内部；不能有悬挂线；线不能自相交； “阀门”必须与“水管”的端点重合；

关系规则：随关系的产生而产生，用于限定对象之间关系映射的数目。例如：原始类和目的类之间建立了N－M的关系，则通过关系规则可以限定关系的原始对象数是1－3，目的对象数是*－5，即原始类中的每个对象与目的类中至少1个、最多3个对象建立关系；而目的类中的对象可以和原始对象没关系，但最多只能与5个原始对象有关系。

连接规则：主要使用在几何网络中，用以约束可能和其它要素相连的网络要素的类型，以及可能和其他任何特殊类型相连的要素的数量。有两种类型的连接规则：边对边连接规则、点对边连接规则。

有效性规则：对象特性的一个特殊表现是某些属性的取值往往存在边界条件，对象之间的关系（包括空间关系）甚至关系本身存在某种约束条件。所有这些限制条件统称为有效性规则

13 什么叫像元、灰度值、栅格数据？

像元：亦称像素点或像元点，是组成数字化影像的最小单元，在GIS中，通常将工作区域的平面表象按一定的行和列的规则划分，最终形成许多网格，每个网格单元就称为一个像元。

灰度值：像元用于表示网格中不同元素各自所代表的实体的属性差异。

网格中每个元素的代码代表了实体的属性或属性的编码，根据所表示实体的表象信息差异，各像元可用不同的"灰度值"来表示。若每个像元规定为 N 比特，则其灰度值范围可在 0～2N−1 之间；
把白—灰色—黑的连续变化量化为 8 比特（bit），则其灰度值范围在 0～255 之间，共256 级；若每个像元只规定 1 比特，则灰度值仅为 0 和 1，这就是所谓的二值图像，0 代表背景，1 代表前景。

栅格数据：栅格数据结构其实就是像元阵列(像元按矩阵形式的集合)。

栅格中的每个像元是栅格数据中最基本的信息存储单元，其坐标位置可以用行号和列号来确定。由于栅格数据是按一定规则排列的，所以表示的实体位置关系是隐含在行号、列号之中的。

实体可分为点实体、线实体和面实体。
点实体在栅格数据中表示为一个像元；线实体则表示为在一定方向上连接成串的相邻像元集合；面实体由聚集在一起的相邻像元集合表示。这种数据结构便于计算机处理面状要素。

图 2-15 栅格数据结构对观测值的影响

注意：用栅格数据表示的地表是不连续的，是量化和近似离散的数据，这意味着地表在一定面积内（像元地面分辨率范围内）地理数据的近似性。

14 举例说明栅格数据层的概念

栅格数据层：在栅格数据结构中，物体的空间位置是通过笛卡尔平面网格中的行号和列号来表示的，而物体的属性是通过像元取值表示，但每个像元在一个网格中只能取值一次，如果同一个像元要表示多重属性的物体就要用到多个笛卡尔平面网格，从而每个笛卡尔平面网格就表示一种属性，这种平面就称为栅格数据层。

地理数据在栅格数据结构中必须分层组织存储，每层构成单一的属性数据层或专题信息层。通常根据不同的使用目的，来确定需要建立哪些层及需要建立哪些描述性属性。

图 2-16 栅格数据的分层与叠加

举例：一个包含有植被、土壤、地形等地理要素的实体，可以将植被组织为一个专题层，土壤组织为一个专题层，地形组织为一个专题层，分别对应于各自的栅格数据层，然后对不同的栅格数据层进行叠加分析而得到分析结论。

15 栅格数据如何以数组的形式进行存储？

二维数组(组合方式)存储：在系统的一个字长中存储多个像素。

例如，在 16 bit/子的系统中，如果按照每个像素 8 bit的数据对待，则可以把相邻两个像素分别存储在上 8 bit和下 8 bit中；如果按照每个像素 4 bit的数据对待，则一个字长可以连续存储 4 个像素的数据；如果按每个像素 1 bit的数据对待，则一个字长可以存储 16 个像素的数据。

二维数据(比特面方式)存储：把数据存储到按 bit 进行存取的二维数组，即比特面中。

例如，对于 n bit的图像，需要有 n 个比特面，在比特面 k 中(k=0,1,…,n-1)，存储的是以二维形式排列的各个像素值的第 k 比特(0 或1，因为bit位的值不是0就是1)的数据。

以 bit 面作为单位进行处理时，其优点是能够在各面间进行高效率的逻辑运算，存储设备利用率高等，但也存在对图像的处理上耗费时间的问题。

图 2-17 组合方式和比特面方式

一维数组存储：如果给栅格数据内的全体像素赋予按照某一顺序排序的一维的连续号码，则能够把栅格数据存储到一维数组中。

其实二维数组存储方式，在系统内部也是以一维数组的方式进行存储的。

也有其他方法，即不存储栅格数据全体，而只是把应该存储的像素的信息，按照一定规则存储到一维数组中。这种方法主要在栅格数据中用来存储图形轮廓线信息等，具体来讲是坐标序列、链码等。

图 2-18 把栅格数据（二维数组）存储到一维数组中

16 栅格数据有哪几种组织方法？各自有何优缺点？

16.1 对栅格数据进行合理组织的前提

基于笛卡尔坐标系的一系列叠层的栅格地图文件已经建立；

每层中的每一个像元在数据库中都是独立单元，即像元、数据值和位置之间存在着一对一的关系。

16.2 对栅格数据进行合理组织的目的

栅格数据有 3 种组织方法，其目的是为了实现：最优数据存取、最少存储空间、最短处理过程。

16.3 组织方法

16.3.1 像元为基础

方法：以像元为基础和记录的序列，将不同层中同一像元上的各属性值表示为一个列数组。

优点：节省许多的存储空间，因为 N 层中实际上只存储了一层的像元坐标。

缺点：全部都存储在一层坐标，没有实现最优的数据存取。

16.3.2 层为基础，像元为序

方法：以层为基础，每层又以像元为序记录它的坐标和属性值，一层记录完后再记录第二层

优点：记录形式简单

缺点：由于每层每个像元是一一记录的，因此需要的存储空间较大，没有实现最少存储空间

16.3.3 层为基础，多边形为序

方法：以层为基础，但每层中以多边形(即制图单元)为序记录多边形的属性值和充满多边形的各像元的坐标。

优点：第一，由于对制图单元中 n 个具有同一属性的像元，只记录了一次属性，因此节省了许多用于存储属性的空间。第二，这种方法实际上是软件中使用的分级结构，这种多像元对应一种属性的多对一的关系，相当于把相同属性的像元排列在一起，使地图分析和制图处理都较为方便。

17 栅格数据如何进行取值？

中心归属法：每个栅格单元的值以网格中心点对应的面域属性值来确定，如图 a。

长度占优法：每个栅格单元的值以网格中线(水平或垂直)的大部分长度所对应的面域的属性值来确定，如图 b。

面积占优法：每个栅格单元的值以在该网格单元中占据最大面积的属性值来确定，如图 c。

重要性法：根据栅格内不同地物的重要性程度，选取特别重要的空间实体决定对应的栅格单元值，如稀有金属矿产区，其所在区域尽管面积很小或不位于中心，也应采取保留的原则，如图 d。

图 2-20 栅格数据取值方法

18 简述栅格数据存储的直接栅格编码方法

直接栅格编码：将栅格数据看作一个数据矩阵，逐行(或逐列)逐个地记录代码，可以每行都从左到右地逐像元记录，也可奇数行从左到右记录，而偶数行从右向左记录，为了特定目的还可采用其他特殊的顺序。

直接栅格编码是最简单、最直观而又非常重要的一种栅格结构编码方法，通常又称这种方法为图像文件或栅格文件。

当每个像元都有唯一一个属性值时，一层内的编码就需要m(行) × n(列)个存储单元，如果一个多边形（或制图单元）内的每个像元都具有相同的属性值，就有可能大大节省栅格数据的存储需要量。

例如影像：

在系统内是一个 4x4 阶的矩阵，但在外部设备上，是按照左上角开始逐行逐列进行存储。上述的直接栅格编码的存储顺序为：
A A A A A B B B A B B B A A A B

栅格结构不论采用直接栅格编码方法还是压缩编码方法，其逻辑原型都是直接编码的网格文件。

19 栅格数据存储的压缩编码方法主要有哪几种？每种方法是如何进行压缩的？

4 种：链式编码、行程编码(游程长度编码)、块式编码、四叉树编码。

19.1 链式编码（弗里曼链码/边界链码）

又称弗里曼链码或边界链码，在多边形中可以表示为：由某一原点开始并按某些基本方向确定的单位矢量链。

优点：链式编码对多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易。

缺点：在叠置运算中，如组合、相交等情况时，很难实施压缩编码，除非还原成栅格结构，而且公共边界需要存储两次，从而产生多余的数据。

图 2-21 栅格地图的简单区域

基本方向可定义为：东=0，南=3，西=2，北=1 等。
如果再确定原点为像元（10, 1），则该多边形边界按顺时针方向的链式编码为：0,1,02,3,02,1,0,3,0,1,03,32,2,33,02,1,05,32,22,3,23,3,23,1,22,1,22,1,22,1,22,13

19.2 行程编码

行程编码 - 方式一：只在各行（或列）数据的代码发生变化时依次记录该代码及相同代码重复的个数，即按"(属性值，重复个数)"的格式编码。

行程编码 - 方式二：逐个记录各行(或列)代码发生变化的位置和相应的代码，即按"(位置，属性值)"格式编码。

行程编码 - 方式三：按行(或列)记录相同代码的始末像元的列号(或行号)和相应的代码，即按"(起位，止位，属性值)"格式编码。

图 2-22 多区域栅格地图

沿行方向使用行程编码(方式一)：

1 行：(3,3),(4,5);2 行：(3,4),(4,4);3 行：(1,1),(3,3),(4,3),(2,1);4 行：(1,2),(3,3),(2,3);5 行：(1,4),(3,1),(2,3);6 行：(1,4),(2,4);7 行：(1,5),(2,3);8 行：(1,5),(2,3);

沿列方向进行行程编码(方式二)：

column 1: (1,3),(3,1);column 2: (1,3),(4,1);column 3: (1,3),(5,1);column 4: (1,4),(2,3),(5,1);column 5: (1,4),(4,3),(6,2),(7,1);column 6: (1,4),(4,2);column 7: (1,4),(4,2);column 8: (1,4),(3,2);

沿行方向使用行程编码(方式三)：

row 1:(1,3,3),(4,8,4);row 2:(1,4,3),(5,8,4);row 3:(1,1,1),(2,4,3),(5,7,4),(8,8,2);row 4:(1,2,1),(3,5,3),(6,8,2);row 5:(1,4,1),(5,5,3),(6,8,2);row 6:(1,4,1),(5,8,2);row 7:(1,5,1),(6,8,2);row 8:(1,5,1),(6,8,2);

19.3 块式编码

将行程编码扩大到二维的情况，把多边形划分成像元组成的正方形，然后对各个正方形进行编码。块式编码数据结构包括 3 类数据：块的原点坐标(块中心或左上角像元的行号和列号)、块的大小(半径)和属性和记录单元的代码组成。

图 2-23 块式编码分解示意图（对）图 2-22 多区域栅格地图（进行说明）

/*格式：(行号,列号,半径,属性)*/(1,1,2,3);(1,3,1,3);(1,4,1,4);(1,5,3,4);(1,8,1,4);(2,3,1,3);(2,4,1,3);(2,8,1,4);(3,1,1,1);(3,2,1,3);(3,3,2,3);(3,8,1,2);(4,1,1,1);(4,2,1,1);(4,5,1,3);(4,6,1,2);(4,7,2,2);(5,1,4,1);(5,5,1,3);(5,6,1,2);(6,5,1,2);(6,6,3,2)/(7,7,3,2);(7,5,1,1);(8,5,1,1);

一个多边形所能包含的正方形越大，多边形的边界越简单，块式编码的效果就越好。行程和块式编码都对大而简单的多边形更有效，而对那些碎部仅比像元大几倍的复杂多边形效果并不好。块式编码即中轴变换的优点是多边形之间求并及求交都方便，探测多边形的延伸特征也较容易。但对某些运算不适应，必须再转换成简单栅格数据形式才能顺利进行。

19.4 四叉树编码

19.4.1 四叉树编码方法存储栅格数据的前提

前提：四叉树对栅格数据的分解、四叉树的结构

图 2-24 四叉树对栅格数据进行分解

分解步骤：将图像区域按 4 个大小相同的象限 4 等分，每个象限又可根据一定规则判断是否继续等分为次一层的 4 个象限，无论分割到哪层象限，只要子象限上仅含一种属性代码或符合既定要求的少数几种属性，则停止继续分割，否则一直分割到单个像元为止。
分解结果：按照象限递归分割的原则，所分图像区域的栅格阵列应为 2n×2n（n 为分割的层数）的形式。

图 2-25 四叉树结构图

根节点和分支：所谓四叉树结构，就是把整个 2n×2n 像元组成的阵列当作树的根结点，树的高度为 n 级（最多为 n 级），每个结点有分别代表南西（SW）、南东（SE）、北西（NW）、北东（NE）4 个象限的 4 个分支。

树叶和树枝：4 个分支中要么是树叶（如①），要么是树枝。树叶不能继续划分，说明该结点代表的子象限具有单一的代码；树枝不止包含一种代码，因而必须继续划分，直到变成树叶为止。

四叉树编码种类：指针四叉树编码和线性四叉树编码

第 1 种，指针四叉树编码。
指针四叉树编码在子结点和父结点之间通过指针建立起整个结构。
指针四叉树编码压缩栅格数据，会在四叉树的每个结点存储 6 个量，4 个子结点指针，1 个父节点和该结点的属性代码。这种方法一般除了要记录叶子结点之外，还要记录中间结点，从而使得内存占用相对较大。

第 2 种，线性四叉树编码。
不使用指针，不用记录中间结点，仅记录叶子结点，并用地址码表示叶子结点的位置。因此，其编码包括叶子结点的地址码和本节点的属性和灰度值，并且地址码隐含了叶结点的位置和深度信息。

19.4.2 基于深度和层次的线性四叉树编码（二进制代码）

该编码方法记录每个终止结点(叶结点)的地址和属性值。

其中，地址共32位，包含两部分，最右边4位记录该叶结点的深度(即处于四叉树的第几层，通过此深度推知子区大小)，左边的28位记录路径，从右边第 5 位开始往左记录从叶结点到根结点的路径，0，1，2，3 分别表示 SW、SE、NW、NE。

图 2-26 基于深度和层次的线性四叉树编码示意图（二进制代码）

第 4 个结点深度为 3，第一层处于 SE 象限，第二层处于 SW 象限，第三层处于 NW 象限

19.4.3 进制地址码

该编码方法从整体开始水平和垂直分隔，每分隔一次，增加 1 位数字。

图 2-27（b）所示为对图 2-27（a）进行分割，由上而下生成四进制 Morton 码

如图 2-27（b）所示为对图 2-27（a）进行第一次分隔后得到 4 个区域（0，1，2，3），即每位均用一个小于 4 的四进制数来表示位置。因此，该码的位数表示分隔的次数。进行第二次分隔后得到“B”的地址编码为“03”。

19.4.4 十进制地址码（十进制 Morton 码）

19.4.4.1 何为 Morton 码？

Morton 码：给出两个数，把它们的二进制位和十进制相等。

例如，给出 3 和 4，有：(0000 0011)₂ = (3)₁₀ 和 (0000 0100)₂=(4)₁₀ ；它们的 Morton 码是：(0000 0010 0101)₂ =(37)₁₀

第一个数的第 i 位对应 Morton 码的第 2*i-1 位，第二个数的第 j 位对应 Morton 码的第 2*j 位。其中，i 和 j 从 1 开始。在一个 n×n 的图像阵列中，每个像元点都相应地给出一个 Morton 码。

图 2-28 8x8 图像阵列的每个像元的 Morton 码

该表中第 7 列 5 行的 Morton 码为 55 ，即行号 7 和列号 5 的二进制数分别为 (0000 0111)₂ 和 (0000 0101)₂
两个二进制数换位后的结果为 (0011 0111)₂ =(55)₁₀ ，从而将行、列表示的二维图像，成功地改用 Morton 码（如，表中）写成一维数据，通过 Morton 码就可知道像元的位置

19.4.4.2 Morton 码的作用步骤

作用：将一幅 2n×2n 的图像压缩成线性四叉树。

步骤：

按 Morton 码把图像读入一维数组；

比较相邻的 4 个像元，一致的合并，只记录第一个像元的 Morton 码；

比较所形成的大块，相同的再合并，直到不能合并为止。

对用上述线性四叉树的编码方法所形成的数据还可进一步用游程长度编码压缩。压缩时只记录第一个像元的 Morton 码。

图 2-30 是图 2-29 所示图像阵列的 Morton 码

该栅格图像的压缩处理过程如下：
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. 将 4 个相邻像元合并，只记录第一个像元的 Morton 码。由于 Morton 码 8, 9, 10, 11 的像元均为 A，故只记录第一个 Morton 码 8 即可，从而达到压缩的目的：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
PS：在解码时，根据 Morton 码可知像元在图像中的位置(左上角)，本 Morton 码和下一个 Morton 码之差即为像元个数。知道了像元的个数和像元的位置就可恢复出原始图像。

19.4.4.3 Morton 码的优缺点

优点：

容易而有效地计算多边形的数量特征；

阵列各部分的分辨率是可变的，边界复杂部分四叉树较高，即分级多，分辨率也高，而不需要表示的许多细节的部分则分级少，分辨率低，因而既可精确地表示图形结构又可减小存储量；

栅格到四叉树及四叉树到简单栅格结构的转换比其他压缩方法容易；

多边形中嵌套异类多边形的表示较方便。

缺点：四叉树编码存在转换的不定性，同一形状和大小的多边形可能得出多种不同的四叉树结构，故不利于形状分析和模式识别。

20 什么叫矢量数据？点、线、面实体数据编码的基本内容是什么？

20.1 矢量数据的概念

有向线段用一系列有序特征点表示，有向线段集合即构成了图形，因此矢量数据就是地图图形的各离散点平面坐标(x, y)的有序集合。

20.2 点、线、面实体数据编码的基本内容

图 2-31 点实体数据结构基本内容

图 2-32 线实体数据结构基本内容

唯一标识码是系统排列序号；线标识码可以标识线的类型；起始点和终止点可以用点号或直接用坐标表示；显示信息是显示时的文本或符号等；与线相连的非几何属性可以直接存储于线文件中，也可单独存储，而由标识码连接查找。

面实体数据结构基本内容
包括多边形的形状、周长、面积，且都是唯一的，并且包括多边形的位置、属性及区域之间的拓扑关系

20.3 点、线、面实体的坐标编码方式

点：用一对(x,y)表示；线：用一组有序 (x,y) 坐标对表示；面：用一组有序但首尾坐标相同的(x,y)坐标表示。

任何点、线、面实体都可以用直角坐标点 x, y 来表示，这里的 x, y 可以对应地面坐标的经纬度，也可以对应数字化时所建立的平面坐标系 x, y 。这些点都是由光滑曲线的隔点采样而来的，同样的曲线长度，取点越多，以后恢复时越接近原来的曲线；反之，取点越少，恢复时就会成为折现。

图 2-33 点、线、面实体的坐标表示(a)和坐标点编码文件(b)

21 举例说明实体式数据结构，它有何缺点？

实体式数据结构包括：点实体数据结构、线实体数据结构、面实体数据结构。

21.1 点实体数据结构

点实体：指包括有单独一对 x,y 坐标定位的一切地理或制图实体，在空间上是不可再分的实体，可以是具体的也可以是抽象的，例如地物点、文本位置点或线段网络的节点等。

21.2 线实体数据结构

线实体：指由两对 x,y 坐标定义的直线元素所组成的各种线性要素，曲线则是由多个直线元素所组成的，x,y 的坐标数量越多，就越逼近曲线。例如，公路、水系、山脊线等线状地物以及符号线和多边形边界等。

21.3 面实体数据结构

面实体：也称为区域，一个区域或一幅地图可以划分成许多多边形，每个多边形由一条或若干条弧段组成，每条弧段由一串有序的 x,y 坐标对组成。例如，行政区、土地类型、植被分布等，也有用等值线描述的，如地形、降雨量等。

21.4 实体式数据结构的缺点

邻接多边形的公共边被数字化和存储两次，结点在数据库中被多次记录。不仅造成数据冗余，而且容易造成数据结构的破坏，引起严重的匹配误差，如狭长多边形即裂隙的产生。

每个多边形自成体系，缺少有关邻域关系的信息。

不能解决"洞"和"岛"之类的多边形嵌套问题，岛只作为单个的图形建造，没有与外包多边形的联系。

难以检查多边形边界的拓扑关系正确与否，例如不完整的多边形(死点)和拓扑学上不能接受的环(奇异多边形)。

22 什么叫拓扑关系？举例说明拓扑关系有哪几种类型。

拓扑关系：指网格结构元素结点、弧段、面域之间的空间关系。

图 2-35 空间几何实体的拓扑关系

拓扑邻接：存在于空间图形的同类元素之间的拓扑关系。例如(a)，结点邻接关系有 N₁/N₄，N₁/N₂ 等，多边形邻接关系有 P₁/P₂，P₂/P₃ 等。
拓扑关联：存在于空间图形的不同类元素之间的拓扑关系。例如(a)，结点与弧段关联关系有 N₁/C₁,C₃,C₆，N₂/C₁,C₂,C₅ 等，多边形与线段的关联关系有 P₁/C₁,C₅,C₆，P₂/C₂,C₄,C₅,C₇ 等。
拓扑包含：存在于空间图形的同类但不同级的元素之间的拓扑关系。例如(b)，P₁ 包含 P₂ 和 P₃ 。

拓扑学：研究图形在连续变形的情况下不变的整体性质。

刚体几何学：在欧几里得几何学中，只允许图形做刚体运动（平移、旋转、反射），在这种运动中，图形上任意两点间的距离保持不变，因此，这里的几何性质是指那些在刚体运动中保持不变的性质，因而欧几里得几何学可称作“刚体几何学”。

弹性几何学：拓扑学中的运动可以称作“弹性运动”，对图形可以任意伸张、扭曲、收缩，但图形中不同的各点仍为不同的点，不可能使不同的两点合并成一点。当且仅当一个图形做弹性运动使其与另一个图形重合，则称这两个图形是“拓扑等价”的（见图 2-34）。

图形的拓扑性质就是那些在弹性运动中保持不变的性质，一个图形的任何弹性运动都丝毫不会改变图形的拓扑性质，所以拓扑学也叫作“弹性几何学”。例如，在地图图形的连续变换中，长度、角度和相对距离等会发生变化，但另一些性质则保持不变，如邻接性、包含性、相交性和空间目标的几何类型（点、线、面特征类型）等，这类在连续变形中保持不变的属性称为拓扑属性，也就是拓扑性质。

23 举例说明拓扑数据结构的表示方式

拓扑数据结构的关键就是对点(结点)、线(弧段或边)、面(多边形)、体(对三维而言)等拓扑要素之间的拓扑关系进行表示。

目前，空间数据的拓扑数据结构的表示没有固定的格式，也还没有形成标准，但其基本原理是相似的。

图 23-1 拓扑关系的基本原理

此处："—"表示边的方向为逆时针，"0"为含洞的弧段。

图 23-2 空间几何实体图形

根据图 23-1 定义的拓扑关系基本原理对图 23-2 的图形进行的拓扑关系描述：表 2-1 表 2-2 表 2-3 表 2-4

24 举例说明索引式数据结构、DIME 数据结构、链状双重独立式数据结构、面条数据结构

索引式数据结构：指根据多边形边界索引文件，来检索多边形边界的坐标数据的一种数据组织形式。

DIME 数据结构：即双重独立地图编码（Dual Independent Map Encoding），一种把几何量度信息(直角坐标)与拓扑逻辑信息结合起来的系统。

最初是由美国人口调查局建立起来的为人口调查而设计的一种拓扑编码方法，也可用于土地利用等多种信息系统的编码和分析。

链状双重独立式数据结构：是 DIME 数据结构的一种改进。
在 DIME 中，一条边只能用直线端点的序号及相邻的面域来表示，而在链式数据结构中，一条边可以由许多点组成，这样在寻找两个多边形之间的公共界线时，只要查询链名就行，与这条界线的长短和复杂程度无关。

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

25 在实际工作中，应如何对矢量和栅格数据结构进行有效选择？

栅格数据结构和矢量数据结构都有一定的局限性，一般来说，大范围小比例的自然资源、环境、农业、林业、地质等区域问题的研究，城市总体规划阶段的战略性布局研究等，使用栅格数据比较合适；城市分区或详细规划、土地管理、公用事业管理等方面的应用，矢量数据结构比较合适。

26 地理数据的显式和隐式表示有何区别？

隐式表示法（矢量表示法）用于存储地理要素的数据量较少，即需要的存储空间少，矢量表示的 x,y 坐标和连接指示字也较少而栅格表示需要的像元较多。

显示表示法（栅格表示法）不如矢量表示法的结果精美，栅格法要达到相同的分辨率，格网要非常小才行，这就需要更多的 x,y 坐标。

矢量法中的连接信息使数据搜索能沿着一定的方向进行，而栅格法则能方便地改变地理事物的形状和大小，因为栅格数据修改只包括清除某些旧值和输入新值两个步骤，而矢量数据的修改除改变坐标值外，还需要重建连接关系(指示字)。

27 三维空间数据模型有哪些？其对应空间数据结构有什么特点？

27.1 三维矢量模型

27.1.1 概念及特点

概念：三维矢量模型是二维中点、线、面矢量模型在三维空间中的推广。它将三维空间中的实体抽象为三维空间中的点、线、面、体这 4 种基本元素，然后以这 4 种基本几何元素的集合来构造更复杂的对象。以起点、终点来限定其边界，以一组型值点来限定其形状；以一个外边界环和若干内边界环来限定其边界，以一组型值曲线来限定其形状；以一组曲面来限定其边界和形状。

特点：矢量模型能精确表达三维的线状实体、面状实体和体状实体的不规则边界，数据存储格式紧凑、数据量小，并能直观地表达空间几何元素间的拓扑关系，空间查询、拓扑查询、邻接性分析、网络分析的能力较强，而且图形输出美观，容易实现几何变换等空间操作，不足之处是操作算法较为复杂，表达体内的不均一性的能力较差，叠加分析实现较为困难，不便于空间索引。

27.1.2 主要模型

27.1.2.1 3D FDS 模型

概念：基于三维矢量图的形式化数据结构（Formal Data Structure，FDS）。

特点
1. 仅考虑空间目标表面的划分和边界表达，没有考虑目标的内部结构，因此只适合于形状规则的简单目标，难以表达地质环境领域中没有规则边界的复杂目标；
2. 没有对空间实体间的拓扑关系进行严格的定义和形式化描述；
3. 显式地存储几何元素间的拓扑关系，使得操作不便。

27.1.2.2 B-Rep 模型

概念：三维边界表示法，通过制定顶点位置、构成边的顶点以及构成面的边来表示三维物体的方法。

例如，一个长方体由 6 个面围成，对应有 6 个环，每个环由 4 条边界定，每条边又由两个端点定义。

特点
1. 详细记录实体的所有几何元素的几何信息及其相互连接关系，以便直接存取构成实体的各个面、面的边界以及各个顶点的定义参数，有利于以面、边、点为基础的各种几何运算和操作；
2. 三位边界模型在表示结构简单的三维物体时十分有效，但对于不规则三维地物很不方便，且效率低下。

27.2 三维体元模型

27.2.1 体元模型的种类

体元模型可以按体元的面数分为四面体（Tetrahedral）、六面体（Hexahedral）、棱柱体（Prismatic）和多面体（Polyhedral）共 4 种类型，也可以根据体元的规整性分为规则体元和非规则体元两个大类。

规则体元：包括 CSG-tree、Voxel、Octree、Needle 和 Regular Block 共 5 种模型。

规则体元通常用于水体、污染和环境问题构模，其中 Voxel、Octree 模型是一种无采样约束的面向场物质（如重力场、磁场）的连续空间的标准分割方法，Needle 和 Regular Block 可用于简单地质构模。

非规则体元：包括 TEN、Pyramid、TP、Geocellular、Irregular Block、Solid、3D-Voronoi 和 GTP 共 8 种模型。

非规则体元均是有采样约束的、基于地质地层界面和地质构造的面向实体的三维模型。

27.2.2 主要模型

27.2.2.1 Octree (八叉树数据结构)

原理：相当于二维栅格数据中的四叉树在三维空间中的推广。该数据结构将所要表示的三维空间 V 按 X、Y、Z 三个方向从中间进行分割，把 V 分割成 8 个立方体；然后根据每个立方体中所含的目标来决定是否对各立方体继续进行八等分的划分，一直划分到每个立方体被一个目标所充满，或没有目标，或其大小已成为预先定义的不可再分的体素为止。

特点：可以非常方便地实现有广泛用途的集合运算（i.e. 可以求两个物体的并、交、差等运算)；由于八叉树的有序性及分层性，因而对显示精度和速度的平衡、隐线和隐面的消除，带来了很大的方便。

图 2-28 在三维空间上划分实体图 2-39 层层划分，便得到八叉树

27.2.2.2 TEN（四面体网格 Tetrahedral Network）

原理：将目标空间用紧密排列但不重叠的不规则四面体形成的格网来表示，其实质是二维TIN（Triangular Irregular Network，不规则三角网）在三维空间中的扩展。

四面体网格数据的组织：四面体格网由点、线、面和体 4 类基本元素组合而成。整个格网的几何变换可以变为每个四面体变换后的组合，这一特性便于许多复杂的空间数据分析。

图 2-41 对图 2-40 的四面体格网中的点、线、面、体进行数据描述

27.3 三维混合数据模型及结构

三维矢量模型优缺点：
基于面模型的构模方法侧重于三维空间实体的表面表示，如地形表面、地质层面等，通过表面表示形成三维目标的空间轮廓，其优点是便于显示和数据更新，不足之处是难以进行空间分析。

三维体元模型优缺点：
基于体模型的构模方法侧重于三维空间实体的边界与内部的整体表示，如地层、矿体、水体、建筑物等，通过对体的描述实现三维目标的空间表示，优点是易于进行空间操作和分析，但存储空间大，计算速度慢。

三维混合数据模型：
混合模型的目的是综合面模型和体模型的优点，以及综合规则体元与非规则体元的优点，取长补短。

27.3.1 TIN-CSG 混合构模

应用：当前城市 3D GIS 和 3D CM 构模的主要方式

TIN 模型：表示地形表面；

CSG 模型：表示城市建筑物。

两种模型的数据是分开存储的。

为了实现 TIN 与 CSG 的集成，在 TIN 模型的形成过程中，将建筑物的地面轮廓作为内部约束，同时把 CSG 模型中建筑物的编号作为 TIN 模型中建筑物的地面轮廓多边形的属性，并且将两种模型集成在一个用户界面中。

这种集成是一种表面上的集成方式，一个目标只由一种模型来表示，然后通过公共边界来连接，因此其操作与显示都是分开进行的。

27.3.2 TIN-Octree 混合构模（Hybrid 构模）

这种模型以 TIN 表达三维空间物体的表面，以 Octree 表达内部结构，用指针建立 TIN 和Octree 之间的联系，其中 TIN 主要用于可视化与拓扑关系表达。这种模型集中了 TIN 和 Octree 的优点，使拓扑关系搜索很有效，而且可以充分利用映射和光线跟踪等可视化技术。缺点是，Octree 模型数据必须随 TIN 数据的变化而改变，否则会引起指针混乱，导致数据维护困难。

27.3.3 Wire Frame - Block 混合构模

这种模型以 Wire Frame 模型来表达目标轮廓、地质或开挖边界，以 Block 模型来填充其内部。为提高边界区域的模拟精度，可按某种规则对 Block 进行细分，如以 Wire Frame 的三角形面与 Block 体的截割角度为准则来确定 Block 的细分次数（每次可沿一个方向或多个方向将尺寸减半）。该模型实用效率不高，即每次开挖或地质边界的变化都需要进一步分割 Block 体，即修改一次模型。

27.3.4 Octree-TEN 混合构模

这个结构中，用八叉树（Octree）进行全局描述，而在八叉树的部分栅格内嵌入不规则四面体（TEN）进行局部描述。这种结构特别适合于表达内部破碎、表面规整的二维对象，但对于表面也不规整的对象则不合适。

考虑将适合于表达实体内部破碎复杂结构的不规则四面体网和适合于表达表面不规整的八叉树层次结构有机结合起来，形成统一的三维集成数据结构。这种结构用八叉树结构表达对象表面及其内部完整部分，并在八叉树的特殊标识结点内嵌入不规则四面体网表达对象内部的破碎部分，整个结构用一棵经过有机集成的八叉树表达。不规则四面体网和三级矢量化八叉树有机结合的统一三维集成数据结构，可用图 2-44、图 2-45 表示。

图 2-44 传统八叉树与 TEN 结合	图 2-45 面八叉树与 TEN 结合

27.3.5 矢量与栅格集成模型

一个三维空间数据模型应具有目标的几何、语义和拓扑描述，具有矢量和栅格数据结构，能够从已有的二维 GIS 获取数据以及三维显示和表示复杂目标的能力。矢量栅格集成的三维空间数据模型，如图 2-46 所示。

图 2-46 矢量栅格集成的三维空间数据模型

在这个模型中，空间目标分为四大类，即点（0D）、线（1D）、面（2D）和体（3D）。
其中，目标的位置信息包含在空间坐标中，形状和大小信息包含在线、面和体中，目标的拓扑信息包含在目标的几何要素和几何要素之间的联系中，而且模型中包含矢量和栅格结构。
模型中包含的各种目标及其数据模型是全面的，对具体的系统用什么样的数据模型可视需要而定。

28 简述四面体格网数据的生成算法

四面体格网数据模型的本质是二维三角形网（Triangulation Irregular Network，TIN）数据结构在三维空间中的扩展。目前，主要有三种生成三角形网的算法，即三角形网生成算法、逐点插入法和分治算法。

28.1 三角网生成算法

28.1.1 基本思想

在数据场中先构建一个四面体，然后以四面体的某个面向外扩展生成新的四面体，直至全部离散点均已连成网为止。

28.1.2 具体步骤

在数据场中选择最近两个点连线，作为第一个三角形的一条边；

选择第 3 个点构成第一个三角形；

选择第 4 个点构成第一个四面体；

i=1，j=1（i 为已构成的四面体个数，j 为正扩展的四面体个数）；

扩展第 j 个四面体，生成新的四面体 0～4 个；

i=i+k（k=0, 1, 2, 4），j=j+1；

若 i≥j 则转向 5. 中寻找第 4 个点；

结束。

28.2 逐点插入法

28.2.1 基本思想

将未处理的点加入到已经存在的四面体格网中，每次插入一个点，然后对四面体格网进行优化。

28.2.2 具体步骤

生成包含所有数据点的立方体（即建立超四面体顶点）；

生成初始四面体格网；

从数据中取出一点 p 加入三角网中；

搜索包含点 p 的四面体，将 p 与此四面体的 4 个点相连，形成 4 个四面体；

用 LOP 算法从里到外优化所有生成的四面体；

LOP 算法（Local Optimization Procedure）：生成四面体格网的优化过程，其思想是运用四面体格网的性质，对由两个公共面的四面体组成的六面体进行判断，如果其中一个四面体的外接球面包含第 5 个顶点，则将这个六面体的公共面交换。

重复步骤 3~5 直至所有点处理完毕。

28.3 分治算法

28.3.1 基本思想

首先将数据排序，即将点集 V 按升序排列使（x_i，y_i，z_i）<（x_i+1，y_i+1，z_i+1），不等式成立的条件是 x_i≤x_i+1 且 y_i≤y_i+1且 z_i<z_i+1，然后递归地分割数据点集，直至子集中只包含 4 个点，从而形成四面体，然后自下而上地逐级合并生成最终的四面体格网。

28.3.2 具体步骤

把点集 V 分为近似相等的两个子集 V_L 和 V_R ；

分别在 V_L 和 V_R 中生成四面体格网-；

用 LOP 算法（局部优化算法）优化所产生的的四面体格网；

合并 V_L 和 V_R 中的两个四面体格网。

在合并 V_L 和 V_R 中两个四面体格网的过程中，在建立第一个四面体，以及逐步扩展四面体时，均是在与已有数据点相连的顶点中寻找。

图 2-43 合并 V_L 和 V_R 的示意图

如图 2-43，在合并 V_L和 V_R 时，先找到第一个三角形△P₁P₂P₃，然后从与 P₁，P₂，P₃ 相连的顶点中找到点 P₄，即生成由 P₁P₂P₃P₄ 这 4 个点所组成的四面体。然后分别从△P₁P₂P₄ 和△P₁P₃P₄ 向外扩展，对于△P₁P₂P₄，是在与点 P₁，P₂，P₄ 相连的点中寻找第 4 个点，而对于△P₁P₃P₄，是在与点 P₁，P₃，P₄ 相连的点中寻找第 4 个点。每找到一个点，必须确认四面体之间无交叉重叠，若出现这种情况，则放弃这个点，认为该三角形不能再扩展。