基于线段的平面多边形最近邻查询

论文摘要

空间数据库是近年的热点研究领域,它在地理信息系统(GIS),计算机辅助设计与制造(CAD/CAM),多媒体系统以及数字地球方面都有着广泛的应用。空间数据近邻查询作为空间数据库在现实生活中的具体应用,受到人们越来越多的关注。目前空间数据近邻查询主要有点近邻查询,反向近邻查询,K近邻查询,约束近邻查询,组近邻查询以及近对近邻查询等等。这些近邻查询的查询粒度都是以点为单位的,即将物体抽象成点,再根据点与点之间的距离公式求出距查询点最近的目标。论文的基本研究内容是实现空间数据近邻查询。不同之处在于查询粒度的不同,论文是基于查询粒度为线段的近邻查询,目的是实现用查询粒度为点的近邻查询所不能实现的功能。论文的主要研究方法为:通过对现实物体进行一定的抽象,将一定的空间物体转化为多边型和线段。根据Hilbert值生成相应的R树,利用空间索引技术和分支限界规则,筛选出不符合条件的结点,对符合条件的结点,将结点中的MBR与查询线段的MBR的关系转化为线段与线段的位置关系,通过引入线段的直接影响区域概念,把线段与线段之间的位置关系分成十种情况,对不同情况进行区分对待,根据研究得到相关规则和结论,获得所有可能最近邻,再通过比较得到结果。论文的创新点为:将近邻查询的查询粒度由一维的点提高到二维的线段。其理论意义在于:可以实现无法抽象成点的物体(如河流,公路,高压线等等)的最近邻查询。其实际意义在于具体应用。比如,高速公路两侧的最近邻物体;高压线路两侧的最近邻物体;距离海洋航道的最近的岛屿等等。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究目的和意义
• 1.2 研究现状
• 1.2.1 点与点的近邻查询
• 1.2.2 点与线的近邻查询
• 1.3 课题的来源及研究内容
• 1.3.1 课题来源
• 1.3.2 研究内容
• 第2章 基础知识
• 2.1 空间数据库索引技术
• 2.2 文件传输方式
• 2.3 R 树的基本知识
• 2.3.1 R 树的算法
• 2.3.2 构建R 树的方法
• 2.4 基于空间索引的距离计算
• 2.5 线段相交的判断方法
• 2.6 空间连接
• 2.7 空间查询算法
• 2.8 空间数据查询
• 2.9 空间数据查询优化
• 2.10 基于属性特征的空间数据近邻查询
• 2.11 本章小结
• 第3章 空间物体的表示
• 3.1 空间物体之间的空间关系
• 3.2 空间物体在索引结构中的表示
• 3.3 空间物体的点表示
• 3.3.1 规则物体的点表示
• 3.3.2 复杂形状物体的点表示
• 3.4 空间物体的线段表示
• 3.5 空间数据点与线段的存储
• 3.5.1 点的表存储
• 3.5.2 线段的表存储
• 3.6 空间物体的R 树构建
• 3.6.1 空间物体在动态环境中的R 树构建
• 3.6.2 点与线段在静态环境中的R 树构建
• 3.7 本章小结
• 第4章 线段最近邻查询
• 4.1 线段最近邻的定义
• 4.2 点到线段的最近距离
• 4.3 线段到线段的最近距离
• 4.3.1 判定点q 是否位于area（L）中的方法
• 4.3.2 线段与线段不相交时的位置关系
• 4.4 基于两条线段不相交的有关定理
• 4.5 本章小结
• 第5章 线段近邻查询算法
• 5.1 R 树中MBR 与线段的MBR 的筛选规则
• 5.2 基于MINDIST 的筛选规则
• 5.3 判断线段与线段的位置关系的算法描述
• 5.3.1 线段与线段相交的判断算法描述
• 5.3.2 线段与线段不相交时位置关系的确定算法描述
• 5.4 查询线段与被查询线段的最近距离的算法描述
• 5.5 查询线段在R 树中的遍历算法描述
• 5.6 本章小结
• 第6章 实验结果
• 6.1 实验环境
• 6.2 点与线段最近距离计算方法的比较
• 6.3 点与线段的最近距离计算方法的实验数据
• 6.4 线段与线段最近距离计算方法的比较
• 6.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢