车载导航电子地图的路网模型

摘要：建立适合于车载导航系统的路网数据是车载导航系统的关键。本文描述了如何表达真实世界的交通要素，并结合实际情况给出数据模型。

关键词：汽车导航；路网模型

中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)25-1558-02

Road Network Model for Vehicle Navigation System

XU Rui

(ECRIEE, Hefei 230031, China)

Abstract: The construction of road network for vehicle navigation system is the key part of navigation system. This paper firstly describes the traffic elements of the real world, then designs the road network model which considers the real traffic limits.

Key words: Vehicle Navigation; Road Network Model

1 引言

路网数据是车载导航电子地图中主要研究的内容。传统路网模型的缺陷在于对真实世界的描述不够详尽，难以完整表达道路之间的拓扑关系和用户所关心的交通信息。而且一般车载导航系统均在嵌入式环境下实现，对软硬件要求很高，数据量过于庞大时将无法实现实时处理。因此必须对传统路网模型进行改进，以适应车载导航系统的要求。

本文主要针对车载导航系统，从路网的逻辑层次、交通要素和数据模型三个方面来探讨建立路网数据的方案。

2 逻辑层次

路网数据的逻辑描述常采用三个层次，即数据层(Level-0)、描述层(Level-1)和综合层(Level-2)。数据层通过点、线和面等图形数据描述地物的几何外形和空间关系，用于储存道路形状。描述层在数据层的基础上，将现实对象的特征提取为属性值，即交通要素，用于地图显示和路径引导。综合层则对描述层进行综合，描述要素间拓扑关系，用于路线计算。

图1 道路的逻辑描述层次

如图1所示，长江路由隔离带分隔为正逆两向车道，并与另两条道路相交形成路口C1、C2。使用分层逻辑描述时，在数据层上，储存长江路各车道的外形和路口位置。在描述层上，道路经双向化后，长江路被表达为L1、L2，路口C1被表达为S1和S2，路口C2为S3和S4。在综合层上，L1、L2被综合为CL1，S1和S2为CS1，S3和S4为CS2。从图中可看到数据层、描述层和综合层三者之间的关系。

3 交通要素

道路错综复杂，路口千变万化，描述哪些信息，之间的关系如何，是建立完整可靠的电子地图的关键。参照欧洲地理数据文件格式标准(GDF)，导航电子地图内容应包括道路与轮渡、隧道与桥梁等12大类。简化后，路网数据可表达为简单路段、连接点、综合道路、综合交叉口、道路附属设施等交通要素。

简单路段指两个连接点之间的道路。在描述层中，路段和连接点均是最小可描述单元。路段的两端各有一个连接点，按其数字化方向，第一个连接点称为左节点，第二个连接点成为右节点。路段之间是互相独立的，当一个路段的属性发生变化是不会影响其它路段的。如图2所示，LAB、LBE、LED、LDC和LCA是图中所有的路段，它们在描述层中是独立的，如果在LCD路段设置栅栏，此时LCD路段不可通行，但LCD路段的通行状态的改变不会影响其它路段。

综合道路指连接两个综合路口的道路。在综合层中，一条道路可以包括一条或多条路段，这些路段一般属性相同（如路名相同），但允许的交通流方向不同。如图1所示，道路CL1包含了路段L1和L2，其两端的交叉口分别是CS1和CS2。

综合路口一般由一个路口内的多个连接点组成。在综合层中，综合路口可以包括一个或多个连接点，且这些连接点相互关联，连接路段可由内部路段通达。如图1所示，综合路口CS1包含连接点S1和S2，综合路口CS2包含连接点S3和S4。综合路口的类型可由路口的图形特征和交通功能来描述，一般按照路口连接道路的数量来区分：(1) 三叉路口；(2) 四叉或多叉路口(图3-A)；(3) 环岛(图3-B)；(4) 立交桥(图3-C)。

图3 路口类型

道路附属设施指设立在道路两旁固定位置上的一些用于交通指引和服务的设施。一般按照设施对交通流的控制功能来区分：(1) 转向限制，如禁左、禁止驶入等交通指示牌。描述了路段间转向或通行路线的限制，包含时间限制信息和通行车辆限制信息；(2) 方向路牌，描述道路出入口或分叉口处路牌所示的方向信息；(3) 红绿灯和测速点；(4) 收费站、加油站和服务区。

4 数据模型

路网数据由三类实体集组成：节点集、边集和交通限制集。它们之间的关系可用数学公式表述：RW = {N,R,LR}，R = {|x, y∈N，且L(x, y)}，L R = {|m,n∈N，L'(m,n)，且m与n存在公共节点}。RW代表路网。N代表节点集合。R代表边集合，其元素是有序对，谓词L(x, y)表示由节点x到节点y存在一条有向通路。LR代表交通限制集合，其元素是有序对，谓词L'(m,n)表示从边m到边n存在限制。不同逻辑层次上的实体集表达的内容是不同的。在描述层，节点表达为连接点，边为简单路段。在综合层，节点表达为综合路口，边为综合道路。交通限制也不仅仅指转向限制，还包括路牌、收费站等道路附属设施。

在建立路网数据库时，有效的组织数据库表可减少数据冗余，提高效率。一般路网数据库包含8个表，如图4所示。综合道路表包括路网中的各条道路。综合道路由简单路段组成，综合路口由连接点组成，两个相邻连接点之间由简单路段连接，线由点组成。

图4 路网数据库表

路网数据应以分级分簇方式组织。在地图显示过程中，选用的显示比例尺越大，显示的地理区域也越大，为保证地图清晰并突出重点内容，须控制载入的数据量，并剔除次要要素。在拓扑分析过程中也存在同样的问题。分级组织是把全体要素按重要性区分等级，具体的等级设定由要素的应用特性和数据特性共同决定。同一等级L的要素放置在一起组织成数据子集，称该数据子集的等级为L。参考Kiwi-W标准，假定一共有n个等级，记为L0、L1、…、Ln，L0为最低等级，依次递增，Ln为最高等级。以道路的修建等级作为划分标准，将全国路网划分为5级，完整路网作为L0级，市区主干道为L1级，县乡道为L2级，省道为L3级，国道、高速作为L4级。分簇组织是将空间上相近的要素组成集合，同一等级的数据子集分为若干簇。簇是地图显示、拓扑运算访问接口所选用的最小单元。可参照《国家基本比例尺地形图分幅和编号》的分幅标准结合K树或R*树进行分簇。

图5路网数据库的应用

5 结束语

层次化的逻辑结构、完整的交通要素类型、精练的数据结构、高效且受控的数据组织方式是一个优秀的车载导航路网模型应具有的重要特征。本文在实际应用基础上出发，说明了在车载导航电子地图的各类交通要素，论述了它们之间的关系，并详细描述了如何设计和组织路网数据库。

基于上述模型，我们以分区方式建立全国的全境路网数据库，并成功的应用到公司的产品之中，如图5所示。经过长期实践的检验，本文提出的路网模型能较完整的表达用户对车载导航系统的使用需求，并保证了程序具有较低的性能要求和较高的运算效率。

参考文献：

[1] Version3.0-95, European committee for standardization: Geographic data file (GDF).

[2] 赵亦林. 车辆定位与导航系统. 1999.

[3] Kiwi-W Input for ISO Physical Storage Format.