4 空间数据结构

参考汤国安《地理信息系统教程》第四章空间数据结构，做成思维导图，帮助同学学习地理信息系统教程这一门课程。

空间数据结构

• 概念
  • 空间数据结构是指对空间数据逻辑模型描述的数据组织关系和编排方式的具体实现
  • 对地理信息系统中数据存储，查询检索和应用分析等操作处理的效率有着至关重要的影响
  • 在地理信息系统中，较常用的有三个数据结构和矢量数据结构。除此之外，还有混合数据结构，镶嵌数据结构和多维数据结构
  • 空间数据结构的选择取决于数据的类型性质和使用方式，应根据不同的任务目标，选择最有效和最合适的数据结构
• 矢量数据结构
  • 概念
    • 是指对矢量数据模型进行数据的组织
    • 它通过记录实体坐标及其关系，尽可能精确的表示点线面的等地理实体，坐标空间为连续空间，允许任意位置长度和面积的精确定义。
    • 具有数据精度高，存储空间小等特点，是一种高效的图形数据结构
    • 优缺点
      • 很好地表达地理实体的空间分布特征，数据精度高，数据存储冗余度低
      • 叠合分析较困难
  • 分类（按其是否明确表示地理实体的空间关系）
    • 实体数据结构
      • 内涵
        • 是指构成多边形边界的各个线段，以多边形为单元进行组织
        • 按照这种数据结构边界坐标，数据和多边形单元实体一一对应，各个多边形边界点都单独编码，并记录坐标
      • 优点
        • 编码容易
        • 数字化操作简单
        • 数据编排直观
      • 缺点
        • 相邻多边形的公共边界要数字化两遍，造成数据冗余，可能导致输出的公共边界出现间隙或重叠
        • 缺少多边形邻域信息和图形拓扑关系
        • 岛只作为单个图形，没有建立与外界的联系
      • 只适用于简单的系统，如计算机制图系统
    • 拓扑数据结构
      • 概念
        • 是一种对空间结构关系进行明确定义的数学方法。具有拓扑关系的矢量数据结构就是拓扑数据结构
        • 他们的共同特点是
          • 点是相互独立的，点连成线，线构成面。
          • 每条线始于起始结点，至于终止结点，并与左右多边形相邻接
      • 重要特征
        • 具有拓扑编辑功能
        • 这种拓扑编辑功能不但能够对数字化原始数据进行自动差错编辑，而且可以自动形成封闭的多边形边界，为由各个单独存储的弧段组成的各类多边形及建立空间数据库奠定基础
      • 类型
        • 索引式
          • 概念
            • 采用树状索引，减少数据冗余并间接增加邻域信息
          • 具体方法
            • 对所有边界点进行数字化
            • 将坐标对以顺序方式存储
            • 由点索引与边界线号相联系
            • 以线索引与各多边形相联系
            • 形成树状索引结构
          • 优点
            • 消除边界数据冗余和不一致的问题
            • 在简化过于复杂的边界线或合并多边形时，可不必改造索引表
            • 邻域信息和岛状信息可以通过对多边形文件的线索引处理得到
          • 缺点
            • 实现过程繁琐，因而给邻域函数运算、消除无用边、处理岛状信息以检查拓扑关系等带来一定的困难
            • 两个编码表都要人工方式建立，工作量大，容易出现错误
        • 双重独立编码结构（DIME）
          • 概念
            • 最早由美国人口统计系统采用的一种编码方式
            • 它是以城市街道为编码主体
            • 特点
              • 采用拓扑编码结构，适合城市信息系统
            • 是对图上网状或面状要素的任何一条线段，用顺序的两点定义以及相邻多边形来予以定义
            • 结点与结点 或 多边形与多边形之间为邻接关系
            • 结点与线段 或 多边形与线段 之间为关联关系
          • 优点
            • 有效进行数据存储正确性检查
            • 便于对数据进行更新和检索
            • 达到数据自动编辑的目的
            • 同样利用该结构可以自动形成多边形，并可以检查线文件数据的正确性
            • 尤其适用于城市地籍宗地管理
          • 局限
            • 适用于城市信息系统
        • 链状双重独立编码结构
          • 内涵
            • 对DIME数据结构的一种改进
            • 将若干直线段合为一个弧段，每个弧度可以有许多中间点
            • 也称之为多边形转换器
            • 四个文件
              • 多边形文件
              • 弧段文件
              • 弧段点文件
              • 点坐标文件
  • 网络数据结构
    • 内涵
      • 有一组 相连的边和交汇点 以及 连通性规则组成，用于表示现实世界中的网状线性系统
      • 根据是否记录位置特征
        • 几何网络
          • 强调边和节点的空间位置关系
        • 逻辑网络
          • 强调边与边之间的拓扑关系
• 栅格数据结构
  • 概念
    • 以规则空间阵列表示空间对象的数据结构
    • 阵列的每个栅格单元上的数值表示空间对象的属性特征。即栅格阵列中每个单元的行列号确定位置，属性号表示空间对象的类型等级等特征。每个栅格单元只能存一个值
    • 表示的地表不是连续的，是量化和近似离散的
    • 地理空间被分成相互邻接、规则排列的栅格单元，一个栅格单元对应小块地理范围
    • 特点
      • 属性明显，定位隐含
        • 数据直接记录属性的指针或属性本身
        • 而所在位置则根据横列号转换为相应的坐标给出
        • 也就是说定位是根据数据在数据集中的位置得到的
      • 优点
        • 数据结构简单、数学模拟方便
      • 缺点
        • 数据量大
        • 难以建立实体之间的拓扑关系
        • 通过改变分辨率减少数据量时精度和信息量同时受损
  • 分类
    • 完全栅格数据结构
      • 内涵
        • 也称编码
        • 将栅格看作一个数据矩阵，逐行逐个记录栅格单元的值
        • 可以每行都从左到右，也可以奇数行从左到右而偶数行从右到左，或者采用其他特殊方法
        • 最简单最直观的栅格编码方法
        • 通常这种编码为栅格文件或格网文件
        • 它不采用任何数据压缩数据的处理，因此是最直观最基本的栅格数据组织方式
      • 组织方式
        • 基于像元
          • 以像元为独立存储单元，每一个像元对应一条记录，每条记录内容包括像元坐标及其各层属性值的编码
          • 节省了许多存储坐标的空间，因为各层对应像元的坐标，只需存储一次
        • 基于层
          • 以层为存储基础
          • 层中又以像元为序记录其坐标和对应层的属性值编码
        • 基于面域
          • 也以层作为存储基础
          • 层中再以面域为单元进行记录
          • 记录的内容包括
            • 面域编号
            • 面域对应该层的属性值编码
            • 面域中所有栅格单元坐标
          • 同一属性的多个相邻像元只需记录一次属性值
    • 压缩栅格数据结构
      • 游程编码结构
        • 内涵
          • 游程指相邻同值网格的数量，也称行程编码
          • 不仅是一种栅格数据无损压缩的重要方法，也是一种栅格数据结构
        • 基本思想
          • 对于一幅栅格数据或影像常常有行和列方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。
        • 编码方案
          • 只在各行列发生变化时依次记录该值以及相同值重复的个数
          • 从而实现数据的压缩，并实现数据的组织
          • 经编码后，原始栅格数据阵列转换为（si, li)数据对，si为属性值，li为行程
        • 目的作用
          • 压缩栅格数据量
          • 消除数据间的冗余
      • 四叉树编码结构
        • 基本思想
          • 将一副栅格数据层或图像等分为四部分，逐块检查其格网属性值（或灰度）
          • 如果其个子区的所有格网都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区分割成四个子区
          • 这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止
          • 四个象限，左上右上左下右下，其结果是一棵倒立的树
        • 特点
          • 优点
            • 压缩效率高
            • 压缩和解压缩比较方便，阵列各部分都分辨率可不同
            • 既可精确地表示图形结构，又可以减少存储量，易于进行大部分图形操作和运算
          • 缺点
            • 不利于形状分析、模式识别
            • 即具有图形编码的不定性，如同一形状和大小的多变形可得出完全不同的四叉树结构
        • 生成方法
          • 自上而下
            • 检测全区域
            • 速度比较慢
          • 自下而上
            • 莫顿码
        • 储存方法
          • 常规四叉树
            • 自下而上
            • 优点
              • 简便灵活
              • 数据索引
              • 图幅索引
          • 线性四叉树
            • 每个节点只储存3个数据
            • 优点
              • 压缩效率高
              • 易于图形操作和运算
            • 缺点
              • 不利于形状分析、模式识别
              • 具有不定性
      • 二维行程编码结构
        • 内涵
          • 前后值相同
          • 大小不一的叶结点
        • 优点
          • 更节省空间
          • 相互转换也非常容易和快速
    • 链码数据结构
      • 内涵
        • 弗里曼
        • 8个基本方向
      • 编码过程
        • 起始点从上到下、从左到右
        • 顺时针方向循迹
        • 作用
          • 对区域分析运算比较弱
          • 优点
            • 压缩了栅格数据
            • 有一定运算能力
            • 比较适合储存图形数据
          • 缺点
            • 对边界修改编辑工作很难实施
            • 局部修改改变整体结构
            • 类似矢量结构，但不具有区域性质，对区域分析比较困难
    • 影像与切片金字塔数据结构
      • 内涵
        • 分辨率由粗到细、数据量由小到大金字塔结构
      • 应用
        • 图像编码
        • 渐进式图像传输
        • 有损压缩方式
        • 提升显示效率
        • 电子地图
        • GIS
          • 栅格数据的有损压缩
          • 互联网地图组织地图切片数据的主要方式
• 矢量与栅格数据结构融合转换
  • 栅格与矢量数据结构比较
    • 
    • 栅格数据
      • 优点
        • 属性明显、位置隐含
        • 易于实现，且操作简单，有利于栅格的空间信息模型的分析
        • 可以很快算出结果
      • 缺点
        • 精度不高，数据存储量大，工作效率低
      • 要根据应用项目特点及其精度要求平衡精度和效率之间的关系
      • 栅格共享简单，易于程序设计人员理解
      • 遥感影像本身就是以像元为单位，所以栅格数据易于和遥感数据结合
    • 矢量数据
      • 位置明显、属性隐含
      • 操作复杂，精度高，数据存储量小，输出图形美观和效率高
  • 矢栅一体化数据结构
    • 背景提出
      • 龚健雅
      • 结合其优点
    • 设计思路
      • 面状实体 边界采用矢量数据结构，内部采用栅格数据结构
      • 线状实体 采用矢量数据结构，经过的位置以栅格单元填充
      • 点实体 同时描述其空间坐标以及栅格单元位置
    • 理论基础
      • 多级格网方法
        • 栅格划分为 粗格网、基本格网、细分格网
        • 三个莫顿码表示
          • M0 点或线通过粗格网的莫顿码
          • M1 点或线通过的基本格网的莫顿码
          • M2 点或线通过细分格网的莫顿码
      • 三个基本约定
        • 点状
          • 只有空间位置
          • 无形状和面积
          • 在计算机中仅有一个坐标数据
        • 线状
          • 有形状
          • 无面积
          • 需要一组元子（栅格单元）填满路径的表达
        • 面状
          • 有形状有面积
          • 填满边界限和内部
      • 线性四叉树编码
  • 矢量与栅格数据结构转换
    • 背景需要
      • 具有各自优缺点
      • 需要根据要解决问题的背景及数据存储、分析及建模的需要，选择符合实际的数据结构
    • 矢量转栅格
      • 前期工作
        • 确定栅格像元的大小、像元值分配类型及分配原则
        • 像元的大小决定了输出精度
        • 像元的分配类型和分配原则主要用于多个对象落入同一个像元中时像元的计算方式
        • 常用要素类型
          • 点线面体
      • 点要素转换
        • 赋值
      • 线要素转换
        • 计算经过的栅格数，赋予线属性值
      • 面要素转换（多边形填充）
        • 面域栅格化
        • 多边形边界栅格化
        • 面域属性值填充
          • 内部点扩散
          • 射线法
          • 扫描线法
    • 栅格转矢量
      • 目的
        • 栅格数据分析的结果，通过矢量绘图装置输出
        • 数据压缩的需要，将大量面状栅格数据转为由少量数据表示的多边形数据
        • 将自动扫描仪获取的栅格数据加入矢量形式的数据库
      • 转换情况
        • 遥感影像或已栅格化的分类图
          • 边界提取
          • 处理成近似线画图的二值图像
          • 转换为矢量数据
        • 从原来的线画图扫描得到的栅格图
          • 二值化的线画宽度占据多个栅格
          • 需要细化处理才能矢量化
      • 具体过程
        • 
• 镶嵌数据结构
  • voronoi数据结构
    • 泰森多边形
    • 特点
      • 
    • 文件
      • 样点的序号、样点的坐标及其属性
      • 各样点所对应相邻样点的序号（逆时针方向）
      • 生成的voronoi单元的顶点坐标
      • 单元的顶点组成
  • TIN数据结构
    • 内涵
      • 不规则三角网
      • 样点的位置控制着三角形的顶点
      • 可以采用类似于多边形的矢量拓扑结构
    • 数据组织
      • 直接表示三角形及其邻接关系的数据组织
        • 点文件
          • 每个样点对应一个记录，给出该点的x\y坐标，以及属性值
        • 三角形拓扑文件
          • 组织三角形与样点以及三角形的邻接关系
          • 每个记录依顺时针方向列出三个顶点号及三个相邻的三角形号
          • 其中相邻三角形的顺序按照每个顶点对边给的邻接三角形的顺序排列
        • 能够很好描述三角形及其邻接关系，非常适合于需要面相邻关系的操作和分析
      • 将特征点作为基本的空间对象的数据组织需要两个文件
        • 点文件
        • 相连结点索引号
        • 这种结构适合于需要三角形相连关系的操作，如TIN的线性内插分析
    • 优缺点
      • 
      • 优点
        • 充分利用地貌的特征点、线、面，能够较好地表示复杂地形
        • 根据不同地形，选取合适的采样点数
        • 进行地形分析和绘制立体图也很方便
      • 缺点
        • 数据结构复杂，不方便规范化和管理
        • 难以与矢量和栅格结构数据联合分析
• 多维数据结构
  • 多维数据结构特征
    • 内涵
      • 添加时间维度
      • 三维或更多维
      • 多个维度的任何组合都必须对应一个或多个属性值
    • 表达及范式
    • 表达
  • 多维数据结构
    • 概述
      • 将三维或多维以上的数据模型称为多维数据
      • 常用的三维数据模型
        • 三维数据模型
          • 八叉树数据结构
          • 三维边界表示数据结构
        • 时空数据模型
          • 时空棱柱数据结构
          • 时空立方体数据结构
• 时空一体化数据模型
  • 概念
    • 是一种有效组织和管理时态地理数据
    • 属性、空间和时间语义更完整的地理数据模型
    • 时空数据模型表达了随时间变化的动态结构，用于地理空间数据的时态变化分析
    • 一个合理的时空数据模型必须考虑
      • 节省存储空间
      • 加快存储速度
      • 表现语义时空
  • 分类
    • 时间片快照模型
      • 矢量快照模型
      • 栅格快照模型
    • 底图叠加模型
      • 首先确立空间数据的基本状态，即 底图数据
      • 然后按照适宜的时间间隔记录数据随时间发生的变化
      • 再通过空间叠加操作，利用记录的变化数据来恢复各个时间片的状态数据，每一次叠加表示状态的一次变化
    • 时空合成模型
      • 在底图叠加模型之上提出
      • 每一次独立的叠加转换为一次性的合成叠加
      • 变化的累积形成最小变化单元
      • 最小变化单元构成的图形变化文件和记录历史的属性文件联系在一起，即可较完整表达数据的时空特征