1、目 录摘 要 . IAbstract. II第一章 引言 .11.1 地理信息系统的研究综述 .11.1.1 GIS 概述 .11.1.2 GIS 的发展 .21.2 导航系统综述： .51.2.1 研究方向 .51.2.2 导航系统算法的研究 .61.2.3 导航系统分类的研究 .81.2.4 导航系统技术方面的研究 .81.3 导航系统产品的发展现状 .91.3.1 国外的发展 .91.3.2 国内的发展 .91.3.3 存在的问题 .101.3.4 车辆导航系统的市场潜力 .101.4 同类问题的研究总结 .111.5 本文的研究思路 .12第二章 基于 GIS 的路径规划系统分析 .1
2、32.1 系统功能分析 .132.1.1 地图浏览功能 .132.1.2 路径规划功能 .142.1.3 属性查询功能 .142.1.4 人机接口 .142.2 数字地图分析 .152.2.1 数字地图的数据分析 .152.2.2 系统对数字地图需求分析 .152.2.3 数字地图的内容分析 .152.3 最优路径分析 .162.4 操作系统分析 .16第三章 基于 GIS 的路径规划系统设计 .183.1 系统总体设计 .183.1.1 系统总体设计目标 .183.1.2 系统总体构成 .183.1.3 系统总体模型 .193.1.4 系统模块 .193.1.5 路径规划系统时序图 .213
3、.1.6 系统的功能集成 .213.2 GIS 基础设计 .223.2.1 GIS 开发平台设计 .223.2.2 数字地图的设计 .243.2.3 数字地图数据库设计 .25第四章 路径规划算法 .284.1 线性四叉树和线性八叉树的几个概念和约定 .284.1.1 线性四叉树的邻域 .284.1.2 线性八叉树的邻域 .284.1.3 边界象元 3D 栅格与非边界象元 3D 栅格.294.1.4 相同尺寸和不同尺寸邻域 .294.2 几个简单约定 .304.2.1 对于四叉树编码基准体系的划分 .304.2.2 对于八叉树编码基准体系的划分 .314.3 线性四叉树和线性八叉树层次编码特性
4、剖析 .314.3.1 线性四叉树和线性八叉树的层次编码 .314.4 线性四叉树邻域的确定 .334.4.1 相同尺寸边邻域的确定 .334.4.2 相同尺寸角邻域的确定 .364.4.3 不同尺寸边邻域和角邻域的确定 .384.5 线性八叉树邻域的确定 .384.5.1 边界栅格识别 .384.5.2 相同尺寸面邻域的确定 .394.5.3 相同尺寸边邻域和角邻域的确定 .40第五章 实验与结论 .415.1 实验 .415.2 结论 .42第六章 总结与展望 .436.1 总结 .436.2 展望 .43参考文献 .45致 谢 .50摘 要地理信息系统(GIS)就是一种利用计算机对有关地
5、理、空间位置的数据信息进行存储、处理、查询和显示的计算机支持系统。GIS 的发展始于 60 年代， 90年代以来，随着互联网络的发展及国民经济信息化的推进，地理信息系统作为大的地理信息中心，进入日常办公室和千家万户之中，从面向专业领域的项目开发到综合性城市与区域的可持续发展研究。21 世纪以来，3D 可视化技术发展势头迅猛，已经实现 GIS 环境下的三维建筑物室外室内漫游、信息查询、空间分析、剖面分析和阴影分析等，基于虚拟现实技术的真三维 GIS 将使人们在现实空间外，可以同时拥有一个 Cyber 空间。随着寻径算法已经越来越贴近我们的生活，面向各种用户群的导航仪也会逐渐深入我们的生活。另一方
6、面，随着我国各个城市建设的发展，每个城市地图变的越来越复杂，信息量越来越大，在单一层面的寻径算法已经遇到了性能上的瓶颈。本文较完整地分析了线性四叉树和线性八叉树编码的特性(层次性、方向性、大小性及可压缩性),并利用它发展了一种新的邻域寻找算法。与前人的方法相比,该算法具有理解容易、实现简单、速度快捷的特点,并用实验进行了证实。相信本文提出的邻域寻找算法在三维实体分析、边界的确定、三维拓扑关系的确定及连通性判断等方面具有重要的意义。本文所做工作如下：1) 确定了线性四叉树和线性八叉树编码基准体系的划分标准。2) 确定了线性四叉树和线性八叉树层次编码。3) 确定了线性四叉树和线性八叉树相同尺寸的边
7、邻域、角邻域，不同尺寸的边邻域、角邻域的邻域的寻找。4) 降低了邻域寻找的时间复杂度， 比较适合于嵌入式系统应用。5) 确定了线性四叉树和线性八叉树的面邻域的寻找标准，使用三维数字地图的应用。6) 降低了邻域寻找在连通性判断的时间复杂度。关键词：嵌入式系统；GIS；路径规划；IAbstractGeographic Information System (GIS) is a computer on the geography, spatiallocation information in the data storage, processing, query and display of the
8、computer support system. The development of GIS began in the 90s, is the result ofthe simultaneous development of the computer. Todays geographic informationsystem integrates computer database technology and computer graphics-aided designsoftware. Into the 21st century, as the rapid development the
9、computer hardware andsoftware technology, direct GIS towards practical application, some developedcountries have established a number of professional land information systems andgeographic information systems.With the routing algorithm has become increasingly close to our lives, usergroups will grad
10、ually navigator depth to our daily lives. On the other hand, as Chinasdevelopment in various cities, each city has become more and more complex on themap, increasing the amount of information in a single-level routing algorithm hasencountered a performance bottleneck. In this paper, a more complete
11、analysis of thelinear quadtree and octree encoding linear features (levels, direction, size andcompressibility), and use it to develop a new neighborhood search algorithm.Compared with the previous method, the algorithm is easy to understand, simple,quick speed, and confirmed by experiment. Believe
12、that the proposed neighborhoodsearch algorithm for three-dimensional entities in the analysis, the determination ofthe border, to determine the relationship between three-dimensional topology anddetermine the areas of connectivity is of great significance. In this paper, the work isas follows:1) Det
13、ermine the linear quadtree and octree encoding linear baseline criteria forthe classification system.2) Determine the linear quadtree and linear level octree encoding.3) Determine the linear quadtree and octree linear dimensions while the sameneighborhood, corner neighborhood, different sizes of edg
14、e-neighbor, KokIIneighborhood neighborhood search.4) Reduce the neighborhood to find the time complexity, are more suitable forapplications in embedded systems.5) Determine the linear quadtree and octree linear neighborhood of the surfaceof the search criteria, the use of three-dimensional digital m
15、ap applications.6) Reduce the neighborhood looking for connectivity to determine the timecomplexity.Key words: Embedded System; GIS; Route Planning;III第一章 引言第一章 引言线性四叉树与八叉树都是只记录叶结点的编码,而不记录中间结点的编码及层次关系,由于它比普通四叉树、八叉树大大节省了存储空间，且蕴含有层次特性，因此它在实际工作中得到了广泛的应用。邻域的确定在二维图象分析、三维实体分析、边界的确定及连通性判断等方面具有重要的意义。另外，邻域实质
16、上是一种拓扑关系,邻域的寻找在一定程度上说,也就是在 2D 或 3D 栅格结构中确定物体间的拓扑关系。因此,寻找某一像元、某一 3D 栅格的邻域也就成了克服栅格结构中拓扑关系不清晰及栅格矢量数据结构相互转换难点的一种新思路。因此,邻域寻找成为许多学者研究的重点之一。1.1 地理信息系统的研究综述1.1.1 GIS 概述地理信息系统(GIS)就是一种利用计算机对有关地理、空间位置的数据信息进行存储、处理、查询和显示的计算机支持系统。GIS 的发展始于 60 年代，是计算机同步发展的结果。今天的地理信息系统集成了计算机数据库技术和计算机图形辅助设计软件。在图象处理上比上述两类软件更加全面，即地理信息系统所处理的事物对象具有空间地理特征，也具有统计信息特征。可以说，地理信息系统将空间信息数字化，并使这些信息可视化，通过功能强大的软件，使空间分析直观简明，数据管理便捷高效. 通过地理信息系统的普及和应用，其强大的功能将成为交通信息管理的必备工具，成为科学管理和决策的依据。基于公路数据库基础上的交通地理信息系统 GIS-T 的研究是公路建设管理现代化的基础.它不仅能够适应各种层次管理部门随时了解已有公路现状的需求，同时还能够通过强大的空间分析能力和丰富的图表显示，实现公路养护管理的电子化。1
