数字道路地图学习教案.pptx

《数字道路地图学习教案.pptx》由会员分享，可在线阅读，更多相关《数字道路地图学习教案.pptx（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数字道路数字道路(dol)地图地图第一页，共47页。3.1 导航(dohng)电子地图概述导航(dohng)电子地图概述第1页/共47页第二页，共47页。地图正北，车头显示切换比例尺的切换 系统时间地图缩小地图放大切换到汽车当前位置各种地理查询信息 地图2D、2.5D切换显示当前目的地GPS，陀螺仪状态提示地图中心点标识符城市地图城市地图导航导航(dohng)(dohng)用电子地图实例用电子地图实例导航(dohng)电子地图概述第2页/共47页第三页，共47页。导航系统组成(z chn)第3页/共47页第四页，共47页。导航导航(dohng)(dohng)电子地图地位及与导航电子地图地位及与

2、导航(dohng)(dohng)功能的对应功能的对应关系关系地位：导航电子地图在整个车辆导航应用体系地位：导航电子地图在整个车辆导航应用体系(tx)(tx)中起中起到核心的作用，针对不同导航应用往往会采用不同规格的到核心的作用，针对不同导航应用往往会采用不同规格的电子地图。电子地图。通常电子地图由记录实际地物的地理数据和与实际地物相通常电子地图由记录实际地物的地理数据和与实际地物相关的标识、修饰信息以及各类附加信息组成。根据应用场关的标识、修饰信息以及各类附加信息组成。根据应用场合的不同，电子地图的选用也不同。合的不同，电子地图的选用也不同。电子地图数据与导航应用功能之间的关系如下图所示：电子

3、地图数据与导航应用功能之间的关系如下图所示：导航(dohng)电子地图概述车 辆 定 位地 图 显 示路 径 规 划路 线 导 引地 址 定 位实时交通数据处理POI(信息点)车辆导航系统功能道路形状数据库背景数据拓扑数据属性数据电子地图数据库电子地图数据与导航应用功能之间的关系第4页/共47页第五页，共47页。地图显示、地址匹配、地图匹配、路径规划、路径引导地图显示、地址匹配、地图匹配、路径规划、路径引导(yndo)(yndo)与数字地图的关系与数字地图的关系地图显示是车辆导航系统的重要组成部分，它构成了人机接口的基础，地图显示是车辆导航系统的重要组成部分，它构成了人机接口的基础，地图显示的

4、成功与否直接影响到用户对产品的印象。地图显示需要依地图显示的成功与否直接影响到用户对产品的印象。地图显示需要依赖数字地图中的道路位置、宽度、级别等属性以及道路附近的各种设赖数字地图中的道路位置、宽度、级别等属性以及道路附近的各种设施。施。地址匹配又称为地址匹配又称为(chn wi)(chn wi)地理编码，即通过给定的经纬度坐标确定地理编码，即通过给定的经纬度坐标确定地图上街道的地址，或者相反的过程。需要数字地图的基本属性是道地图上街道的地址，或者相反的过程。需要数字地图的基本属性是道路的名称和地址范围。路的名称和地址范围。地图匹配是利用数字地图的路网信息修正车辆定位模块的位置输出，地图匹配是

5、利用数字地图的路网信息修正车辆定位模块的位置输出，位置修正的前提是车辆在道路上行驶。位置修正的前提是车辆在道路上行驶。路线规划和路线引导更是与数字地图密切相关，它的几乎所有数据如路线规划和路线引导更是与数字地图密切相关，它的几乎所有数据如路网的空间分布、几何坐标、拓扑连接、道路平均时速、转向限制等路网的空间分布、几何坐标、拓扑连接、道路平均时速、转向限制等等来源都是数字地图中的道路信息，等来源都是数字地图中的道路信息，第5页/共47页第六页，共47页。车辆导航系统的功能(gngnng)与数字道路地图特征的关系第6页/共47页第七页，共47页。车辆导航系统的数字地图和通用数字地图侧重点不同：车辆

6、导航系统的数字地图和通用数字地图侧重点不同：首先，地图要素种类不同。首先，地图要素种类不同。导航图重点要素：道路导航图重点要素：道路 每条路的地理坐标、道路之间每条路的地理坐标、道路之间的拓扑关系、道路交叉口的交通限制情况等。因此设的拓扑关系、道路交叉口的交通限制情况等。因此设计导航数字地图数据库时，需要着重考虑道路的表达计导航数字地图数据库时，需要着重考虑道路的表达与组织，同时要有一个高效的访问道路信息的机制，与组织，同时要有一个高效的访问道路信息的机制，以便可以高效率的进行诸如路线规划，路线引导等功以便可以高效率的进行诸如路线规划，路线引导等功能。对于车辆导航系统来说，应该根据功能需要选择

7、能。对于车辆导航系统来说，应该根据功能需要选择合适的信息进行表达和存储合适的信息进行表达和存储(cn ch)(cn ch)。数字道路地图。数字道路地图是导航数字地图数据库的重点和基础，是数字地图的是导航数字地图数据库的重点和基础，是数字地图的核心内容。核心内容。其次，数据层次划分不同。其次，数据层次划分不同。地图数据层次划分应该强调道路的分层，同时要求能地图数据层次划分应该强调道路的分层，同时要求能够方便扩展，便于地图的升级维护。够方便扩展，便于地图的升级维护。车辆导航系统的功能与数字道路地图(dt)特征的关系第7页/共47页第八页，共47页。3.23.2节点节点(ji din)(ji din

8、)一路段数据模型一路段数据模型3.2.13.2.1图论基本概念图论基本概念图图(Graph)(Graph)图表示的是定义在顶点集上的二元关系。图图表示的是定义在顶点集上的二元关系。图GG是由两是由两个集合个集合V(G)V(G)和和E(G)E(G)组成的组成的,记为记为G=(V,E)G=(V,E)其中：其中：V(G)V(G)是顶点的非空有限是顶点的非空有限(yuxin)(yuxin)集，集，V(G)V(G)中所含元素的个中所含元素的个数即顶点数，称为图的阶，记为数即顶点数，称为图的阶，记为|V(G)|V(G)|或或n n E(G)E(G)是边的有限是边的有限(yuxin)(yuxin)集合，边是

9、顶点的无序对或有序对，集合，边是顶点的无序对或有序对，E(G)E(G)中所含元素的个数称为边数或弧数，记为中所含元素的个数称为边数或弧数，记为mm有向图有向图有向图有向图GG是由两个集合是由两个集合V(G)V(G)和和E(G)E(G)组成的组成的 其中：其中：V(G)V(G)是顶点的非空有限是顶点的非空有限(yuxin)(yuxin)集集 E(G)E(G)是有向边（也称弧）的有限是有向边（也称弧）的有限(yuxin)(yuxin)集合，弧是顶点的集合，弧是顶点的有序对，记为有序对，记为，v,wv,w是顶点，是顶点，v v为弧尾，为弧尾，w w为弧头为弧头(终端点终端点)无向图无向图无向图无向图

10、GG是由两个集合是由两个集合V(G)V(G)和和E(G)E(G)组成的组成的 其中：其中：V(G)V(G)是顶点的非空有限是顶点的非空有限(yuxin)(yuxin)集集 E(G)E(G)是边的有限是边的有限(yuxin)(yuxin)集合，边是顶点的无序对，记为集合，边是顶点的无序对，记为（v,wv,w）或（）或（w,v)w,v)，并且（，并且（v,w)=(w,v)v,w)=(w,v)第8页/共47页第九页，共47页。邻接邻接 与与 关关 联联 对于无向图对于无向图G=(V,E)G=(V,E)，若有边，若有边(u,v)(u,v)E E，则称，则称u u和和v v互为邻接点或相邻接，且边互为邻

11、接点或相邻接，且边(u,v)(u,v)依附于顶点依附于顶点u u和和v v，或称边，或称边(u,v)(u,v)与顶点与顶点u u和和v v相关联。对于有向图相关联。对于有向图G=(V,A)G=(V,A)，若有弧，若有弧 A A，则称顶点，则称顶点v v邻接到顶点邻接到顶点v v，顶点，顶点v v邻接自顶点邻接自顶点v v，且弧，且弧 与顶与顶点点v v和和v v，相关联，它从顶点，相关联，它从顶点v v发出，也称为发出，也称为(chn wi)(chn wi)顶点顶点v v的前的前向关联边，顶点向关联边，顶点v v的后向关联边。的后向关联边。顶点的度顶点的度:无向图中，顶点的度为与每个顶点相连的

12、边数无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目出度：以该顶点为尾的弧的数目 某个顶点的度某个顶点的度=此顶点的入度此顶点的入度+此顶点的出度此顶点的出度第9页/共47页第十页，共47页。带权带权 图（网络图（网络(Network)(Network)）:图的边或弧可具有与之相关的图的边或弧可具有与之相关的量化信息，表示从一个顶点到另一个顶点的距离、费用等等。量化信息，表示从一个顶点到另一个顶点的距离、费用等等。这种与图的边或弧相关的量化信息叫做边

13、或弧的权这种与图的边或弧相关的量化信息叫做边或弧的权(Weight)(Weight)，其中，其中(qzhng)(qzhng)的顶点称为节点的顶点称为节点(Node)(Node)。路径路径 从顶点从顶点v v到顶点到顶点w w的一条路径是由一个不同顶点组成的的一条路径是由一个不同顶点组成的序列序列V=Vi,0V=Vi,0，Vi,1Vi,1，Vi,nVi,n，满足，满足(Vi,j-1(Vi,j-1，Vi,j)Vi,j)E E 或或 Vi,j-1Vi,jE,(1jE,(1jn)n)且其中且其中(qzhng)Vi,0=v(qzhng)Vi,0=v，Vi,n=w Vi,n=w。路径长度路径长度 沿路径边

14、的数目。沿路径边的数目。连通：从顶点连通：从顶点V V到顶点到顶点WW有一条路径，则有一条路径，则V V和和WW是连通的是连通的连通图：图中任意两个顶点都是连通的无向图叫连通图：图中任意两个顶点都是连通的无向图叫 第10页/共47页第十一页，共47页。例245136G1图G1中：V(G1)=1,2,3,4,5,6 E(G1)=,顶点(dngdin)2入度：1 出度：3例157324G26图G2中：V(G2)=1,2,3,4,5,6,7 E(G2)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)顶点(dngdin)2的度：4V1V4V2V3V510113425

15、86带权图第11页/共47页第十二页，共47页。3.2.23.2.2节点一路节点一路(yl)(yl)段数据模型的形式化定义段数据模型的形式化定义 目前的车辆导航系统中，道路网用图的形式来表示，而且目前的车辆导航系统中，道路网用图的形式来表示，而且大多使用基于节点大多使用基于节点路段的数字道路地图数据模型。路段的数字道路地图数据模型。道路网道路网 带权有向图，道路以线或折线对象的方式存储，带权有向图，道路以线或折线对象的方式存储，表示为一系列带坐标点的有序集。表示为一系列带坐标点的有序集。包含交叉点的道路被拆分包含交叉点的道路被拆分成最基本的路段，使其只在端点处与其他路段相交。拆分后成最基本的路

16、段，使其只在端点处与其他路段相交。拆分后的基本路段对应的基本路段对应(duyng)(duyng)于路网中的弧，其端点就是图中的于路网中的弧，其端点就是图中的顶点。顶点。用图的形式可以表示为用图的形式可以表示为:其中，NR:代表(dibio)道路网络；Ns为道路的节点集，对应图的顶点集;Rs为道路的有向路段集，对应图的弧集，可以用道路网络中两个节点的拓扑关系表示，u和v分别是起点和终点，Quv路段的属性集，可表示长度、平均时速、通过时间、是否收费等。第12页/共47页第十三页，共47页。道路在数字地图中作用：道路在数字地图中作用：1 1、道路描述主要是现实道路的显示，要求、道路描述主要是现实道路

17、的显示，要求(yoqi)(yoqi)数据比较数据比较细致和详细细致和详细;2 2、计算主要是指配合车辆导航的地图匹配、路线规划和引导、计算主要是指配合车辆导航的地图匹配、路线规划和引导等内容，要求等内容，要求(yoqi)(yoqi)道路具有明确的综合性，以利于道道路具有明确的综合性，以利于道路计算的速度和算法的实现。路计算的速度和算法的实现。对道路数据的空间描述：一般采用三个层次，即数据对道路数据的空间描述：一般采用三个层次，即数据层、描述层，综合层，它们的内容见下表层、描述层，综合层，它们的内容见下表第13页/共47页第十四页，共47页。3.2.33.2.3路网的基本要素路网的基本要素路网的

18、基本要素为：点实体路网的基本要素为：点实体(节点节点(ji din)(ji din)和线实体和线实体(路段路段)第14页/共47页第十五页，共47页。1 1、路段、路段 路段一般作为道路的最小空间描述单元。即路段是具有同一属性路段一般作为道路的最小空间描述单元。即路段是具有同一属性在路网中相互独立且最小的道路图形特征。每一条道路，有对应的一在路网中相互独立且最小的道路图形特征。每一条道路，有对应的一些属性信息，例如道路的交通限制、道路名称、道路宽度等，所以需些属性信息，例如道路的交通限制、道路名称、道路宽度等，所以需要根据属性信息的变化把一些道路拆分为更小的路段。要根据属性信息的变化把一些道路

19、拆分为更小的路段。2 2、节点、节点 节点并不是一个实际意义上的点，它是一个抽象的概念，即可能节点并不是一个实际意义上的点，它是一个抽象的概念，即可能使车辆行驶路线发生改变的控制点。使车辆行驶路线发生改变的控制点。（1 1）道路的交叉口或者路的终点。）道路的交叉口或者路的终点。（2 2）道路特性发生改变的点，如在该点道路的宽度显著增加或者减）道路特性发生改变的点，如在该点道路的宽度显著增加或者减少，或者从该点开始道路需要收费行驶等。少，或者从该点开始道路需要收费行驶等。（3 3）可能进行转向操作）可能进行转向操作(cozu)(cozu)的点，如进行物理分隔的道路中间的点，如进行物理分隔的道路中

20、间将隔离栏将隔离栏(带带)打开，专供车辆掉头的点，打开，专供车辆掉头的点，（4 4）快速路的出入口等。直接影响车辆导航系统路线计算的结果的）快速路的出入口等。直接影响车辆导航系统路线计算的结果的点。点。第15页/共47页第十六页，共47页。（2.12.1）几种）几种(j zhn)(j zhn)典型的道路交叉口典型的道路交叉口(1)(1)多道交叉口多道交叉口三条或者三条以上的单车道三条或者三条以上的单车道(chdo)(chdo)或多车道或多车道(chdo)(chdo)相相交的平面交叉口形成一个节点，如交的平面交叉口形成一个节点，如:T:T型交叉口、型交叉口、Y Y型交叉型交叉口、十字交叉口、多路

21、交叉口等，如图口、十字交叉口、多路交叉口等，如图(a)(a)所示。有时多所示。有时多条道路的中心线在交叉口没有交叉成为一个点时，但如果条道路的中心线在交叉口没有交叉成为一个点时，但如果起到了交叉口的作用，仍然可以把它作为一个节点处理，起到了交叉口的作用，仍然可以把它作为一个节点处理，如图如图(b)(b)路网基本要素节点(ji din)路段第16页/共47页第十七页，共47页。(2)(2)环岛型交叉口环岛型交叉口环岛环岛 型型 交交 叉口是一种特殊的交叉口，在该交叉口内部，车辆必须单向叉口是一种特殊的交叉口，在该交叉口内部，车辆必须单向行驶，绕环岛逆时针旋转行驶，如图行驶，绕环岛逆时针旋转行驶，

22、如图3.2(c).3.2(c).(3)(3)快速路的出入口快速路的出入口快速快速 路路(含高速路、高架桥等含高速路、高架桥等)的出入口包含了交叉信息和出入口，它既的出入口包含了交叉信息和出入口，它既要描述正常要描述正常(zhngchng)(zhngchng)快速路的行驶路线，也要确定道路出入口位置，快速路的行驶路线，也要确定道路出入口位置，如图如图3.2(d).3.2(d).(4)U(4)U 型转弯口，如图型转弯口，如图3.2(e)3.2(e)。路网基本要素节点(ji din)路段第17页/共47页第十八页，共47页。（2.22.2）道路）道路(dol)(dol)连接点连接点道路连接点，用于标

23、定道路连接点，用于标定(bio dn)(bio dn)道路方向的改变以及同一道路道路方向的改变以及同一道路发生属性描述变化的转折点，复杂道路通过增加道路连接点来进发生属性描述变化的转折点，复杂道路通过增加道路连接点来进行分段。例如在行分段。例如在C,F,GC,F,G使道路属性发生改变影响车辆导航功能实使道路属性发生改变影响车辆导航功能实现的点，它们是道路连接点。现的点，它们是道路连接点。（2.32.3）各种复杂的立交桥，应将各个匝道的出入口定义为节点，）各种复杂的立交桥，应将各个匝道的出入口定义为节点，使得计算的行车路线能清楚的表达桥内的行驶，使出行者了解各使得计算的行车路线能清楚的表达桥内的

24、行驶，使出行者了解各种转向操作的具体行走方法。种转向操作的具体行走方法。路网基本要素节点(ji din)路段图3.3第18页/共47页第十九页，共47页。3 3、典型、典型(dinxng)(dinxng)示例示例如图如图3.43.4所示是城市所示是城市快速路中主、辅路并快速路中主、辅路并行，且存在非互通式行，且存在非互通式立交桥的情形。立交桥的情形。这种情况下，主、辅这种情况下，主、辅路用两条平行的路段路用两条平行的路段(l dun)(l dun)表示，快表示，快速路的出口速路的出口P P和入口和入口QQ、WW为下层交叉点为下层交叉点辅路与相交道路辅路与相交道路EFEF的平面交叉口都形成的平面

25、交叉口都形成节点，而主路在立交节点，而主路在立交处则没有形成节点。处则没有形成节点。图3.4实际(shj)道路网络及对应的节点一路段模型路网基本要素节点 路段第19页/共47页第二十页，共47页。4 4、组成、组成(z chn)(z chn)要素的属性要素的属性4.1 4.1 节点的属性数据应包括节点的属性数据应包括:（1 1）节点编号、（）节点编号、（2 2）节点坐标、（）节点坐标、（3 3）灯控路口的时间配时、）灯控路口的时间配时、（4 4）节点的车辆行驶平均时间延误、（）节点的车辆行驶平均时间延误、（5 5）交叉口转向限制等。）交叉口转向限制等。4.24.2车辆导航系统路段属性数据应该至

26、少包含以下内容车辆导航系统路段属性数据应该至少包含以下内容:(1)(1)路段编号路段编号;(2);(2)起点、终点编号；起点、终点编号；(3)(3)路段名称路段名称;(4)(4)路段长度路段长度;(5);(5)路段宽度路段宽度;(6);(6)道路等级道路等级(高速路，国道，省道，高速路，国道，省道，县道，城市一级路，二级路，三级路县道，城市一级路，二级路，三级路););(7)(7)车辆平均时速车辆平均时速:(8):(8)路面路面(lmin)(lmin)建筑状况建筑状况(好、一般、差好、一般、差););(9)(9)最高速度限制最高速度限制;(10);(10)是否收费与收费标准是否收费与收费标准(

27、11)(11)实时路况信息实时路况信息(交通事故、堵塞程度等交通事故、堵塞程度等);(12);(12)允许车辆类型允许车辆类型路网基本要素节点(ji din)路段第20页/共47页第二十一页，共47页。序号序号字段字段名称名称字段类型字段类型字段字段长度长度注注 释释1NODE_IDinteger4节点的编号节点的编号2Longitudefloat4节点经度节点经度(乘乘10万后的值万后的值)3Latitudefloat4节点纬度节点纬度(乘乘10万后的值万后的值)4typesmallinteger 4节点类型节点类型5updatedate4数据更新日期数据更新日期导航数据库中节点导航数据库中

28、节点(ji din)(ji din)要素说明要素说明实例实例第21页/共47页第二十二页，共47页。序号序号字段名称字段名称字段类型字段类型字段长度字段长度注注 释释1ROAD_IDSegment_idInteger4路段标识符路段标识符2FNODEInteger4路段始结点号路段始结点号3TNODEInteger4路段终结点号路段终结点号4LENGTHFloat4路段图幅里程路段图幅里程5NAMECharater30路段名称路段名称6SRANKCharater2路段等级路段等级路段所属道路级别路段所属道路级别1 未知道路类型未知道路类型1.高等级公路高等级公路(高速公路、国道高速公路、国道)

29、;2.省级道路省级道路;3.城市主干道和县乡间干道城市主干道和县乡间干道;4.城市次干道；城市次干道；5.城市支路级其他道路。城市支路级其他道路。7SBRLCharater1路段所属道路层面码道路路段所属道路层面码道路平面平面 1高架高架 2地下地下 38SANGLEInteger4路段方位角路段方位角导导航航(d(d o oh h n ng)g)数数据据库库中中路路段段要要素素说说明明第22页/共47页第二十三页，共47页。9SORDWAYCharater1 1路段的单、双行路段的单、双行双向通行，不可回转双向通行，不可回转 1双向通行，可回转双向通行，可回转 2双向通行，正向可回转双向通行

30、，正向可回转 3双向通行，反向可回转双向通行，反向可回转 4双向禁行双向禁行 (路不通路不通)5单行单行 610DISTRICTCharater21行政区域编码行政区域编码(多个行政区域用多个行政区域用“，”隔开隔开)11LIMITCharater100路段限制信息路段限制信息12GoInCntinteger4正向的入度正向的入度13GoInRoadIDscharacter50正向的进入路段正向的进入路段14GoOutCntinteger4正向的出度正向的出度15GoOutRoadIDscharacter50正向的出去路段正向的出去路段16BackInCntinteger4反向的入度反向的入度

31、17BackInRoadIDscharacter50反向的进入路段反向的进入路段18BackOutCntinteger4反向的出度反向的出度19BackOutRoadIDscharacter50反向的出去路段反向的出去路段20UPDATEdate更新日期更新日期第23页/共47页第二十四页，共47页。3.2.4 3.2.4 路网连通性表达路网连通性表达(biod)(biod)路段之间的连接关系的表达即路段通过节点建立拓扑关系，路段之间的连接关系的表达即路段通过节点建立拓扑关系，建立拓扑关系的路网可以方便的执行地图匹配、路线规划等建立拓扑关系的路网可以方便的执行地图匹配、路线规划等道路计算。道路

32、计算。车辆导航系统中连通性与实际道路网络中的有所不同：车辆导航系统中连通性与实际道路网络中的有所不同：数字道路地图可以用带权有向图的形式来描述，图论意义上数字道路地图可以用带权有向图的形式来描述，图论意义上的连通性描述了节点之间的邻接关系，这种节点之间的连通的连通性描述了节点之间的邻接关系，这种节点之间的连通性具有性具有(jyu)(jyu)传递性，即节点传递性，即节点n1n1与与n2n2连通，连通，n2n2与与n3n3连通，连通，那么那么n1n1一定与一定与n3n3连通。连通。但在实际的道路网络中，交通管理部门经常会采取一些交通但在实际的道路网络中，交通管理部门经常会采取一些交通管理措施，如单

33、向交通、转向限制等，这种情况下，节点之管理措施，如单向交通、转向限制等，这种情况下，节点之间的连通性不再具有间的连通性不再具有(jyu)(jyu)传递性，从而那些直观上连通的传递性，从而那些直观上连通的路线在实际交通行为中是不可达的。路线在实际交通行为中是不可达的。第24页/共47页第二十五页，共47页。例如例如(lr)(lr)，从花园北路到北航东南门路口，从图中直观地看是连通，从花园北路到北航东南门路口，从图中直观地看是连通的，但由于北航路口的东进口禁止左转，使得在实际交通行为中不能的，但由于北航路口的东进口禁止左转，使得在实际交通行为中不能由花园北路左转到学知路口，因此这条路线不可达。由花

34、园北路左转到学知路口，因此这条路线不可达。第25页/共47页第二十六页，共47页。解决解决(jiju)(jiju)方法一：增加虚边法方法一：增加虚边法基本思想：在具有基本思想：在具有(jyu)(jyu)转向限制的节点处增加多个虚拟节点和虚拟边，将每一种允转向限制的节点处增加多个虚拟节点和虚拟边，将每一种允许的转向行为表示出来。许的转向行为表示出来。设在路网设在路网NrNr中，节点中，节点vi vi，具有，具有(jyu)n(i)(jyu)n(i)个后继和个后继和n(i)n(i)个前驱，那么必须将该节点拆个前驱，那么必须将该节点拆分为分为n(i)n(i)十十n(i)n(i)个虚节点，分别代表该交叉

35、口处的个虚节点，分别代表该交叉口处的n(i)n(i)个出口和个出口和n(i)n(i)个入口，对于允许个入口，对于允许的转向行为，在虚节点之间构造虚有向边，一个具有的转向行为，在虚节点之间构造虚有向边，一个具有(jyu)(jyu)转向限制的转向限制的T T型交叉口型交叉口(图图3.53.5所示所示)可以用增加虚节点的方法表示出来，如图可以用增加虚节点的方法表示出来，如图3.63.6第26页/共47页第二十七页，共47页。增加虚边的方法增加虚边的方法(fngf)(fngf)优点：非常直观，简单优点：非常直观，简单缺点：缺点：1 1、增大了存储量，从而增加了计算时间，加大了路网编码的、增大了存储量，

36、从而增加了计算时间，加大了路网编码的工作量。工作量。2 2、大量虚节点和虚边，与原有路网中的弧和节点混杂、大量虚节点和虚边，与原有路网中的弧和节点混杂在一起，输出结果的可读性较差。在一起，输出结果的可读性较差。图3.6增加虚边法表示转向(zhunxing)限制第27页/共47页第二十八页，共47页。3.3 3.3 适合适合(shh)(shh)车辆导航的路段车辆导航的路段链数据模型链数据模型即解决方法二即解决方法二3.3.13.3.1车辆车辆(chling)(chling)导航系统对数字道路地图数据导航系统对数字道路地图数据模型的要求模型的要求1)1)能够表达路网要素及拓扑结构能够表达路网要素及

37、拓扑结构;2)2)能够表达单向交通、交叉口转向限制等交通管制能够表达单向交通、交叉口转向限制等交通管制措施措施;3)3)能够表达具体实际中各种特殊的路网结构能够表达具体实际中各种特殊的路网结构;4)4)能够表达路口的时间延迟，即道路网络的节点权能够表达路口的时间延迟，即道路网络的节点权值值;5)5)便于地图匹配算法对路网的操作便于地图匹配算法对路网的操作;6)6)便于路线规划算法对路网的操作便于路线规划算法对路网的操作;第28页/共47页第二十九页，共47页。3.3.23.3.2路段路段(l dun)(l dun)一链的数据模型一链的数据模型1 1、形式化定义、形式化定义基本思想：将路网的基本

38、单元基本思想：将路网的基本单元“路段路段”作为图的顶点作为图的顶点(dngdin)(dngdin)，而将路段之间的允许转向行为，而将路段之间的允许转向行为(这种转向行为这种转向行为称作称作“链链”)”)作为图的弧。作为图的弧。它的形式化定义为它的形式化定义为:其中，其中，NRNR为一个图，代表道路网络为一个图，代表道路网络;RsRs为图的顶点为图的顶点(dngdin)(dngdin)集，代表道路网络的有向路段集集，代表道路网络的有向路段集;LsLs为图的弧集，代表道路网络的链集。为图的弧集，代表道路网络的链集。P P代表对应道路网络代表对应道路网络NRNR的路段集。的路段集。第29页/共47页

39、第三十页，共47页。2 2、链的形成、链的形成(xngchng)(xngchng)路路 段段 链数据模型与节点一路段数据模型之间存在紧密的链数据模型与节点一路段数据模型之间存在紧密的关系关系设节点设节点路段的道路网络为路段的道路网络为N=(V,E),VN=(V,E),V是顶点集，是顶点集，E E是弧集；是弧集；对应对应(duyng)(duyng)的基于路段一链的道路网络定义如下的基于路段一链的道路网络定义如下:N=(:N=(V,L)V,L)，其中其中 V=E V=E，即网络，即网络NN中的的顶点集中的的顶点集VV就是网络就是网络N N中的弧集，中的弧集，LL表示链集，它可以定义如下：表示链集，

40、它可以定义如下：x,yx,yVV表示表示NN中的顶点，对应中的顶点，对应(duyng)(duyng)网络网络N N中的弧，中的弧，x=(u,v,Quv )x=(u,v,Quv )表示表示NN中弧的起点是网络中弧的起点是网络N N中的起始弧，中的起始弧，y=(v,w,Qvw)y=(v,w,Qvw)表示表示NN中弧的终点是网络中弧的终点是网络N N中的中的x x的后继弧的后继弧,(u,v,w)(u,v,w)P P 表示网络表示网络N N中有转向限制的弧，在中有转向限制的弧，在NN中不再存中不再存在。在。第30页/共47页第三十一页，共47页。3-7链的生成(shn chn)图假设存在如图(a)所示

41、由南向西的禁止左转限制，同时该路口不允许车辆掉头(dio tu)，图(b)是该道路的节点一路段表示，那么可以生成路段一链的道路网络模型，如图(c)所示。第31页/共47页第三十二页，共47页。3 3、“路段路段(l dun)(l dun)一链一链”数据模型具有特点数据模型具有特点:(1)(1)很好解决了交通实际中的单行线问题很好解决了交通实际中的单行线问题;由于该数据模型以由于该数据模型以“路段路段”为网络节点，它继承了有为网络节点，它继承了有向路段的属性信息，任何个双向道路向路段的属性信息，任何个双向道路(dol)(dol)都对都对应于两个有向路段，当某条道路应于两个有向路段，当某条道路(d

42、ol)(dol)为单向时，为单向时，该地理实体仅对应一有向路段，也就是对应该模该地理实体仅对应一有向路段，也就是对应该模型中的一个节点。型中的一个节点。(2)(2)很自然的表达了路网中的转向限制很自然的表达了路网中的转向限制由于该数据模型以由于该数据模型以“链链”为网络弧段，假如相邻的路为网络弧段，假如相邻的路段可以通行的话，该数据模型就建立了以节点为段可以通行的话，该数据模型就建立了以节点为连接的联系，也就是该模型中的一条连接的联系，也就是该模型中的一条“链链”;”;第32页/共47页第三十三页，共47页。(3)(3)对于路网中交叉口处的不同转向对于路网中交叉口处的不同转向(zhunxing

43、)(zhunxing)行为的交叉口延迟，行为的交叉口延迟，它们可以转化到它们可以转化到“链链”的属性中，用网络弧段的权值表达。的属性中，用网络弧段的权值表达。对应的弧的权值由下式确定对应的弧的权值由下式确定:d(Li d(Li，Lj)=d(Li)+dp(Li,Lj)Lj)=d(Li)+dp(Li,Lj)其中其中:d(Li,Lj):d(Li,Lj)为路段为路段-链模型中弧链模型中弧(链链)的权值，的权值，d(Li)d(Li)为节点一路为节点一路段模型中弧段模型中弧(路段路段)的权值，的权值，dp(Li,Lj)dp(Li,Lj)为路段为路段LiLi转向转向(zhunxing)Lj(zhunxing

44、)Lj的的延迟所对应的权值。延迟所对应的权值。(4)(4)这种数据模型也增大了网络的规模这种数据模型也增大了网络的规模这是由于在城市道路网路中，路段的数目大于节点的数目，同时路段这是由于在城市道路网路中，路段的数目大于节点的数目，同时路段连接关系的数目也大于路段数目。连接关系的数目也大于路段数目。第33页/共47页第三十四页，共47页。3.4 3.4 数字道路数字道路(dol)(dol)地图的分层组织地图的分层组织3.4.1普通的地图分层方法最初传统的数字地图，没有分层组织，一幅图包含有各类不同的信息，如边界、城市、村镇、河流、注记、道路等，在进行某一专题或地理分析时，只注重对某一单项同类对象

45、进行显示和分析，而其他内容不作为分析对象，从直观上给人杂乱的感觉，处理(chl)也不方便。目前的GIS软件都采用分层结构组织地图数据。一般地，分层结构采用按图层组织的方法，即把同一类(y li)或几类地理要素的信息放在同一个图层，每一个图层存储为一个或一组独立的文件，如图3.9所示，在这组文件中进行叠加显示操作。图3.9第34页/共47页第三十五页，共47页。3.4.23.4.2数字数字(shz)(shz)道路地图的单图集分层结构道路地图的单图集分层结构由于车载导航设备的计算能力和存储由于车载导航设备的计算能力和存储(cn ch)(cn ch)资源的限制，需要设计资源的限制，需要设计专门的分层

46、结构来组织道路数据。专门的分层结构来组织道路数据。目前国际上主流的导航地图数据（如目前国际上主流的导航地图数据（如Kiwi,SDALKiwi,SDAL等标准等标准)的分层组织结的分层组织结构就是针对车载设备的特点设计的。构就是针对车载设备的特点设计的。其特点：是将主地图数据依比例尺组织成其特点：是将主地图数据依比例尺组织成“比例尺层比例尺层 图幅图幅”结构。结构。一个主地图称作图集，在一个主地图称作图集，在1:5001:500至至1:40001:4000万比例尺的范围内将图集分成万比例尺的范围内将图集分成若干比例尺层，也称存储若干比例尺层，也称存储(cn ch)(cn ch)层，所有存储层，所

47、有存储(cn ch)(cn ch)层覆盖同一层覆盖同一地理区域，但每个存储地理区域，但每个存储(cn ch)(cn ch)层信息的详细程度不同。存储层信息的详细程度不同。存储(cn(cn ch)ch)层内依一定规则划分成等距或不等距的矩形区域，称作图幅，也可层内依一定规则划分成等距或不等距的矩形区域，称作图幅，也可以在存储以在存储(cn ch)(cn ch)层内按层内按“块块 基准图幅基准图幅 图幅图幅”的多级结构划分地的多级结构划分地理空间。理空间。优点：充分考虑了车载设备对大容量地图数据的操作能力，能缓解强势优点：充分考虑了车载设备对大容量地图数据的操作能力，能缓解强势数据与弱势资源之间的

48、矛盾。数据与弱势资源之间的矛盾。第35页/共47页第三十六页，共47页。分层、分块数目的大小分层、分块数目的大小,可以根据硬件可以根据硬件(yn jin)(yn jin)软件条件综合考虑。软件条件综合考虑。将第将第1 1层地图数据根据屏层地图数据根据屏幕显示范围大小幕显示范围大小,按横方按横方向分为向分为mm份份,纵向分为纵向分为n n份份,这样一屏幕数据由这样一屏幕数据由mnmn份矢量数据组成。第份矢量数据组成。第2 2层层(mn)2 (mn)2 份矢量数据组份矢量数据组成。依此类推，第成。依此类推，第I I层由层由(mn)i(mn)i 份矢量数据组成。份矢量数据组成。分割的数据采用树结构分

49、割的数据采用树结构索引存储。索引存储。如图如图3-103-10所示。所示。3-10 单图集分层组织(zzh)结构“比例尺层图幅”分层结构第36页/共47页第三十七页，共47页。单图集分层组织单图集分层组织(zzh)(zzh)的缺点：的缺点：不利于后续数据的添加和现有数据的局部更新不利于后续数据的添加和现有数据的局部更新由于它把整个地理空间的数据资料集合到一个由于它把整个地理空间的数据资料集合到一个(y)(y)主地图上，我国现在正处于经济和城市建设的高速发主地图上，我国现在正处于经济和城市建设的高速发展时期，地图数据的添加和更新要求能够快速及时，展时期，地图数据的添加和更新要求能够快速及时，这种

50、单图集分层组织形式不适用我国车辆导航地图数这种单图集分层组织形式不适用我国车辆导航地图数据生产的现状。据生产的现状。第37页/共47页第三十八页，共47页。3.4.3 3.4.3 数字数字(shz)(shz)道路地图的多图集分层结构道路地图的多图集分层结构多图集分层组织结构可以通过多图集分层组织结构可以通过(tnggu)(tnggu)一个图幅树的多叉树结构一个图幅树的多叉树结构将所有主地图连接在一起。如图将所有主地图连接在一起。如图3-113-11所示。所示。311多图集分层组织(zzh)结构第38页/共47页第三十九页，共47页。每个图集按显示比例尺分成多个存储层；每个图集按显示比例尺分成多