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

摘要

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

目录

文摘

英文文摘

声明

第1章绪论

1.1研究目的及意义

1.2国内外研究现状分析

1.3基于凸多边形逼近的空间索引的应用

1.4课题来源

1.5本文主要研究内容

1.6本章小结

第2章基础知识

2.1空间查询

2.1.1目标近似

2.1.2空间查询

2.2常用的空间索引

2.2.1 R-树

2.2.2 CP-树

2.3关于R树的一些基本知识

2.3.1 R树的概念及其索引结构

2.3.2 R-树查找

2.3.3 R树的插入

2.3.4 R-树的删除

2.4空间聚类

2.4.1空间聚类的定义

2.4.2空间聚类的分类

2.4.3k-均值聚类算法

2.4.4k-均值聚类的思想

2.5本章小结

第3章 凸多边形的概念、性质及其应用

3.1凸壳的定义及其基本性质

3.2求平面点集凸壳的算法

3.3求平面点集凸壳的一种新算法

3.3.1相关定义

3.3.2算法描述

3.3.3算法的时间复杂度

3.3.4结束语

3.4求任意两个相交凸多边形的交与并的算法

3.4.1相关定义

3.4.2算法描述

3.4.3时间复杂度分析

3.4.4结束语

3.5本章小结

第4章基于凸多边形逼近的空间索引

4.1基于凸多边形逼近(二叉树)的空间索引结构

4.1.1空间凸多边形的聚类划分

4.1.2二叉树的性质及其索引结构的建立

4.1.3二叉树的查找

4.1.4二叉树结点的插入

4.1.5二叉树结点的删除

4.1.6 CP-树的索引结构

4.1.7 CP-树的生成运算

4.2基于凸多边形逼近(四叉树)的空间索引结构

4.2.1基于四叉树的空间索引

4.2.2四叉树的查找及其插入

4.2.3四叉树的删除

4.3本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢