GPS车载导航系统路径规划的研究(4)

江苏大学 学士学位论文

存工作空间；否则，该地图将没有被真正保存。

3．3．6 布局与资源

（1）把一个或者多个地图放置在布局窗口中，并辅以其他的地图要素如图名、图例、地图比例尺等，就成为布局。同地图一样，布局的保存也依赖与工作空间文件的保存；

（2）资源包括：符号、线形、填充。

3．3．7 记录集

记录(Record) 是处理和存储实体信息的基本单位，记录的集合叫记录(Recordset)。

SuperMap 空间数据组织和存储方式的基本单位仍然是记录。每个空间几何对象对应一条记录，这条记录中既有属性字段（或称属性列），又有几何字段。一般地，记录集是数据集的全部或者部分记录的集合。记录集通常是把数据集中的记录按照某种条件筛选出来的。可以是对行的筛选，也可以是对列（字段）的筛选，或者二者结合起来。如果在记录集中添加、修改或删除某个记录，数据集中的数据将发生相应的变化。

3．3．8 上述概念之间的关系

（1） 工作空间和数据源的关系

? 一个工作空间中可以有多个数据源，数据源对应一个空间数据文件或一个空间数据库； ? 当前工作空间只有一个，打开另一个工作空间必须先关闭原来的工作空间。 （2） 数据源和数据集的关系

? 一个数据源可以有多个或多种类型的数据，一个或多个数据集可以组成一个或多个数据源；

? 同一个数据集中只能存储一种类型的数据，如点对象。 （3） 工作空间和地图、布局的关系

? 地图和布局都保存在工作空间文件中，保存地图和布局后，如没有保存工作空间，结果将不被保存；

? 如果工作空间中没有数据源，则相应的地图和布局将没有数据。 （4） 数据集和地图的关系

? 数据集存储于数据源（文件或数据库）中，地图存储于工作空间文件（*.SMW）中； ? 数据集是地图的重要数据来源，没有数据集中的数据对象，就不能显示地图； ? 数据集中只有数据内容，地图除了数据内容之外，还有数据的显示风格等； ? 地图会随着数据集的改变而动态更新。 （5） 数据集和图层的关系

11

江苏大学 学士学位论文

? 数据集保存在数据源文件或数据库中，图层的保存是以地图的方式保存的；

? 一个图层对应着一个数据集，同一个数据集可以被多次添加到不同的地图窗口中，而且可以赋予不同的显示风格。因此，同一个数据集可以对应不同地图窗口的多个图层。

3．4 SuperMap Objects 空间数据引擎

SuperMap Objects 采用独特的多源空间数据无缝集成技术，提供了多种空间数据引擎。在实际应用中，可以根据应用系统需求，选择一个或者多个合适的数据引擎。SuperMap Objects提供的空间数据引擎本有：（1）SDB 引擎（2）DGN 引擎（3）DWG 引擎（4）MDB 引擎（5）SDX for SQL Server 引擎（6）SDX for Oracle 引擎（7）SDX for Oracle Spatial 引擎（8）SDX+ for Oracle 引擎。

设计采用了SDX for SQL Server 引擎。SQL Server 引擎是一个基于大型数据库SQL Server 的纯关系数据库空间引擎。实现了空间数据和属性数据的无缝组织，支持大数据量管理，支持多用户共享读写访问，支持短事务和长事务处理，有严格的权限管理。SQL Server 引擎适合建立大型空间数据应用。

12

江苏大学 学士学位论文

第四章 路径规划子系统的分析与设计

前面介绍了车载导航系统的概念、体系结构以及地理信息系统的相关概念和原理，并简单介绍了SuperMap地理信息系统的技术与功能，本章主要介绍在本课题中设计的路径规划子系统的运行环境、总体结构、主要功能和路径规划算法的分析与设计。

4. 1 系统简介

路径规划是指在旅行前或旅行中为驾驶员提供参考行驶路线和驾驶引导的过程,是车辆定位与导航系统的基本功能之一。路径规划所要实现的是：用户输入任意起点、终点，在电子地图上规划出一条从起始点到达终点的最佳路径。针对陆地车辆导航的不同要求,在路径规划中可采取多种优化标准,如最短距离、最少行驶时间或收费等. 但无论使用哪种标准,路径规划最终都可以归结为在特定道路网络中搜索总代价最小的目标路径问题。车辆导航系统中的路径规划问题从本质上说属于图论中的最短路问题。

本系统以SuperMap地理信息系统作为开发平台，Delphi7.0作为开发工具，通过调用SuperMap objects控件SuperMap和Superworkspace,来实现相应的功能，它主要包括两大功能：

⑴地图信息处理功能：选择菜单栏中的“地图操作”的下拉菜单的选项，或选择工具栏上的快捷按扭，然后在地图上点击，可以完成地图的放大、缩小、漫游和全副显示功能。

⑵路径规划功能：选择菜单栏中的“路径分析”的下拉菜单的“起始点”选项，或选择工具栏上的快捷按扭

，在地图上任意点击选择起始点（为红色标记点），然后选择菜单栏中

，在地图上任

的“路径分析”的下拉菜单的“终止点”选项，或选择工具栏上的快捷按扭意点击选择终止点（为蓝色标记点），然后点击快捷按扭

，或单栏中的“路径分析”的下拉

菜单的“求最短路径”选项，可以根据用户刚在地图上选取的任意目标，进行计算，按要求规划从出发地到目的地的最短路径，并用红色标出路径，显示输出结果。

系统主界面如图4.1：

13

江苏大学 学士学位论文

图4.1 系统界面图

4. 2 系统体系结构设计

本课题设计的路径规划子系统的主要功能是进行基于网络的最短路径的选择以及显示，系统按功能划分为地理信息交互平台、最短路径算法、地图显示输出几个模块。

a 地理信息系统交互平台：地理信息系统交互平台是系统主要的接口平台，主要提供系统与用户之间以及系统各个模块之间的交互功能。电子地图的显示、规划结果的显示等。

b 路径规划模块：对网络进行最短路径选择计算，即：当用户在地图上任意选择起点、终点，规划出一条从起始点到达终点的最短路径。

c 地图显示输出模块：对地图进行选择、放大、缩小、漫游、以及刷新等操作。 系统模块结构图如图4.2。

路径规划子系统 地理信息系统交互平台 路径规划算法模块 地图显示输出模块 图4.2 系统模块结构图

4． 3 路径规划算法的设计

4．3．1 现有的路径规划算法

最短路径问题的解决方法很多，包括图论基本方法、启发式搜索方法、动态规划方法、神

14

江苏大学 学士学位论文

经网络方法等。传统的最短路径算法主要有Floyd算法、矩阵算法和Dijkstra算法等，其中Floyd算法是用于计算网络中所有的点对之间的最短路径；矩阵算法主要用于计算网络中所有的点对中的最短路径，并且可以同时求出次短路径；Dijkstra算法用于计算一个源节点到所有其他节点的最短路径，有较高的应用价值。 三种算法的比较如表4.1所示：

表4.1 三种路径规划算法的比较

适用范围 功能 Dijkstra算法 有向或无向图 每次只能求出一个源点Floyd算法 有向或无向图 求得所有顶点间的最O(n3) 不能 矩阵算法 无向图，改进后可用于有向图 求得所有顶点间的最短路径 O(n4) 能 至其余各点的最短路径 短路径 时间复杂度 O(n2) 次短路径

Dijkstra算法是求指定点到其余各点得最短路径，很容易将其改造成指定点到指定点得最短路径算法，算法在执行过程中只需记录每个顶点的标号和它的紧前顶点，因此其空间复杂度为O(n)（n为顶点数）；Dijkstra 算法虽然只能求出指定点对之间的最短路径，但该算法简单，算法数量级为O(n2)，所以本课题选用Dijkstra 算法。

不能 [6]

[5]

4．3．2 经典Dijkstra算法

对于图G = ( V , E) ,V 是包含n 个顶点的顶点集, E 是包含m 条弧的弧集, ( v ,w) 是E 中从v至w 的弧, c ( v , w) 是弧( v , w) 的非负权值,设s为V 中的顶点, t 为V 中可由s 到达的顶点,则求解从s 至t 的具有最小弧权值和的最短路径搜索，过程可以实现如下：

1) 将V 中的顶点分为3 类:已标记点、未标记点和已扫描点,将s 初始化为已标记点,其他顶点为未标记点. 为每个顶点v 都建立一个权值d和后向顶点指针p ,并将d 初始化如下: d ( v) = 0 ,v = s ; d ( v) = ∞, v ≠s .

2) 重复进行扫描操作:从所有已标记点中选择一个具有最小权值的顶点v 并将其设为已扫描点,然后检测每个以v 为顶点的弧( v , w) ,若满足d ( v) + c ( v ,w) < d ( w) ,则将顶点w 设为已标记点,并令d ( w) = d ( v) + c ( v ,w) , p ( w) = v.

3) 若终点t 被设为已扫描点,则搜索结束.由t 开始遍历后向顶点指针p 直至起点s ,即获得最短路径解.

4．3．3 改进 Dijkstra 算法

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库GPS车载导航系统路径规划的研究(4)在线全文阅读。