单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,车载GPS定位技术与应用,第三章数字道路地图,3.1 导航电子地图概述 3.2 节点-路段数据模型 3.3 适合车辆导航的路段链数据模型 3.4 数字地图的分层组织 3.5 导航数据的组织方法,3.1 导航电子地图概述,导航电子地图概述,地图正北，车头显示切换,比例尺的切换,系统时间,地图缩小,地图放大,切换到汽车当前位置,各种地理查询信息,地图2D、2.5D切换,显示当前目的地,GPS，陀螺仪状态提示,地图中心点标识符,城市地图,导航用电子地图实例,导航电子地图概述,导航系统组成,导航电子地图地位及与导航功能的对应关系,地位：导航电子地图在整个车辆导航应用体系中起到,核心的作用,，针对不同导航应用往往会采用不同规格的电子地图通常电子地图由记录实际地物的地理数据和与实际地物相关的标识、修饰信息以及各类附加信息组成根据应用场合的不同，电子地图的选用也不同电子地图数据与导航应用功能之间的关系如下图所示：,导航电子地图概述,车 辆 定 位,地 图 显 示,路 径 规 划,路 线 导 引,地 址 定 位,实时交通数据处理,POI(信息点),车辆导航系统功能,道路形状数据库,背景数据,拓扑数据,属性数据,电子地图数据库,电子地图数据与导航应用功能之间的关系,地图显示、地址匹配、地图匹配、路径规划、路径引导与数字地图的关系,地图显示,是车辆导航系统的重要组成部分，它构成了人机接口的基础，地图显示的成功与否直接影响到用户对产品的印象。
地图显示需要依赖数字地图中的道路位置、宽度、级别等属性以及道路附近的各种设施地址匹配,又称为地理编码，即通过给定的经纬度坐标确定地图上街道的地址，或者相反的过程需要数字地图的基本属性是道路的名称和地址范围地图匹配,是利用数字地图的路网信息修正车辆定位模块的位置输出，,位置修正的前提是车辆在道路上行驶路线规划,和,路线引导,更是与数字地图密切相关，它的几乎所有数据如路网的空间分布、几何坐标、拓扑连接、道路平均时速、转向限制等等来源都是数字地图中的道路信息，,车辆导航系统的功能与数字道路地图特征的关系,车辆导航系统的数字地图和通用数字地图侧重点不同,：,首先，地图要素种类不同,导航图重点要素：道路 每条路的地理坐标、道路之间的拓扑关系、道路交叉口的交通限制情况等因此设计导航数字地图数据库时，需要着重考虑道路的表达与组织，同时要有一个高效的访问道路信息的机制，以便可以高效率的进行诸如路线规划，路线引导等功能对于车辆导航系统来说，应该根据功能需要选择合适的信息进行表达和存储数字道路地图是导航数字地图数据库的重点和基础，是数字地图的核心内容其次，数据层次划分不同地图数据层次划分应该强调道路的分层，同时要求能够方便扩展，便于地图的升级维护。
车辆导航系统的功能与数字道路地图特征的关系,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,为弧头,(终端点),无向图,无向图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),，若有弧 A，则称顶点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,或 E,(1节点 路段,(2),环岛型交叉口,环岛 型 交 叉口是一种特殊的交叉口，在该交叉口内部，车辆必须单向行驶，绕环岛逆时针旋转行驶，如图,3.2(c).,(3),快速路的出入口,快速 路,(,含高速路、高架桥等,),的出入口包含了交叉信息和出入口，它既要描述正常快速路的行驶路线，也要确定道路出入口位置，如图,3.2(d).,(4)U,型转弯口，,如图,3.2(e),。
路网基本要素节点 路段,（,2.2,）道路连接点,道路连接点，,用于标定道路方向的改变以及同一道路发生属性描述变化的转折点,，复杂道路通过增加道路连接点来进行分段例如在,C,F,G,使道路属性发生改变影响车辆导航功能实现的点,，它们是道路连接点2.3,）各种复杂的立交桥,，应将各个,匝道的出入口,定义为节点,，使得计算的行车路线能清楚的表达桥内的行驶，使出行者了解各种转向操作的具体行走方法路网基本要素节点 路段,图3.3,3,、典型示例,如图,3.4,所示是城市快速路中主、辅路并行，且存在非互通式立交桥的情形这种情况下，主、辅路用两条平行的路段表示，快速路的出口,P,和入口,Q,、,W,为下层交叉点辅路与相交道路,EF,的平面交叉口都形成节点，而主路在立交处则没有形成节点图,3.4实际道路网络及对应的节点一路段模型,路网基本要素节点 路段,4,、组成要素的属性,4.1,节点的属性数据应包括,:,（,1,）节点编号、（,2,）节点坐标、（,3,）灯控路口的时间配时、,（,4,）节点的车辆行驶平均时间延误、（,5,）交叉口转向限制等4.2,车辆导航系统路段属性数据应该至少包含以下内容,:,(1),路段编号,;(2),起点、终点编号；,(3),路段名称,;,(4),路段长度,;(5),路段宽度,;(6),道路等级,(,高速路，国道，省道，县道，城市一级路，二级路，三级路,);,(7),车辆平均时速,:(8),路面建筑状况,(,好、一般、差,);,(9),最高速度限制,;(10),是否收费与收费标准,(11),实时路况信息,(,交通事故、堵塞程度等,);(12),允许车辆类型,路网基本要素节点 路段,导航数据库中节点要素说明实例,导航数据库中路段要素说明,3.2.4,路网连通性表达,路段之间的连接关系的表达即,路段通过节点建立拓扑关系,，建立拓扑关系的路网可以方便的执行地图匹配、路线规划等道路计算。
车辆导航系统中连通性与实际道路网络中的有所不同：,数字道路地图可以用带权有向图的形式来描述，,图论意义上的连通性,描述了节点之间的邻接关系，这种节点之间的,连通性具有传递性,，即节点,n1,与,n2,连通，,n2,与,n3,连通，那么,n1,一定与,n3,连通但在实际的道路网络中，,交通管理部门经常会采取一些交通管理措施，,如单向交通、转向限制等，这种情况下，,节点之间的连通性不再具有传递性，,从而那些直观上连通的路线在实际交通行为中是不可达的例如，,从花园北路到北航东南门路口,，从图中直观地看是连通的，但由于北航路口的东进口禁止左转，使得在实际交通行为中不能由花园北路左转到学知路口，因此这条路线不可达解决方法一：增加虚边法,基本思想：,在具有转向限制的节点处增加多个虚拟节点和虚拟边，将每一种允许的转向行为表示出来设在路网,Nr,中，节点,vi,，具有,n,(i),个后继和,n(i),个前驱，那么必须将该节点拆分为,n,(i),十,n(i),个虚节点，分别代表该交叉口处的,n,(i),个出口和,n,(i),个入口，对于允许的转向行为，在虚节点之间构造虚有向边，一个具有转向限制的,T,型交叉口,(,图,3.5,所示,),可以用增加虚节点的方法表示出来，如图,3.6,增加虚边的方法优点：,非常直观，简单,缺点：,1,、增大了存储量，从而增加了计算时间，加大了路网编码的工作量。
2,、大量虚节点和虚边，与原有路网中的弧和节点混杂在一起，输出结果的可读性较差图3.6增加虚边法表示转向限制,3.3,适合车辆导航的路段,链数据模型,即解决方法二,车辆导航系统对数字道路地图数据模型的要求,1),能够表达路网要素及拓扑结构,;,2),能够表达单向交通、交叉口转向限制等交通管制措施,;,3),能够表达具体实际中各种特殊的路网结构,;,4),能够表达路口的时间延迟，即道路网络的节点权值,;,5),便于地图匹配算法对路网的操作,;,6),便于路线规划算法对路网的操作,;,路段一链的数据模型,1,、形式化定义,基本思想：,将路网的基本单元,“路段”作为图的顶点,，而将路段之间的,允许转向行为,(,这种转向行为称作“链”,),作为图的弧它的形式化定义为,:,其中，,N,R,为一个图，代表道路网络,;,Rs,为图的顶点集，代表道路网络的有向路段集,;,Ls,为图的弧集，代表道路网络的链集P,代表对应道路网络,NR,的路段集,2,、链的形成,路 段 链数据模型与节点一路段数据模型之间存在紧密的关系,设节点路段的道路网络为N=(V,E),V是顶点集，E是弧集；,对应的基于路段一链的道路网络定义如下:N=(V,L)，其中 V=E，即网络N中的的顶点集V就是网络N中的弧集，L表示链集，它可以定义如下：,x,yV表示N中的顶点，对应网络N中的弧，,x=(u,v,Q,uv,)表示N中弧的起点是网络N中的起始弧，,y=(v,w,Q,vw,)表示N中弧的终点是网络N中的x的后继弧,(u,v,w)P 表示网络N中有转向限制的弧，在N中不再存在。
3-7链的生成图,假设存在如图(a)所示由南向西的禁止左转限制，同时该路口不允许车辆掉头，,图(b)是该道路的节点一路段表示，,那么可以生成路段一链的道路网络模型，如图(c)所示3,、“路段一链”数据模型具有特点,:,(1),很好解决了交通实际中的单行线问题,;,由于该数据模型以“路段”为网络节点，它继承了有向路段的属性信息，任何个双向道路都对应于两个有向路段，当某条道路为单向时，该地理实体仅对应一有向路段，也就是对应该模型中的一个节点2),很自然的表达了路网中的转向限制,由于该数据模型以“链”为网络弧段，假如相邻的路段可以通行的话，该数据模型就建立了以节点为连接的联系，也就是该模型中的一条“链”,;,(3),对于路网中交叉口处的不同转向行为的交叉口延迟，它们可以转化到“链”的,属性中，用网络弧段的权值表达,对应的弧的权值由下式确定:,d(Li，Lj)=d(Li)+dp(Li,Lj),其中,:d(Li,Lj)为路段-链模型中弧(链)的权值，d(Li)为节点一路段模型中弧(路段)的权值，dp(Li,Lj)为路段Li转向Lj的延迟所对应的权值4)这种数据模型也增大了网络的规模,这是由于在城市道路网路中，路段的数目大于节点的数目，同时路段连接关系的数目也大于路段数目。
3.4,数字道路地图的分层组织,普通的地图分层方法,最初传统的数字地图，,没有。