第三章数字道路地图.ppt

车载GPS定位技术与应用 第三章 数字道路地图 3.1 导航电子地图概述 导航用电子地图实例 导航电子地图地位及与导航功能的对应关系 地位：导航电子地图在整个车辆导航应用体系中起到核心的作用，针对不同导航应用往往会采用不同规格的电子地图。 通常电子地图由记录实际地物的地理数据和与实际地物相关的标识、修饰信息以及各类附加信息组成。根据应用场合的不同，电子地图的选用也不同。 电子地图数据与导航应用功能之间的关系如下图所示： 地图显示、地址匹配、地图匹配、路径规划、路径引导与数字地图的关系 地图显示是车辆导航系统的重要组成部分，它构成了人机接口的基础，地图显示的成功与否直接影响到用户对产品的印象。地图显示需要依赖数字地图中的道路位置、宽度、级别等属性以及道路附近的各种设施。 地址匹配又称为地理编码，即通过给定的经纬度坐标确定地图上街道的地址，或者相反的过程。需要数字地图的基本属性是道路的名称和地址范围。 地图匹配是利用数字地图的路网信息修正车辆定位模块的位置输出，位置修正的前提是车辆在道路上行驶。 路线规划和路线引导更是与数字地图密切相关，它的几乎所有数据如路网的空间分布、几何坐标、拓扑连接、道路平均时速、转向限制等等来源都是数字地图中的道路信息， 车辆导航系统的数字地图和通用数字地图侧重点不同： 首先，地图要素种类不同。 导航图重点要素：道路 每条路的地理坐标、道路之间的拓扑关系、道路交叉口的交通限制情况等。因此设计导航数字地图数据库时，需要着重考虑道路的表达与组织，同时要有一个高效的访问道路信息的机制，以便可以高效率的进行诸如路线规划，路线引导等功能。对于车辆导航系统来说，应该根据功能需要选择合适的信息进行表达和存储。数字道路地图是导航数字地图数据库的重点和基础，是数字地图的核心内容。 其次，数据层次划分不同。 地图数据层次划分应该强调道路的分层，同时要求能够方便扩展，便于地图的升级维护。 3.2节点一路段数据模型 3.2.1图论基本概念 图(Graph)——图表示的是定义在顶点集上的二元关系。图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集，V(G)中所含元素的个数即顶点数，称为图的阶，记为|V(G)|或n E(G)是边的有限集合，边是顶点的无序对或有序对，E(G)中所含元素的个数称为边数或弧数，记为m 有向图——有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头(终端点) 无向图——无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 邻接 与 关 联—— 对于无向图G= (V ,E) ，若有边(u,v) ∈E，则称u和v互为邻接点或相邻接，且边(u,v) 依附于顶点u和v，或称边(u,v) 与顶点u和v相关联。对于有向图G=(V,A)，若有弧v,v’ ∈ A，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v，且弧v,v ’ 与顶点v和v’，相关联，它从顶点v发出，也称为顶点v的前向关联边，顶点v’的后向关联边。 顶点的度:无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目 某个顶点的度=此顶点的入度+此顶点的出度 带权 图（网络(Network) ）: 图的边或弧可具有与之相关的量化信息，表示从一个顶点到另一个顶点的距离、费用等等。这种与图的边或弧相关的量化信息叫做边或弧的权(Weight)，其中的顶点称为节点(Node)。 路径 从顶点v到顶点w的一条路径是由一个不同顶点组成的序列V={Vi,0，Vi,1，……Vi,n}，满足(Vi,j-1，Vi,j)?E 或 Vi,j-1，Vi,j?E,(1j?n)且其中Vi,0=v， Vi,n=w。 路径长度 沿路径边的数目。 连通：从顶点V到顶点W有一条路径，则V和W是连通的 连通图：图中任意两个顶点都是连通的无向图叫~ 3.2.2节点一路段数据模型的形式化定义 目前的车辆导航系统中，道路网用图的形式来表示，而且大多使用基于节点——路段的数字道路地图数据模型。 道路网 —— 带权有向图，道路以线或折线对象的方式存储，表示为一系列带坐标点的有序集。 包含交叉点的道路被拆分成最基本的路段，使其只在端点处与其他路段相交。拆分后的基本路段对应于路网中的弧