嵌入式电子地图的数据组织与检索算法研究

摘要

随着计算机科学与技术和国内经济的不断发展，嵌入式移动设备(PDA、智能手机、车载终端等)性能有了很大的提高，GIS技术的应用逐步进入到了后PC阶段。同时，GPS导航系统也得到了越来越广泛的应用。由于嵌入式系统在硬件结构、操作系统上与桌面算机系统存在较大差异，较桌面计算机来说；必须考虑CPU运算速度相对较慢、存储空间相对较小、内存共用、可视范围小等特点，设计时会有一些时间、空间上不能平衡的瓶颈问题。在构建GPS导航系统空间数据结构时，也不能简单套用桌面系统的数据结构与实现方法。基于这些问题，本文对空间数据在嵌入式GPS导航设备上的组织和搜索进行了研究。
　　 本文主要研究了空间数据的组织与管理、空间数据的检索，主要做了以下研究：(1)给出了改进的空间数据的格网索引结构；(2)研究了使用嵌入式数据库Sqlite管理空间数据的策略；(3)研究了空间数据的组织结构。本文首先通过分析常用的数据组织方法和空间数据索引算法，如B树、R树、四又树等基本索引算法，给出了结合空间数据组织与空间数据快速检索的格网索引机制，并进行了改进；然后以矢量数据为模型，对空间数据进行了网格划分，并给出了以网格为单位求线段交点的方法。本文以Hilbert空间排列码对网格进行编码，使用嵌入式数据库sqlite对空间数据进行管理，并结合哈希表的搜索思想设计了数据库表。本文建立了面向内存的空间数据组织结构和格网索引机制。在格网索引机制上使用双缓冲技术实现了电子地图的浏览功能；同时以格网索引机制为基础，实现了多重邻接表的路网存储。最后，本文在嵌入式平台上使用A*算法实现路径静态规划，验证了本文格网索引机制的有效性。
　　 本文以嵌入式linux操作系统和Qt/Embedded作为研究的实验平台，使用了开源的嵌入式数据库sqlite，充分利用了免费的资源，与现有的大部分以WINCE操作系统和EVC(Embedded Visual C++)为平台的导航系统相比，节省了开发成本。

目录

文摘

英文文摘

声明

第一章 绪论

1.1 引言

1.2 国内外现状综述

1.2.1 GPS系统

1.2.2嵌入式Linux系统

1.2.3电子地图

1.2.4地图数据组织与检索

1.3 本文的研究内容和章节安排

第二章 电子地图数据组织研究

2.1 电子地图数据介绍

2.1.1 电子地图数据的构成

2.1.2 电子地图数据的数据模型

2.1.3拓扑数据模型

2.2 电子地图数据组织

2.2.1 电子地图数据组织的管理方式

2.2.2电子地图数据组织方法研究

2.3 本章小结

第三章 电子地图数据索引与检索研究

3.1 数据检索与空间索引算法

3.1.1 数据检索

3.1.2空间索引算法研究

3.2格网索引

3.2.1 格网划分

3.2.2网格的Hilbert空间排列码

3.2.3格网索引结构的改进

3.2.4 多级索引的建立

3.2.5格网索引的可行性分析

3.3空间数据检索

3.4本章小结

第四章 电子地图数据预处理

4.1 电子地图数据的压缩

4.2 电子地图数据的格网划分

4.2.1 点的划分

4.2.2路段的划分

4.3 路段的交点

4.4 本章小结

第五章 SQLite在空间数据组织中的应用

5.1 SQLite

5.1.1 SQLite简介

5.1.2 SQLite的数据类型

5.1.3 SQLite的编译和移植

5.2 SQlite数据库的操作

5.3 嵌入式数据库表的设计

5.4 本章小结

第六章 空间数据组织与检索的实现

6.1 开发板上的内存

6.2 空间数据在内存中的组织

6.2.1 空间数据的组织结构

6.2.2空间数据在内存中组织的实现

6.3 空间数据索引的建立

6.3.1 索引结构

6.3.2 空间数据索引结构的实现

6.4 地图浏览技术研究

6.4.1 地图动态显示

6.4.2双缓冲技术

6.5 本章小结

第七章 路网组织研究

7.1 路网的组织结构

7.2 路网的存储结构

7.3 路网的邻接多重表存储

7.4系统测试数据

7.5 本章小结

第八章 总结与展望

参考文献

致 谢

攻读学位期间参加的科研项目和成果