学位论文 > 优秀研究生学位论文题录展示

空间关系的研究和实现

作　者: 赵红超
导　师: 唐志敏
学　校: 中国科学院研究生院（计算技术研究所）
专　业: 计算机系统结构
关键词: 地理信息系统空间关系 BO算法 BMN算法维度扩展的9交矩阵空间关系判断函数空间关系获取获取函数空间关系的模式串匹配算法织女星地理信息系统
分类号: P208
类　型: 博士论文
年　份: 2006年
下　载: 598次
引　用: 11次
阅　读: 论文下载

内容摘要

随着地理信息系统(GIS)的发展和普及,作为GIS基础的空间数据库已经得到人们足够的重视和发展。空间关系是空间数据库和GIS分析的一个重要的方面,为此,很多学者对其进行了大量的研究,产生了关于空间关系的一个相对完备的数学基础-维度扩展的9交矩阵:DE-9IM。OpenGIS协会(OGC)根据这个数学基础,定义了空间关系在简单地理几何要素中的抽象规范和实现规范。本文在DE-9IM模型和OpenGIS规范的基础上,以扩展的BMN交点算法为支撑,利用模板元编程的特性,具体而微的设计并实现了空间关系的的系统架构,以及适用于所有空间关系函数的统一算法流程。在此基础上,本文实现了OGC规定的所有空间关系的函数接口。本文通过把空间关系函数划分为空间关系判断函数和空间关系获取函数,设计并实现了空间关系判断函数的模式串匹配算法,使得这类函数的实现更加的直接、简便和高效。利用BMN交点扫描算法本身的特点,本文设计并实现了点线在多边形内外侧判定的算法,极大的降低了算法的时间复杂度。本文关于空间关系实现的架构和算法已经在实际的VegaGIS系统中成功运用,并取得了良好的效果。

全文目录

摘要  4-13
第1章引言  13-30
  1.1 地理信息系统  13-14
  1.2 空间关系  14-18
    1.2.1 空间查询语言（Spatial SQL）  14-15
    1.2.2 拓扑关系  15-16
    1.2.3 符号化表示  16-17
    1.2.4 9 交矩阵（91M）  17-18
    1.2.5 维度扩展的9 交矩阵（DE-91M）  18
  1.3 OpenGIS规范  18-26
    1.3.1 OGC  18-19
    1.3.2 OpenGIS规范  19-22
    1.3.3 空间关系的形式化描述  22-26
  1.4 交点算法  26-27
  1.5 本文的贡献  27-29
  1.6 论文的组织  29-30
第2章空间关系实现的基础设施  30-54
  2.1 交点算法  30-38
    2.1.1 平面扫描技术  30-31
    2.1.2 BO算法  31-33
    2.1.3 BMN算法  33-36
    2.1.4 改进的BMN算法  36-38
    2.1.5 BMN算法的复杂度  38
  2.2 辅助性的结论  38-42
    2.2.1 最小包围盒技术  38-39
    2.2.2 INum结论  39-41
    2.2.3 局部关系和整体关系  41-42
  2.3 算法流程  42-44
  2.4 输入线段的优化  44-45
  2.5 语言特性  45-46
    2.5.1 多态模式的选择  45
    2.5.2 二次分派  45-46
  2.6 基础设施的代码实现  46-54
    2.6.1 基本结构和函数  46-48
    2.6.2 同质关系和异质关系  48
    2.6.3 统一的算法流程  48-49
    2.6.4 空间关系接口  49-51
    2.6.5 空间关系判断函数和空间关系获取函数  51
    2.6.6 空间关系判断函数的模式匹配实现法  51-52
    2.6.7 getPartRelation的完备性  52-54
第3章点型关系的实现  54-63
  3.1 点点关系  54-55
    3.1.1 点点关系的BMNAlgo实现  54
    3.1.2 准备工作  54-55
    3.1.3 空间关系判断函数的实现  55
    3.1.4 空间关系的获取函数的实现  55
    3.1.5 复杂度分析  55
  3.2 点线关系  55-57
    3.2.1 准备工作  55-56
    3.2.2 空间关系判断函数的实现  56
    3.2.3 空间关系获取函数实现  56-57
    3.2.4 复杂度分析  57
  3.3 点面关系  57-60
    3.3.1 优化的点在多边形内外侧的判定法  57-58
    3.3.2 准备工作  58-59
    3.3.3 空间关系判断函数实现  59
    3.3.4 空间关系获取函数实现  59
    3.3.5 复杂度分析  59-60
  3.4 点型关系实现的总结  60-63
    3.4.1 点型关系的模式串  60-61
    3.4.2 辅助性的结论  61-62
    3.4.3 最小包围盒技术和自相交检验  62
    3.4.4 最优决策树  62-63
第4章线型关系的实现  63-77
  4.1 线线关系  63-67
    4.1.1 线边界的确定  63
    4.1.2 准备工作  63-64
    4.1.3 线线getPartRelation的实现  64-65
    4.1.4 空间关系判断函数的实现  65-66
    4.1.5 isOverlap的实现  66
    4.1.6 空间关系获取函数实现  66-67
    4.1.7 复杂度分析  67
  4.2 线面关系  67-74
    4.2.1 准备工作  67-70
    4.2.2 线段在多边形内外侧的判定  70-71
    4.2.3 线面getPartRelation的实现  71-73
    4.2.4 空间关系判断函数实现  73-74
    4.2.5 空间关系获取函数实现  74
    4.2.6 复杂度分析  74
  4.3 线型关系实现的总结  74-77
    4.3.1 局部关系的确定  74-75
    4.3.2 辅助性的结论  75
    4.3.3 线型关系的模式串  75-77
第5章面型关系的实现  77-83
  5.1 准备工作  77-79
  5.2 面面getPartRelation的实现  79-80
  5.3 空间关系判断函数的实现  80
  5.4 isOverlap的实现  80-81
  5.5 空间关系获取的实现  81
  5.6 复杂度分析  81-82
  5.7 面面关系实现的总结  82-83
第6章结束语  83-87
  6.1 本文工作的总结  83-85
    6.1.1 扩展的BMN交点算法  83
    6.1.2 空间关系判断函数的模式串匹配算法  83-84
    6.1.3 辅助性的结论  84
    6.1.4 统一的算法流程  84-85
    6.1.5 空间关系的具体实现  85
  6.2 本文实现方法的特点  85-86
  6.3 下一步的研究方向  86-87
参考文献  87-92
附录  92-103
致谢  103-104
作者简历  104

空间关系的研究和实现

内容摘要

全文目录

相似论文