基于最小边界圆和最小包围扇形的空间索引方法

摘要

空间数据库被广泛地应用于计算机视觉、计算机辅助设计、计算几何和地理信息系统等领域。在空间数据库中，空间数据库索引技术是空间数据库应用中的一个核心问题。最近几十年，对空间索引的研究引起了国内外学者的足够重视，许多空间索引结构与方法相继提出，但这些方法都有其各自的局限性。 本文首先全面介绍了空间数据索引技术。同时，对空间数据的组成、空间目标查询和空间目标近似技术做了详细描述。通过对空间数据库结构特点和空间检索过程的分析，寻求改善空间数据库性能的新索引结构的突破口。 然后，从数据库的空间占有率和检索速度两方面寻求改进，提出基于最小边界圆空间索引方法，并详细地介绍了基于最小边界圆空间索引结构的构造原理，针对基于最小边界圆空间索引结构的特点给出了查询、结点插入和删除算法。同时，对插入或删除结点时产生外溢的情况，提出了结点分裂算法。基于最小边界圆的索引结构要求更少的存储空间，而且检索精度和速度比较高。 在空间方位查询领域，许多空间数据库索引方法不能够满足其特殊的需要，本文针对空间方位查询的特点提出了基于最小包围扇形空间索引方法，并针对基于最小包围扇形空间索引结构提出与之相适应的查找、结点插入和结点删除算法。

目录

文摘

英文文摘

声明

第1章 绪论

1.1 研究目的及意义

1.2 国内外研究现状分析

1.3 课题来源

1.4 本文主要研究内容

1.5 本章小结

第2章 空间数据库索引技术

2.1 空间数据组织

2.1.1 空间数据特征

2.1.2 空间数据模型

2.2空间目标查询

2.3 目标近似技术

2.4 基于目标近似的空间检索过程

2.5 空间索引

2.5.1 空间索引的需要

2.5.2 空间索引的设计原则

2.5.3 空间索引技术

2.6 本章小结

第3章 基于最小边界圆空间索引结构

3.1 多边形最小边界圆的算法

3.1.1 多边形最小边界圆的算法思路

3.1.2 多边形最小边界圆的算法描述

3.1.3 多边形最小边界圆算法分析

3.1.4 构造简单多边形顶点凸壳算法

3.1.5 凸多边形直径算法

3.2 基于最小边界圆的索引结构的构造

3.2.1 圆求并算法

3.2.2 基于最小边界圆索引结构的构造算法

3.3 基于最小边界圆的索引结构的查找算法

3.3.1 查找算法

3.3.2 圆求交判断算法

3.3.3 查找举例

3.4 基于最小边界圆的索引结构的插入算法

3.4.1 算法思路

3.4.2 算法描述

3.5 基于最小边界圆的索引结构的删除算法

3.5.1 算法思路

3.5.2 算法描述

3.5.3 算法分析

3.6 结点分裂算法

3.6.1 算法思路

3.6.2 算法描述

3.7 本章小结

第4章 基于最小包围扇形的空间索引结构

4.1 多边形最小包围扇形的算法

4.1.1 覆盖多边形顶点集S的最小扇形算法

4.1.2 直角坐标转极坐标算法

4.2 基于最小包围扇形的索引结构的构造

4.2.1 扇形求并算法

4.2.2 基于最小包围扇形索引结构的构造算法

4.3 基于最小包围扇形的索引结构的查找算法

4.3.1 查找算法

4.3.2 扇形求交判断算法

4.3.3 查找举例

4.4 基于最小包围扇形的索引结构的插入算法

4.4.1 算法思路

4.4.2 算法描述

4.5 基于最小包围扇形的索引结构的删除算法

4.5.1 算法思路

4.5.2 算法描述

4.6 分裂结点算法

4.6.1 分裂结点算法的算法思路

4.6.2 分裂结点算法的算法描述

4.7 本章小结

结论

参考文献

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

致谢