专利名称：基于复合路口的交通规制的处理方法
技术领域：
本发明涉及一种基于复合路口的交通规制的处理方法，特别是涉及一种对导航数据中交通规制的处理过程，属于导航、电子地图、智能交通系统和数据挖掘的交叉领域。
背景技术：
为了将规制信息正确、高效的组织成为能够被导航系统使用的数据，各种导航数据格式采用了不同的处理方式。导航数据一般是使用在嵌入式硬件设备上的，数据量要求尽量少。路径规划算法需要路口必须有紧凑的聚合性。要求规制处理、存储的原则是方便导航系统使用，尽量提高导航系统的效率。
但是在实际应用中，规制数据的组织一般是松散的，不利于导航系统路径探索的效率，甚至影响路径规划的合理性，从而影响产品质量。
基于以上原因本文提出一种能高效处理和组织规制数据的方法。并在实际数据编译中得到了验证和应用。从模型角度讲，当需要紧凑组织带权有向图并需要在图中进行探索时，也可采用本方法。
相关名词解释
1. Link
Link是对现实生活中的道路进行抽象而形成的曲线，同时道路自身的属性信息被存储在Link上。
2. Node
当道路与道路之间的属性发生变化时或者道路有分叉时，道路就会被抽象成多条 Link, Link之间的连接点被抽象为node，同时这些属性变化信息被存储在node上。
3.复合路口
复合路口是由一个复杂路口内的多个连接点(node)构成的复杂要素。在抽象化时，由于部分道路双线化表达而形成多个连接点(node)，将这些有关系的连接点(node)综合成一个复杂的复合路口，用于方便地表达路口的信息。复合路口是为了构建拓扑关系而定义的虚拟要素。复合路口包含连接点(node)、路口内连接(内Link)。复合路口内部的道路都是路口内Link，但本文中提到的内Link是从逻辑角度讲的，只要在规制处理过程中有需要，可人为设置为内Link，即使这条Link在实际路况中不是一般意义上的复合路口内部Link。复合路口关联的道路除了路口内Link外都叫做外部道路(外Link)。
4.交通规制
交通规制，又称交通限制、通行规制、通行规则等，作为导航数据中的核心内容之一，是由现实道路中的各种实际的交通限制抽象得到的。。
5.完整规制
所谓完整规制是相对于复合路口而言的，规制的进入、退出Link都是复合路口外 Link，经由Link为复合路口内Link的规制，或者是一般路口上的简单规制。
6.非完整规制
所谓非完整规制就是指进入、退出Link有一个或者两者都为复合路口内Link的规制。
7.规制表
多条规制的集合，每条规制存储进入Link、退出Link和规制类型。
8.道路参考表
多条可通行路径的集合，每条路径存储进入Link、退出Link、经由Link。 发明内容
本发明所要解决的问题是提供一种基于复合路口的交通规制处理方法，使用该方法在规制数据处理方面不仅能正确存储交通规制，更能够提高规制处理和存储的效率， 从而提高导航系统路径探索的效率。除此之外，由于本方法不依赖于具体数据实体，仅依赖于规制本身，甚至对可以抽象为本文中规制的实体，均可采用本文的方法进行处理，即可认为本文提供了一种模型方法，从而本方法可应用到其它领域。
为了实现本发明的技术效果，本发明提供的对导航数据中交通规制的处理方法， 将道路抽象成曲线，定义为Link，道路与道路之间的连接点被定义为node，而交通规制中的复合路口由多个连接点(node)构成，位于复合路口内部的Link定义为路口内连接，简称为内Link，复合路口外部的Link定义为路口外连接，简称外Link，该方法基于交通规制本身的经由Link构建复合路口，基于道路拓扑关系和复合路口自身特点补全复合路口，之后再将规制以复合路口规制表和道路参考表的形式组织在复合路口的主结点上。
优选的，上述方法具体包括以下步骤
步骤一、根据交通规则对复合路口内部的Link设置内Link标识；
步骤二、构建基本复合路口，即根据内Link标识和道路拓扑关系构建基本复合路 Π ；
步骤三、复合路口完整化，即对不完整的复合路口实施完整化处理；
步骤四、完整规制的处理，即对规制的进入、退出Link都是复合路口外Link，经由 Link为复合路口内Link的规制进行处理；
步骤五、非完整规制的处理，即对进入、退出Link有一个或者两者都为复合路口内Link的规制进行处理。
优选的，上述步骤一如果Link为通行规制的经由Link，则将此Link标识为内 Link。
优选的，上述步骤二构建基本复合路口包括
1)任取内Link的一个Node作为复合路口主点Pl ；
2)对Pl的每条邻接Link进行处理，判断是否为内Link，如果不是内Link，则存入外Link列表；如果是内Link，则存入内Link列表；
3)收集邻接Node，即当邻接Link为内Link时，收集当前点通过内Link邻接的 Node，即邻接 Node ；
4)所有邻接Link都处理完成后，需要检查邻接Node列表，当有邻接Node被收集的时候将分别以这些Node为当前Node进行递归处理，递归退出条件为遇到了已经处理过的 Node ；
5)每一递归层的所有邻接Node都处理完成以后，复合路口初步构建完成。
优选的，上述步骤三的复合路口完整化包括
1)内Link补全，首尾点都是复合路口 Node的Link需要补全为内Link ；—列Link 首Link的首点和尾Link的尾点为复合路口 Node，且中间Link首尾点度都为2的Link都需要补全为内Link;
2)复合路口 Node补全，基于补全的内Link，其首尾点为需要补全的Node。
优选的，上述步骤四完整规制的处理具体包括
1)完整规制判断，即如果规制的进入Link和退出Link都为复合路口外Link，所有经由Link都为复合路口内Link，则判断为完整规制；
2)完整规制直接存储至规制表；
3)复合路口上其余可通行路径使用Dijkstra算法探索出最优路径存入道路参考表。
优选的，上述步骤五非完整规制的处理具体包括
1)针对复合路口进入、退出Link直接使用Dijkstra算法探索出所有路径；
2)在探索出的路径上，根据规制信息进行筛选处理；得到不受规制影响的路径；
3)在筛选出的路径中选取最优路径，如果不存在，则认为当前进入、退出Link组合不可通行，存入规制表；如果存在，则存入道路参考表。
本发明的优点是通过使用本方法处理的规制数据能高效的解决复合规制的存储和使用问题。本发明的假设前提是通行规制数据的各要素点，包括进入Link、经由Link和退出Link正确。
图1是复合路口抽象示意图2是本发明的算法实施流程图3是一个复合路口上存在两条复合规制示意图4是设置内Link标志流程图5是复合路口构建流程图6是复合路口补全说明示意图7是完整规制示意图8是不完整规制示意图9是规制处理算法流程图。
具体实施方式
为了便于本领域普通技术人员理解和实施本发明，下面结合附图及具体实施方式
对本发明作进一步的详细描述。
如图1所示，为本发明的复合路口抽象示意图，从图上可以看出，复合路口是从真实的路口情况进行抽象化提取出来的，其中m、N2、N3和N4分别是四个连接点，连接点之间的Link分别为L2、L3、L4和L5，即为路口内连接，称为内Link,这些内Link都是位于复合路口内部的道路部分，而复合路口外部的道路L6、L7、L8......L12等即为外Link。
如图2所示，本发明的实现方式，在开始之后包括以下步骤
步骤1)、2)、3)的说明将以图3为例进行，此路口存在两条规制，请参考表1。
权利要求
1.一种基于复合路口的交通规制的处理方法，将道路抽象成曲线，定义为Link，道路与道路之间的连接点被定义为node，而交通规制中的复合路口由多个连接点(node)构成， 位于复合路口内部的Link定义为路口内连接，简称为内Link，复合路口外部的Link定义为路口外连接，简称外Link，其特征在于，该方法基于交通规制本身的经由Link构建复合路口，基于道路拓扑关系和复合路口自身特点补全复合路口，之后再将规制以复合路口规制表和道路参考表的形式组织在复合路口的主结点上。
2.如权利要求1所述的基于复合路口的交通规制的处理方法，其特征在于具体包括以下步骤步骤一、根据交通规则对复合路口内部的Link设置内Link标识；步骤二、构建基本复合路口，即根据内Link标识和道路拓扑关系构建基本复合路口 ；步骤三、复合路口完整化，即对不完整的复合路口实施完整化处理；步骤四、完整规制的处理，即对规制的进入、退出Link都是复合路口外Link，经由Link 为复合路口内Link的规制进行处理；步骤五、非完整规制的处理，即对进入、退出Link有一个或者两者都为复合路口内 Link的规制进行处理。
3.如权利要求2所述的基于复合路口的交通规制的处理方法，其特征在于所述如果 Link为通行规制的经由Link，则将此Link标识为内Link。
4.如权利要求2所述的基于复合路口的交通规制的处理方法，其特征在于所述步骤二构建基本复合路口包括1)任取内Link的一个Node作为复合路口主点Pl；2)对Pl的每条邻接Link进行处理，判断是否为内Link，如果不是内Link，则存入外 Link列表；如果是内Link，则存入内Link列表；3)收集邻接Node，即当邻接Link为内Link时，收集当前点通过内Link邻接的Node， 即邻接Node ；4)所有邻接Link都处理完成后，需要检查邻接Node列表，当有邻接Node被收集的时候将分别以这些Node为当前Node进行递归处理，递归退出条件为遇到了已经处理过的 Node ；5)每一递归层的所有邻接Node都处理完成以后，复合路口初步构建完成。
5.如权利要求2所述的基于复合路口的交通规制的处理方法，其特征在于所述步骤三的复合路口完整化包括1)内Link补全，首尾点都是复合路口Node的Link需要补全为内Link ；如果一列Link 首Link的首点和尾Link的尾点为复合路口 Node，且中间Link首尾点的邻接Link数量都为2，则这些中间Link都需要补全为内Link ；2)复合路口Node补全，基于补全的内Link，其首尾点为需要补全的Node。
6.如权利要求2所述的基于复合路口的交通规制的处理方法，其特征在于所述步骤四完整规制的处理具体包括1)完整规制判断，即如果规制的进入Link和退出Link都为复合路口外Link，所有经由Link都为复合路口内Link，则判断为完整规制；2)完整规制直接存储至规制表；3)复合路口上其余可通行路径使用Dijkstra算法探索出最优路径存入道路参考表。
7.如权利要求2所述的基于复合路口的交通规制的处理方法，其特征在于所述步骤五非完整规制的处理具体包括1)针对复合路口进入、退出Link直接使用Dijkstra算法探索出所有路径；2)在探索出的路径上，根据规制信息进行筛选处理；得到不受规制影响的路径；3)在筛选出的路径中选取最优路径，如果不存在，则认为当前进入、退出Link组合不可通行，存入规制表；如果存在，则存入道路参考表。
全文摘要
本发明提出了一种基于复合路口的交通规制的处理方法，其步骤包括1)设置每条规制的经由link的属性为复合路口内link；2)根据内Link标识及道路拓扑关系，探索构建基本的复合路口；3)对不完整的复合路口实施完整化处理，得到完整的复合路口；4)对规制的进入、退出link等复合路口外link，经由link为复合路口内link的规制进行处理；5)对进入、退出link有一个或者两者都为复合路口内link的规制进行处理，从而完成所有通行规制的处理。通过该方法，在实现路口的高聚合，减少数据量，减轻路径规划�？榈拇硌沽Φ耐保煌ü春下房谏系墓嬷拼娲ⅲ锏搅斯嬷聘咝Ю玫哪康�。
文档编号G01C21/26GK102519476SQ20111043353
公开日2012年6月27日 申请日期2011年12月21日 优先权日2011年12月21日
发明者朱敦尧, 蔡春亮 申请人:光庭导航数据(武汉)有限公司
专业数控铣床产品供应商
20年生产经验，实力工厂，精工品质，质量有保障
