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

基于凸多边形逼近的空间索引方法研究

作　者: 王三
导　师: 刘润涛
学　校: 哈尔滨理工大学
专　业: 应用数学
关键词: 凸多边形空间索引 R-树二叉树四叉树
分类号: TP391.41
类　型: 硕士论文
年　份: 2009年
下　载: 85次
引　用: 0次
阅　读: 论文下载

内容摘要

一般来说,GIS所处理的空间目标具有不规则的形状,若基于它们的精确位置和扩展来实现某些空间操作(如相邻,包含等),其计算量会非常庞大。因此,一些近似的方法,如最小约束矩形法等,常常被用来表达具有不规则形状的空间目标。空间目标近似表达方法可以简化某些空间查询过程,避免一些不必要的计算,从而可以有效地提高查询效率。本文采用凸多边形(convex polygon)来近似表达空间目标,凸多边形是d维欧氏空间Rd中一个非空、有限的凸集。对Rd中的一个集合,如果这个集合中的任意2个点,连接这2个点的线段被完全包含在该集合中,则该集合被称作凸集。研究表明,对于任意一个空间目标而言,这个目标对应的凸多边形必然包含在该目标对应的最小约束矩形中。因此,凸多边形能够更精确地定义空间目标的位置,减少不同空间目标之间的重叠区域,从而可以更有效地实现空间查询。首先,本文分析了经典的R-树查询方法,以及R*-树,R+-树的索引结构及其各自的特点和缺点。其次,进一步的研究求任意多边形的的凸包的最优算法,提出了求平面点集凸壳的一种新算法,求任意两个凸多边形交与并的凸壳新算法,分析其时间复杂度。此外,研究了基于凸多边形的索引结构树:CP-树,研究CP-树的索引结构,以及搜索运算和生成运算。最后,建立一种新的基于凸多边形逼近的二叉树,四叉树结构,提出其查询,插入以及删除算法。基于凸多边形逼近的空间索引方法,减少了不同空间目标之间的重叠区域,从而可以更有效地实现空间查询。

全文目录

摘要  5-6
Abstract  6-10
第1章绪论  10-16
  1.1 研究目的及意义  10-11
  1.2 国内外研究现状分析  11-14
  1.3 基于凸多边形逼近的空间索引的应用  14-15
  1.4 课题来源  15
  1.5 本文主要研究内容  15
  1.6 本章小结  15-16
第2章基础知识  16-26
  2.1 空间查询  16-18
    2.1.1 目标近似  16-17
    2.1.2 空间查询  17-18
  2.2 常用的空间索引  18-19
    2.2.1 R-树  18
    2.2.2 CP-树  18-19
  2.3 关于R 树的一些基本知识  19-22
    2.3.1 R 树的概念及其索引结构  19-21
    2.3.2 R-树查找  21-22
    2.3.3 R 树的插入  22
    2.3.4 R-树的删除  22
  2.4 空间聚类  22-25
    2.4.1 空间聚类的定义  22-23
    2.4.2 空间聚类的分类  23
    2.4.3 k-均值聚类算法  23-24
    2.4.4 k-均值聚类的思想  24-25
  2.5 本章小结  25-26
第3章凸多边形的概念、性质及其应用  26-39
  3.1 凸壳的定义及其基本性质  26-29
  3.2 求平面点集凸壳的算法  29-30
  3.3 求平面点集凸壳的一种新算法  30-33
    3.3.1 相关定义  30-31
    3.3.2 算法描述  31-33
    3.3.3 算法的时间复杂度  33
    3.3.4 结束语  33
  3.4 求任意两个相交凸多边形的交与并的算法  33-38
    3.4.1 相关定义  34
    3.4.2 算法描述  34-37
    3.4.3 时间复杂度分析  37-38
    3.4.4 结束语  38
  3.5 本章小结  38-39
第4章基于凸多边形逼近的空间索引  39-54
  4.1 基于凸多边形逼近（二叉树）的空间索引结构  39-47
    4.1.1 空间凸多边形的聚类划分  39-40
    4.1.2 二叉树的性质及其索引结构的建立  40-42
    4.1.3 二叉树的查找  42-43
    4.1.4 二叉树结点的插入  43-44
    4.1.5 二叉树结点的删除  44-45
    4.1.6 CP-树的索引结构  45-46
    4.1.7 CP-树的生成运算  46-47
  4.2 基于凸多边形逼近（四叉树）的空间索引结构  47-53
    4.2.1 基于四叉树的空间索引  47-49
    4.2.2 四叉树的查找及其插入  49-51
    4.2.3 四叉树的删除  51-53
  4.3 本章小结  53-54
结论  54-55
参考文献  55-59
攻读硕士学位期间发表的学术论文  59-60
致谢  60

基于凸多边形逼近的空间索引方法研究

内容摘要

全文目录

相似论文