随着计算机科学与技术和国内经济的不断发展,嵌入式移动设备(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++)为平台的导航系统相比,节省了开发成本。