地理信息系统第四讲.pdf

6 4 6 4 6 4 6 4 空间数据索引空间数据索引空间数据索引空间数据索引 空间索引的层次结构空间索引的层次结构 无缝图层无缝图层 工作区索引工作区索引 目标索引目标索引 窗坐标 窗坐标 BSPBSPBSPBSP KDBKDBKDBKDB树 树 R R R R树和树和R R R R 树 树 CELLCELLCELLCELL树树 1 1 1 1 空间数据索引的必要性 空间数据索引的必要性 空间数据索引的必要性 空间数据索引的必要性 在在GISGISGISGIS中需要根据空间位置进行查询 例如 中需要根据空间位置进行查询 例如 找出找出 通过某个区域的所有公路通过某个区域的所有公路 检索在某个区域内的检索在某个区域内的 所有湖泊所有湖泊 等等 等等 为了处理这类空间查询 数据库需要检查每一个可为了处理这类空间查询 数据库需要检查每一个可 能满足条件的空间要素的记录 看它是否与查询区能满足条件的空间要素的记录 看它是否与查询区 域相交或是在查询区域内 这种空间相交运算需要域相交或是在查询区域内 这种空间相交运算需要 先读出空间要素几何形状的边界坐标 然后再与空先读出空间要素几何形状的边界坐标 然后再与空 间区域进行空间关系运算 间区域进行空间关系运算 由于传统数据库的这种穷尽式搜索方法花费的磁盘由于传统数据库的这种穷尽式搜索方法花费的磁盘 访问时间和空间运算时间都很长 往往达到令人无访问时间和空间运算时间都很长 往往达到令人无 法忍受的程度 故必须建立空间数据索引机制 法忍受的程度 故必须建立空间数据索引机制 2 2 2 2 空间索引的层次 空间索引的层次 空间索引的层次 空间索引的层次 工程工程 工程区索引工程区索引 工作区工作区1 1 1 1工作区工作区2 2 2 2工作区工作区3 3 3 3 工作层工作层1 1 1 1工作层工作层2 2 2 2工作层工作层3 3 3 3 地物空间索引地物空间索引 地物层地物层 3 3 3 3 无缝图层 无缝图层 无缝图层 无缝图层 现实世界的地区 城市均是连续的 现实世界的地区 城市均是连续的 对较小的区域可以将数据物理连接 生对较小的区域可以将数据物理连接 生 成物理无缝图层 成物理无缝图层 对无法生成物理无缝图层的地区 可以对无法生成物理无缝图层的地区 可以 建立逻辑无缝图层 建立逻辑无缝图层 逻辑无缝图层建立了地物的连接描述 逻辑无缝图层建立了地物的连接描述 4 4 4 4 工作区索引 工作区索引 工作区索引 工作区索引 对海量数据而言 必须建立多个工作对海量数据而言 必须建立多个工作 区 将数据按工作区存放于存储器区 将数据按工作区存放于存储器 建立索引文件建立索引文件 在开窗操作时 系统根据窗口坐标 按在开窗操作时 系统根据窗口坐标 按 索引文件迅速调入所涉及的工作区索引文件迅速调入所涉及的工作区 5 5 5 5 目标索引 目标索引 目标索引 目标索引 窗坐标索引机制窗坐标索引机制 格网型空间索引格网型空间索引 BSPBSP索引机制索引机制 KDBKDB树树 R R树和树和R R 树树 CELLCELL树树 6 6 6 6 窗 窗 窗 窗 坐标坐标坐标坐标 索引索引索引索引 机制机制机制机制 建立每个实体的最小包容矩形 记录其对角坐标 建立每个实体的最小包容矩形 记录其对角坐标 单点检索可判断是否在包容矩形内 范围检索可判单点检索可判断是否在包容矩形内 范围检索可判 断每个实体的最小包容矩形和范围的关系 内 外 断每个实体的最小包容矩形和范围的关系 内 外 相交 相交 对所有空间实体的外接矩形最大最小坐标进行落入对所有空间实体的外接矩形最大最小坐标进行落入 判别 其中空间实体判别 其中空间实体B B B B C C C C完全落入查询窗 从空间完全落入查询窗 从空间 数据库中提取数据库中提取B B B B和和C C C C的相应数据 的相应数据 A 查询窗口 B C C C C E F D 7 7 7 7 格网型空间索引 格网型空间索引 格网型空间索引 格网型空间索引 将区域用横竖线条划分大小相等和不等将区域用横竖线条划分大小相等和不等 的格网 记录每一个格网所包含的空间的格网 记录每一个格网所包含的空间 实体 进行空间查询时 首先计算出查实体 进行空间查询时 首先计算出查 询对象所在格网 然后再在该网格中快询对象所在格网 然后再在该网格中快 速查询所选空间实体 速查询所选空间实体 一条河流 一个湖泊和一条省界 它们的关键字分别为一条河流 一个湖泊和一条省界 它们的关键字分别为 5 5 5 5 11111111和和23232323 河流穿过的栅格为 河流穿过的栅格为2 2 2 2 34343434 35353535 67676767 68686868 湖 湖 泊覆盖的栅格为泊覆盖的栅格为68686868 69696969 100100100100 101101101101 省界所通过的栅格 省界所通过的栅格 为为5 5 5 5 37373737 36363636 35353535 67676767 99999999 98989898 97979797 8 8 8 8 BSPBSPBSPBSP索引机制索引机制索引机制索引机制 是一种二叉树 它将空间逐级进行一分为二的划分 是一种二叉树 它将空间逐级进行一分为二的划分 BSPBSPBSPBSP树能很好地与空间数据库中空间对象的分布情况相适树能很好地与空间数据库中空间对象的分布情况相适 应 但对一般情况而言 应 但对一般情况而言 BSPBSPBSPBSP树深度较大 对各种操作均有树深度较大 对各种操作均有 不利影响 不利影响 9 9 9 9 KDBKDBKDBKDB树树树树 KDBKDBKDBKDB树是树是B B B B树向多维空间的一种发展 树向多维空间的一种发展 它对于多维空间中的点进行索引具有较它对于多维空间中的点进行索引具有较 好的动态特性 删除和增加空间点对象好的动态特性 删除和增加空间点对象 也可以很方便地实现 也可以很方便地实现 其缺点是不直接支持占据一定空间范围其缺点是不直接支持占据一定空间范围 的地物要素 如二维空间中的线和面 的地物要素 如二维空间中的线和面 该缺点可以通过空间映射或变换的方法该缺点可以通过空间映射或变换的方法 部分地得到解决 部分地得到解决 10101010 R R R R 树示意图树示意图树示意图树示意图 上图表示了三组多边形 矩形 用实线画出 及对应于上图表示了三组多边形 矩形 用实线画出 及对应于 这三组多边形的这三组多边形的R R树中结点的外包络矩形 用虚线画树中结点的外包络矩形 用虚线画 出 右图为出 右图为R R树本身 树本身 11111111 R R R R 树结构示意图树结构示意图树结构示意图树结构示意图 R R R R 树的数据结构与树的数据结构与R R R R树的相同 但是 对于被分割的下层虚拟矩形或实树的相同 但是 对于被分割的下层虚拟矩形或实 体外接矩形 还要增加关系表达 体外接矩形 还要增加关系表达 原矩形标识符 分割后矩形原矩形标识符 分割后矩形1 1 1 1的标识符 分割后矩形的标识符 分割后矩形2 2 2 2的标识符的标识符 12121212 R R R R树和树和树和树和R R R R 树比较树比较树比较树比较 由于由于R R R R树兄弟结点对应的空间区域可以重叠 因此 树兄弟结点对应的空间区域可以重叠 因此 R R R R树树 可以较容易地进行插入和删除操作 但正因为区域之间可以较容易地进行插入和删除操作 但正因为区域之间 有重叠 空间索引可能要对多条路径进行搜索后才能得有重叠 空间索引可能要对多条路径进行搜索后才能得 到最后的结果 因此 其空间搜索的效率较低 到最后的结果 因此 其空间搜索的效率较低 在在R R R R 树中 兄弟结点对应的空间区域没有重叠 而没有树中 兄弟结点对应的空间区域没有重叠 而没有 重叠的区域划分可以使空间索引搜索的速度大大提高 重叠的区域划分可以使空间索引搜索的速度大大提高 但由于在插入和删除空间对象时要保证兄弟结点对应的但由于在插入和删除空间对象时要保证兄弟结点对应的 空间区域不重叠 而使插入和删除操作的效率降低 空间区域不重叠 而使插入和删除操作的效率降低 13131313 CELLCELLCELLCELL树树树树 R R R R树和树和R R R R 在插入 删除和空间搜索效率两方面难于兼顾 在插入 删除和空间搜索效率两方面难于兼顾 故故CELLCELLCELLCELL树应运而生 它在采用凸多边形来作为划分的基本树应运而生 它在采用凸多边形来作为划分的基本 单位 与单位 与BSPBSPBSPBSP树有类似之处 子空间不再相互覆盖 故树有类似之处 子空间不再相互覆盖 故 CELLCELLCELLCELL树是比较优秀的空间索引方法 树是比较优秀的空间索引方法 6 5 6 5 6 5 6 5 空间数据模型空间数据模型空间数据模型空间数据模型 三种传统模型三种传统模型 层次 网络 关系层次 网络 关系 面向对象模型面向对象模型 二维矢量模型二维矢量模型 栅格数据模型栅格数据模型 三维空间模型三维空间模型 矢量 栅格矢量 栅格 一 三种传统模型 层次层次 网络网络 关系关系 1 1 1 1 层次模型 层次模型 层次模型 层次模型 ABC 1 DEF 2 E 层次模型是一种树层次模型是一种树 结构模型 它把数据按结构模型 它把数据按 自然的层次关系组织起自然的层次关系组织起 来 以反映数据之间的来 以反映数据之间的 隶属关系 隶属关系 一棵树有且仅有一一棵树有且仅有一 个无双亲结点的称为根个无双亲结点的称为根 的结点 其余结点有且的结点 其余结点有且 仅有一个双亲结点 仅有一个双亲结点 2 2 2 2 层次模型描述矢量数据 层次模型描述矢量数据 层次模型描述矢量数据 层次模型描述矢量数据 特点是将数据特点是将数据 组织成一对多组织成一对多 关系的结构 关系的结构 层次结构采用层次结构采用 关键字来访问关键字来访问 其中每一层次其中每一层次 的每一部分 的每一部分 层次数据库结层次数据库结 构特别适用于构特别适用于 文献目录 土文献目录 土 壤分类 部门壤分类 部门 机构等分级数机构等分级数 据的组织据的组织 1 2 3 4 5 6 a b c d e f g M M abcdefg 1223344134355664 c 3 3 3 3 层次数据的特点 层次数据的特点 层次数据的特点 层次数据的特点 优点优点 存取方便且速度快存取方便且速度快 结构清晰 容易理解结构清晰 容易理解 数据修改和数据库扩展容易实现数据修改和数据库扩展容易实现 检索关键属性十分方便检索关键属性十分方便 缺陷缺陷 结构呆板 缺乏灵活性结构呆板 缺乏灵活性 同一属性数据要存储多次 数据冗余大 如公共边 同一属性数据要存储多次 数据冗余大 如公共边 不适合于拓扑空间数据的组织不适合于拓扑空间数据的组织 4 4 4 4 空间对象的层次分类编码 空间对象的层次分类编码 空间对象的层次分类编码 空间对象的层次分类编码 分类对象的从属和层次关系分类对象的从属和层次关系 有明确的分类对象类别和严格的隶属关系有明确的分类对象类别和严格的隶属关系 高压711电线架715 管线 7 地下电力线 与电缆72 电力线71地下检修井74管线73 低压712电杆713电塔714 不依比例7142依比例7141 5 5 5 5 网网网网 络络络络 模模模模 型型型型 基本特征 基本特征 结点数据之间没有明确的从属关系 一个结点可结点数据之间没有明确的从属关系 一个结点可 与其它多个结点建立联系 即结点之间的联系是任意的 任与其它多个结点建立联系 即结点之间的联系是任意的 任 何两个结点之间都能发生联系 可表示多对多的关系 何两个结点之间都能发生联系 可表示多对多的关系 6 6 6 6 用网络数据模型描述复杂关系 用网络数据模型描述复杂关系 用网络数据模型描述复杂关系 用网络数据模型描述复杂关系 网络模型用连接指令或指针来确定数据间的显式网络模型用连接指令或指针来确定数据间的显式 连接关系 是具有多对多类型的数据组织方式连接关系 是具有多对多类型的数据组织方式 系名 土木系 教师数学生数研究生 系名 管理系 教师数 49 学生数 257 研究生 71 学校名称 工程学院 系名 测绘系 教师数 52 学生数 300 研究生 70 系名教师数学生数研究生 系名教师数学生数 学号 002312 姓名 杨乐 年级 3 籍贯 广东 系名教师数学生数研究生 系名教师数学生数 教师号 66 姓名 年龄 53 职称 教授 系名教师数学生数研究生 系名教师数学生数 课程号 A01 课程名 GIS 周学时 4 学分 5 系名教师数 系名 学号 002312 课程号 A01 7 网络数据模型特点 优点 优点 能明确而方便地表示数据间的复杂关系能明确而方便地表示数据间的复杂关系 数据冗余小数据冗余小 缺陷 缺陷 网状结构的复杂 增加了用户查询和定位的困难网状结构的复杂 增加了用户查询和定位的困难 需要存储数据间联系的指针 使得数据量增大需要存储数据间联系的指针 使得数据量增大 数据的修改不方便 指针必须修改数据的修改不方便 指针必须修改 8 8 8 8 关系数据模型 关系数据模型 关系数据模型 关系数据模型 关系模型的数据结构为满足一定条件的二维表 表具有固关系模型的数据结构为满足一定条件的二维表 表具有固 定的列数和任意的行数 在数学上称为定的列数和任意的行数 在数学上称为 关系关系 二维表是同类实体的各种属性的集合 每个实体对应于表二维表是同类实体的各种属性的集合 每个实体对应于表 中的一行 在关系中称为元组 通常称为一条记录 中的一行 在关系中称为元组 通常称为一条记录 表中的列表示属性 称为域 相当于通常记录中的一个数表中的列表示属性 称为域 相当于通常记录中的一个数 据项 若二维表中有据项 若二维表中有n n n n个域 则每一行叫做一个个域 则每一行叫做一个n n n n元组 元组 这样的关系称为这样的关系称为n n n n度度 元元 关系 关系 表的行对应于对象的实例 各个表的行列交点就用来存贮表的行对应于对象的实例 各个表的行列交点就用来存贮 简单值 满足一定条件的规范化关系的集合 就构成了关简单值 满足一定条件的规范化关系的集合 就构成了关 系模型 系模型 9 9 9 9 房屋表和道路表 房屋表和道路表 2001砼12公房29 1986砖7私房20 建筑年代结构楼层数性质房号 6 4 车道数 200116沥青2201 198612水泥1302 建筑年代宽度路面材料等级编号 1 2 3 4 5 6 a b c d e f g M 10101010 用关系模型表示地理实体 用关系模型表示地理实体 用关系模型表示地理实体 用关系模型表示地理实体 地理实体地理实体 多边形关系 多边形关系 M M M M 多边形多边形 边关系 边关系 a b c d a b c d a b c d a b c d e f g c e f g c e f g c e f g c 边边 结点关系 结点关系 a Va Va Va V V V V V2 2 2 2 b Vb Vb Vb V2 2 2 2 V V V V3 3 3 3 c V c V c V c V3 3 3 3 V V V V4 4 4 4 d Vd Vd Vd V V V V V4 4 4 4 e Ve Ve Ve V V V V V5 5 5 5 f Vf Vf Vf V5 5 5 5 V V V V6 6 6 6 g Vg Vg Vg V6 6 6 6 V V V V4 4 4 4 cgfe dcba 46g 65f 53e 41d 43c 32b 21a M M 11111111 关系模型的进一步发展 关系模型的进一步发展 关系模型的进一步发展 关系模型的进一步发展 RDBMSRDBMSRDBMSRDBMS的现状是理论和技术都非常完善的现状是理论和技术都非常完善 和成熟 基本上占据了全部传统应用领和成熟 基本上占据了全部传统应用领 域和域和90 90 90 90 以上的非传统应用领域以上的非传统应用领域 典型的代表有 典型的代表有 Oracle MS SQL DB2 INGRES SyBase Xbase FoxPro Rdb VMS Informix 12121212 非结构化大型对象的引进 非结构化大型对象的引进 多媒体多媒体 如文本数据 图象数据 静止的视如文本数据 图象数据 静止的视 频片断 全动感的视频信息 声音波形等等 频片断 全动感的视频信息 声音波形等等 需要用关系数据库存储和管理这类非结构化数需要用关系数据库存储和管理这类非结构化数 据 据 DECDECDECDEC公司于公司于1981198119811981年就引进能存贮变长字符串和年就引进能存贮变长字符串和 二进制数据的概念 目前一些大型的二进制数据的概念 目前一些大型的RDBMSRDBMSRDBMSRDBMS 如 如OracleOracleOracleOracle等 中 增加了大型对象这种数据等 中 增加了大型对象这种数据 类型 类型 数据从等长转为变长 数据从等长转为变长 13131313 分布式数据库 分布式数据库 70707070年代以来计算机网络迅速发展 在地年代以来计算机网络迅速发展 在地 理上分散的公司 团体和组织对于数据理上分散的公司 团体和组织对于数据 库更为广泛的应用 产生了分布式数据库更为广泛的应用 产生了分布式数据 库系统 库系统 分布式数据库系统是数据库和网络两者分布式数据库系统是数据库和网络两者 有机结合的结果 有机结合的结果 比如 全省各院校可以把招生的情况存比如 全省各院校可以把招生的情况存 放在各自的招生办 省招生办可以通过放在各自的招生办 省招生办可以通过 网络随时查询统计各校数据 网络随时查询统计各校数据 14141414 对象特性的融入 对象特性的融入 为了迎接面向对象数据库在非传统应用为了迎接面向对象数据库在非传统应用 领域对关系数据库提出的挑战 确保关领域对关系数据库提出的挑战 确保关 系数据库在数据库领域的霸主地位 关系数据库在数据库领域的霸主地位 关 系数据库巨头系数据库巨头OracleOracleOracleOracle SybaseSybaseSybaseSybase DB2DB2DB2DB2 InformixInformixInformixInformix都在积极努力 使自己的关系都在积极努力 使自己的关系 型产品增加一些面向对象的成分 目前型产品增加一些面向对象的成分 目前 已经有推向市场的这类产品存在 如已经有推向市场的这类产品存在 如 Oracle10gOracle10gOracle10gOracle10g DB2DB2DB2DB2等 等 15151515 面向对象模型 面向对象模型 面向对象模型 面向对象模型 面向对象的基本概念是在上世纪面向对象的基本概念是在上世纪70707070年代萌发 年代萌发 它的基本做法是把系统工程中的某个模块和构它的基本做法是把系统工程中的某个模块和构 件视为问题空间的一个或一类对象 件视为问题空间的一个或一类对象 80808080年代 面向对象的方法得到很快发展 在系年代 面向对象的方法得到很快发展 在系 统工程 计算机 人工智能等领域获得了广泛统工程 计算机 人工智能等领域获得了广泛 应用 应用 90909090年代 人们在更高级的层次上和更广泛的领年代 人们在更高级的层次上和更广泛的领 域内对面向对象的方法进行研究 域内对面向对象的方法进行研究 16161616 面向对象的特性和核心技术 面向对象的特性和核心技术 面向对象的特性和核心技术 面向对象的特性和核心技术 面向对象方法的特性面向对象方法的特性 抽象性 封装性 多态性抽象性 封装性 多态性 面向对象方法的核心技术面向对象方法的核心技术 分类 概括 聚集 联合分类 概括 聚集 联合 17171717 面向对象的几何抽象类型 面向对象的几何抽象类型 面向对象的几何抽象类型 面向对象的几何抽象类型 GIS GIS GIS GIS中的各种地物 在几何性质方面不外乎表现为四种类中的各种地物 在几何性质方面不外乎表现为四种类 型 即点状地物 线状处物 面状地物以及由它们混合组型 即点状地物 线状处物 面状地物以及由它们混合组 成的复杂地物 因而这四种类型可以作为成的复杂地物 因而这四种类型可以作为GISGISGISGIS中各种地物类中各种地物类 型的超类 型的超类 空间地物 点状地物线状地物面状地物复杂地物 电视塔 桥 梁 车 站 道 路 水 管 电力线 建筑物 湖 公 园 矿 山 大 学 县 三 二维矢量模型 矢量方法强调了离散现象的存在 由边矢量方法强调了离散现象的存在 由边 界线 点 线 面 来确定边界 因此界线 点 线 面 来确定边界 因此 可以看成是基于要素的 可以看成是基于要素的 然而 在一些基于矢量的然而 在一些基于矢量的GISGISGISGIS中 表现表中 表现表 面的便利 带给它模拟二维场的可能面的便利 带给它模拟二维场的可能 性 最常见的例子就是地表高程 性 最常见的例子就是地表高程 二 维 矢 量 数 据 表 示 四 栅格数据模型四 栅格数据模型四 栅格数据模型四 栅格数据模型 栅格数据模型是基于连续铺盖的 它是将连续空间离栅格数据模型是基于连续铺盖的 它是将连续空间离 散化 即用二维铺盖或划分覆盖整个连续空间 铺盖散化 即用二维铺盖或划分覆盖整个连续空间 铺盖 可以分为规则的和不规则的 后者可当做拓扑多边形可以分为规则的和不规则的 后者可当做拓扑多边形 处理 如社会经济分区 城市街区 铺盖的特征参数处理 如社会经济分区 城市街区 铺盖的特征参数 有尺寸 形状 方位和间距 有尺寸 形状 方位和间距 对同一现象 也可能有若干不同尺度 不同聚分性对同一现象 也可能有若干不同尺度 不同聚分性 Aggregation or SubdivisionsAggregation or SubdivisionsAggregation or SubdivisionsAggregation or Subdivisions 的铺盖 的铺盖 在边数从在边数从3 3 3 3到到N N N N的规则铺盖 的规则铺盖 Regular TesselationsRegular TesselationsRegular TesselationsRegular Tesselations 中 方格 三角形和六角形是空间数据处理中最常用中 方格 三角形和六角形是空间数据处理中最常用 的 三角形是最基本的不可再分的单元 根据角度和的 三角形是最基本的不可再分的单元 根据角度和 边长的不同 可以取不同的形状 方格 三角形和六边长的不同 可以取不同的形状 方格 三角形和六 角形可完整地铺满一个平面 角形可完整地铺满一个平面 栅格单元的形态栅格单元的形态栅格单元的形态栅格单元的形态 栅格数据表示的地表 五 三维空间模型五 三维空间模型五 三维空间模型五 三维空间模型 三维矢量模型三维矢量模型 三维边界三维边界 用顶点 边 面和体三个表来表示用顶点 边 面和体三个表来表示 三维栅格数据模型 假设体假设体V V V V可以放在一个充分大的正方体可以放在一个充分大的正方体C C C C内 内 C C C C 的边长为的边长为2 2 2 2n n n n 对形体对形体VCVCVCVC 如果 如果V CV CV CV C 那么 那么V V V V的八叉树仅有树的八叉树仅有树 根 否则对根 否则对C C C C等分为八个子立方体 只要某个等分为八个子立方体 只要某个 子立方体不是完全空白或完全为子立方体不是完全空白或完全为V V V V所占据 就所占据 就 要再被八等分 直到灰节点分完要再被八等分 直到灰节点分完 八叉树上的节点可分为三类八叉树上的节点可分为三类 1 1 1 1 灰节点 对应的立方体部分地为 灰节点 对应的立方体部分地为V V V V所占据 所占据 2 2 2 2 白节点 所对应的立方体中无 白节点 所对应的立方体中无V V V V的内容 的内容 3 3 3 3 黑节点 所对应的立方体全为 黑节点 所对应的立方体全为V V V V所占据所占据 体元形式的三维数据体元形式的三维数据体元形式的三维数据体元形式的三维数据 线性八叉树编码线性八叉树编码线性八叉树编码线性八叉树编码 本章要点本章要点本章要点本章要点 建立数据模型的意义建立数据模型的意义 数据模型和数据结构的区别数据模型和数据结构的区别 空间数据的三个基本特征空间数据的三个基本特征 如何描述地理空间数据 如何描述地理空间数据 空间数据的分类 分级 编码空间数据的分类 分级 编码 工作空间 分区 层的概念工作空间 分区 层的概念 空间索引的种类 网格索引 空间索引的种类 网格索引 R R R R树树 面向对象数据模型的优点面向对象数据模型的优点 第七章第七章第七章第七章 地理空间数据结构地理空间数据结构地理空间数据结构地理空间数据结构 无拓扑矢量数据结构无拓扑矢量数据结构 拓扑数据结构拓扑数据结构 栅格数据结构栅格数据结构 DEMDEMDEMDEM结构结构 四叉树和八叉树四叉树和八叉树 其它数据结构其它数据结构 7 1 7 1 7 1 7 1 无拓扑矢量数据结构无拓扑矢量数据结构无拓扑矢量数据结构无拓扑矢量数据结构 点的矢量结构点的矢量结构 链的矢量结构链的矢量结构 面的矢量结构面的矢量结构 点 节点点 节点 结点结点 链 链 弧弧 边边 线线 线段线段 面 多边形面 多边形 区域区域 面面 体 体 点弧面的矢量表示点弧面的矢量表示点弧面的矢量表示点弧面的矢量表示 23523523523521212121656565652 2 2 2 23423423423476767676232323231 1 1 1 H H H HY Y Y YX X X X点号点号 弧表弧表1 1 1 1 xyh xyh xyh xyh xyh xyh xyh xyh 2 2 2 2 xyh xyh xyh xyh xyh xyh xyh xyh 1 1 1 1 坐标串坐标串链号链号 弧表弧表2 2 2 2 点号点号 点号点号 2 2 2 2 点号点号 点号点号 1 1 1 1 点号串点号串链号链号 面表面表1 1 1 1面表面表2 2 2 2 面表面表3 3 3 3 xyh xyh xyh xyh xyh xyh xyh xyh 2 2 2 2 xyh xyh xyh xyh xyh xyh xyh xyh 1 1 1 1 坐标串坐标串面号面号 点号点号 点号点号 2 2 2 2 点号点号 点号点号 1 1 1 1 点号串点号串面号面号 弧号弧号 弧号弧号 2 2 2 2 弧号弧号 弧号弧号 1 1 1 1 弧号串弧号串面号面号 点表点表 各种表示法的比较各种表示法的比较各种表示法的比较各种表示法的比较 点号点号 弧 弧号弧 弧号 面面 冗余小 维护方便 调用复杂冗余小 维护方便 调用复杂 弧弧 坐标 面坐标 面 坐标坐标 冗余大 维护不便 调用简单冗余大 维护不便 调用简单 易产生多重坐标易产生多重坐标 7 2 7 2 7 2 7 2 拓扑数据结构拓扑数据结构拓扑数据结构拓扑数据结构 在在GISGISGISGIS中 为了真实地反映地理实体 不仅要存储实体中 为了真实地反映地理实体 不仅要存储实体 的位置 形状 大小和属性 还必须存储实体间的相的位置 形状 大小和属性 还必须存储实体间的相 互关系 互关系 拓扑元素拓扑元素 点 弧 面点 弧 面 拓扑关系拓扑关系 最基本关系最基本关系 关联 关联 空间图形中空间图形中不同类元素不同类元素之间的拓扑关系之间的拓扑关系 邻接 邻接 空间图形中空间图形中同类元素同类元素之间的拓扑关系之间的拓扑关系 其它关系其它关系 包含 包含 空间图形中空间图形中同类不同级同类不同级元素之间的拓扑关系元素之间的拓扑关系 连通 连通 空间网络图形中 结点之间存在的路径关系空间网络图形中 结点之间存在的路径关系 层次 层次 相同拓扑元素相同拓扑元素间的等级关系间的等级关系 拓扑关系的表示拓扑关系的表示拓扑关系的表示拓扑关系的表示 拓扑关系表示实例拓扑关系表示实例拓扑关系表示实例拓扑关系表示实例 弧段串弧段串面块面块IDIDIDID A A A A L6 L6 L6 L6 B B B B L7L7L7L7 L8 L8 L8 L8 L9L9L9L9 L10 L10 L10 L10 C C C C L1L1L1L1 L11 L11 L11 L11 L7 L7 L7 L7 L5 L5 L5 L5 D D D D L11L11L11L11 L2L2L2L2 L12L12L12L12 L8 L8 L8 L8 E E E E L L L L13 131313 L L L L9 9 9 9 L L L L12 121212 L L L L3 3 3 3 F F F F L4L4L4L4 L5L5L5L5 L10 L10 L10 L10 L13 L13 L13 L13 L L L L1 1 1 1 P P P P9 9 9 9 P P P P2 2 2 2 L L L L2 2 2 2 P P P P2 2 2 2 P P P P3 3 3 3 L L L L3 3 3 3 P P P P3 3 3 3 P P P P6 6 6 6 L L L L4 4 4 4 P P P P6 6 6 6 P P P P9 9 9 9 P P P P1 1 1 1 L L L L6 6 6 6 P P P P2 2 2 2 L L L L1 1 1 1 L L L L11 111111 L L L L2 2 2 2 P P P P3 3 3 3 L L L L2 2 2 2 L L L L12 121212 L L L L3 3 3 3 P P P P4 4 4 4 L L L L12 121212 L L L L8 8 8 8 L L L L9 9 9 9 L L L L1 1 1 1 0 0 0 0C C C C L L L L2 2 2 2 0 0 0 0D D D D L L L L3 3 3 3 0 0 0 0E E E E L L L L4 4 4 4 0 0 0 0F F F F L L L L5 5 5 5 C C C C F F F F 起点 终点起点 终点弧段弧段IDIDIDID弧段串弧段串结点结点IDIDIDID 右多边形右多边形左多边形左多边形弧段弧段IDIDIDID 全显式和半隐式全显式和半隐式全显式和半隐式全显式和半隐式 弧段 起结点 终结点 左多边形 右多边形弧段 起结点 终结点 左多边形 右多边形 全显式全显式 半隐式半隐式 7 3 7 3 7 3 7 3 栅格数据结构栅格数据结构栅格数据结构栅格数据结构 基于像元基于像元 基于层基于层 基于多边形基于多边形 栅栅栅栅 格格格格 数数数数 据据据据 结结结结 构构构构 的的的的 存存存存 储储储储 顺顺顺顺 序序序序 栅格数据结构小结栅格数据结构小结栅格数据结构小结栅格数据结构小结 基本概念基本概念 像元及像元阵列 像元属性及属性取值方法像元及像元阵列 像元属性及属性取值方法 像元越小 分辨率越高 图斑越精细像元越小 分辨率越高 图斑越精细 理解理解栅格编码栅格编码 同样的数据可以有不同的编码方式 不影响结果同样的数据可以有不同的编码方式 不影响结果 的显示的显示 数据压缩编码方式可以自己定义数据压缩编码方式可以自己定义 7 4 DEM7 4 DEM7 4 DEM7 4 DEM结构结构结构结构 矩形格网结构矩形格网结构 不规则三角网结构不规则三角网结构 DEM DEM 的生成的生成 DEM DEM DEM DEM 的概念的概念的概念的概念 数字高程模型 数字高程模型 DEM DEM DTMDTM中属性为高程的要素称为数中属性为高程的要素称为数 字高程模型字高程模型 它是地表单元上的高程集合它是地表单元上的高程集合 通常用矩阵通常用矩阵 来表示 来表示 DEMDEM是建立是建立DTMDTM的的 基础数据基础数据 或称为单要素图 其它或称为单要素图 其它 要素均可以从要素均可以从DEMDEM数据直接或间接导出 这些数据直接或间接导出 这些 派生数派生数 据据 通常包括 平均高程 坡度 坡向等 通常包括 平均高程 坡度 坡向等 矩形格网结构矩形格网结构矩形格网结构矩形格网结构 矩形格网矩形格网GRIDGRID是一个高程矩阵是一个高程矩阵 可以由高程点 等高线内插产生 也可以由全可以由高程点 等高线内插产生 也可以由全 数字摄影测量模式产生 直接接收数字摄影测量模式产生 直接接收VirtuoZoVirtuoZo系系 统格式的数字高程模型和正射影像数据 同统格式的数字高程模型和正射影像数据 同 时 也接受解析测图仪实测的随机采样数据和时 也接受解析测图仪实测的随机采样数据和 既有地形图数字化等高线数据既有地形图数字化等高线数据 对于特殊地形 还存在地形地物特征点线数据 对于特殊地形 还存在地形地物特征点线数据 随机栅格转换的算法包括距离加权平均 又称随机栅格转换的算法包括距离加权平均 又称 移动曲面法 和基于移动曲面法 和基于TINTIN的两种方法的两种方法 内插矩形格网内插矩形格网内插矩形格网内插矩形格网 TIN TIN TIN TIN 结构结构结构结构 G G G GI I I I0 0 0 09 9 9 94 4 4 43 3 3 3J J J J J J J JH H H H0 0 0 09 9 9 95 5 5 54 4 4 4I I I I9 9 9 9 I I I IE E E E0 0 0 09 9 9 96 6 6 65 5 5 5H H H H8 8 8 8 D D D DF F F FJ J J J8 8 8 88 8 8 83 3 3 3G G G G7 7 7 7 E E E EG G G GC C C C9 9 9 98 8 8 87 7 7 7F F F F6 6 6 6 H H H HF F F FB B B B9 9 9 97 7 7 76 6 6 6E E E E5 5 5 5 C C C CG G G G0 0 0 08 8 8 83 3 3 33 3 3 3D D D D4 4 4 4 B B B BF F F FD D D D7 7 7 78 8 8 82 2 2 2C C C C3 3 3 3 A A A AE E E EC C C C6 6 6 67 7 7 72 2 2 2B B B B2 2 2 2 0 0 0 0B B B B0 0 0 06 6 6 62 2 2 21 1 1 1A A A A1 1 1 1 3 32 21 13 3 3 32 2 2 21 1 1 1 邻邻 顶点顶点 号号H H H HY Y Y YX X X X点号点号 TIN TIN TIN TIN 的主要特征的主要特征的主要特征的主要特征 TINTINTINTIN由一系列三角形组成由一系列三角形组成由一系列三角形组成由一系列三角形组成 三角形顶点都是一些特征点三角形顶点都是一些特征点三角形顶点都是一些特征点三角形顶点都是一些特征点 每个三角形的坡度 坡向均一每个三角形的坡度 坡向均一每个三角形的坡度 坡向均一每个三角形的坡度 坡向均一 三角形大小随地形变化而变三角形大小随地形变化而变三角形大小随地形变化而变三角形大小随地形变化而变 尽可能是等边三角形尽可能是等边三角形尽可能是等边三角形尽可能是等边三角形 三角形外接圆内没有其它点三角形外接圆内没有其它点三角形外接圆内没有其它点三角形外接圆内没有其它点 与与与与VoronoiVoronoiVoronoiVoronoi多边形多边形多边形多边形 泰森多边形泰森多边形泰森多边形泰森多边形 对偶对偶对偶对偶 以拓扑方式存储以拓扑方式存储以拓扑方式存储以拓扑方式存储 DEM DEM DEM DEM 的生成的生成的生成的生成 r r r r 7 5 7 5 7 5 7 5 四叉树和八叉树四叉树和八叉树四叉树和八叉树四叉树和八叉树 将栅格数据二维空间区域按照将栅格数据二维空间区域按照4 4 4 4个象限进行递归分割个象限进行递归分割 2 2 2 2n n n n 2 2 2 2n n n n 且 且n 1n 1n 1n 1 直到子象限的数值单调为止 最后得 直到子象限的数值单调为止 最后得 到一棵四分叉的倒向树 到一棵四分叉的倒向树 四叉树分解 各子象限大小不完全一样 但都是同代码栅四叉树分解 各子象限大小不完全一样 但都是同代码栅 格单元组成的子块 其中最上面的一个结点叫做根结点 格单元组成的子块 其中最上面的一个结点叫做根结点 它对应于整个图形 它对应于整个图形 不能再分的结点称为叶子结点 可能落在不同的层上 该不能再分的结点称为叶子结点 可能落在不同的层上 该 结点代表子象限单一的代码 所有叶子结点所代表的方形结点代表子象限单一的代码 所有叶子结点所代表的方形 区域覆盖了整个图形 区域覆盖了整个图形 从上到下 从左到右为叶子结点编号 最下面的一排数字从上到下 从左到右为叶子结点编号 最下面的一排数字 表示各子区的代码 表示各子区的代码 为了保证四叉树分解能不断的进行下去 要求图形必须为为了保证四叉树分解能不断的进行下去 要求图形必须为 2n2n2n2n 2n2n2n2n的栅格阵列 的栅格阵列 n n n n为极限分割次数 为极限分割次数 n n n n 1 1 1 1是四叉树最是四叉树最 大层数或最大高度 大层数或最大高度 四叉树编码四叉树编码四叉树编码四叉树编码 11111111 1212121213131313 141414141515151516161616 1717171718181818 19191919202020202121212122222222 2323232324242424 2525252526262626272727 2728282828 2929292930303030 31313131323232323333333336363636373737373838383839393939 343434343535353540404040 0 0 00 0 00 0 00 0 0 0 0 0 0 3 3 3 3 3 3 0 3 3 3 3 3 0 3 3 3 3 3 0 3 3 3 3 3 0 3 3 33 3 5 3 0 0 2 2 3 3 5 3 0 0 2 23 3 5 3 0 0 2 23 3 5 3 0 0 2 22 3 2 2 2 2 0 22 3 2 2 2 2 0 22 3 2 2 2 2 0 22 3 2 2 2 2 0 2 2 2 2 5 2 5 5 52 2 2 5 2 5 5 52 2 2 5 2 5 5 52 2 2 5 2 5 5 5 3 33 33 33 33 5 53 5 53 5 53 5 5 西南西南东南东南 西北西北 东北东北 四叉树地址和 Morton码 MortonMortonMortonMorton码码码码 叶节点码叶节点码叶节点码叶节点码 将十进制将十进制MortonMortonMortonMorton码转为二进制码码转为二进制码 39 39 39 39 100111 100111 100111 100111 将二进制将二进制MortonMortonMortonMorton码每二位转为十进制数码每二位转为十进制数 10 01 11 10 01 11 10 01 11 10 01 11 2 1 3 2 1 3 2 1 3 2 1 3 叶节点码叶节点码叶节点码叶节点码 MortonMortonMortonMorton码码码码 将叶节点码逐位转为二进制将叶节点码逐位转为二进制 2 1 3 2 1 3 2 1 3 2 1 3 10 01 1110 01 1110 01 1110 01 11 将二进制叶节点码转为将二进制叶节点码转为MortonMortonMortonMorton码码 100111 100111 100111 100111 39 39 39 39 1 1 1 1 2 2 2 25 5 5 5 0 0 0 0 2 2 2 24 4 4 4 0 0 0 0 2 2 2 23 3 3 3 1 1 1 1 2 2 2 22 2 2 2 1 1 1 1 2 2 2 21 1 1 1 1 1 1 1 2 2 2 20 0 0 0 32 0 0 4 2 1 39 32 0 0 4 2 1 39 32 0 0 4 2 1 39 32 0 0 4 2 1 39 MortonMortonMortonMorton码码码码 行列值行列值行列值行列值 将将MortonMortonMortonMorton码码39393939转为二进制转为二进制100111100111100111100111 将二进制的将二进制的MortonMortonMortonMorton码奇偶分开码奇偶分开 10 01 11 10 01 11 10 01 11 10 01 11 101 011 101 011 101 011 101 011 将奇偶分别变成十进制的行列将奇偶分别变成十进制的行列 101 011101 011101 011101 011 5 3 5 3 5 3 5 3 行列值行列值行列值行列值 MortonMortonMortonMorton码码码码 将十进制的行列分别变成二进制将十进制的行列分别变成二进制 5 3 5 3 5 3 5 3 101 011101 011101 011101 011 将二进制的行列值奇偶合并得将二进制的行列值奇偶合并得MortonMortonMortonMorton码码 101 011 101 011 101 011 101 011 10 01 11 10 01 11 10 01 11 10 01 11 将二进制将二进制MortonMortonMortonMorton码变为十进制码变为十进制 1 1 1 1 2 2 2 25 5 5 5 0 0 0 0 2 2 2 24 4 4 4 0 0 0 0 2 2 2 23 3 3 3 1 1 1 1 2 2 2 22 2 2 2 1 1 1 1 2 2 2 21 1 1 1 1 1 1 1 2 2 2 20 0 0 0 32 0 0 4 2 1 39 32 0 0 4 2 1 39 32 0 0 4 2 1 39 32 0 0 4 2 1 39 十进制和二进制的转换十进制和二进制的转换十进制和二进制的转换十进制和二进制的转换 十进制转二进制 十进制转二进制 用用2 2 2 2辗转相除至结果为辗转相除至结果为0 0 0 0 将余数从下向上倒序写将余数从下向上倒序写 就是二进制就是二进制 值值 例如例如302302302302转二进制转二进制 302 2 151 302 2 151 302 2 151 302 2 151 余余0 0 0 0 151 2 75 151 2 75 151 2 75 1