一种导航用道路拓扑数据模型和计算方法

摘要

一种涉及导航相关的应用技术领域，尤旨一种利用集中在导航专用的道路拓扑数据的分析和提取方法，并以此建立数据模型，用于导航地图数据中能处理大面积，长距离的道路分析计算的一种导航用道路拓扑数据模型和计算方法。该方法包括：分层抽取算法、道路联通性计算函数、层次相邻节点转换表、道路网络的行政区划提取算法和路网出入间的最小代价算法等模块；主要解决如何实现合理的长距离大范围的路线计算等有关技术问题。本发明的积极效果是：确保整体道路网络的连通性；保留了路线计算的启发性数据，提高了路线计算的效率；实现了合理的长距离大范围的路线计算，具有在合理的时间和成本内达到合理的分析计算结果等优点。

主权项

1.一种导航用道路拓扑数据模型和计算方法，该方法通过路线规划和实时导航提供数据基础，完成导航地图数据中道路拓扑网络的核心数据，其特征在于：该方法利用道路网络的各种属性数据，包括：等级，平均车速，行政区划从属，交通功能，道路链路之间的联接节点，将数据容量的平面道路网络转换成多层多块的立体道路网络，并标记出各层各块道路链路之间的联接节点，实现整体道路网络的连通性；通过多层多块道路网络数据的分割存储和局部引用，实现路线计算过程中的有限资源消耗，和道路网络数据的增量更新；通过多层多块的立体道路数据的静态预统计，保留路线计算的启发性数据；通过多层多块的立体道路数据的选择性联接，实现合理的长距离大范围的路线计算；该数据模型和计算方法(1)至少包括：分层抽取算法(10)、道路联通性计算函数(20)、层次相邻节点转换表(30)、道路网络的行政区划提取算法(40)和路网出入间的最小代价算法(50)；其中：所述分层抽取算法(10)是用每个层次的道路网络的自身连通性，不同层次间的道路网络为切换，切换的地点是不同链路的联接节点；该开发对应的分层抽取算法(10)的具体工作步骤是：步骤1.初始化(101)步骤2.设计联通性函数(102)执行完初始化(101)模块后，则进入设计联通性函数(102)模块，设计出联通性函数；步骤3.设定分层集合S(103)执行完设计联通性函数(102)模块后，则进入设定分层集合S(103)模块，并且初始化为空集合；步骤4.寻找符合当前分层要求的链路L(104)执行完设定分层集合S(103)模块后，则进入寻找符合当前分层要求的链路L(104)模块，在原始道路网络中寻找到一条符合当前分层要求的链路L，将L加到集合S；步骤5.判断集合S为空(105)执行完寻找符合当前分层要求的链路L(104)模块后，则进入判断集合S为空(105)模块 如果集合S为非空，则进入S为非空，将相同层次的链路集合加到S(106)模块，假如S非空，取出一条链路Li，以Li为起点，根据联通性函数，将可达到的所有相同层次的链路Lj，Lk，Lm，….集合加到S，并将Li设定成已访问；如果集合S为空，则进入S为空，结束计算(107)模块；步骤6.循环执行执行完S为非空，将相同层次的链路集合加到S(106)模块后，则反馈进入寻找符合当前分层要求的链路L(104)模块的输入端，重复步骤4，直到S为空结束计算；步骤7.S为空，结束计算(107)；所述道路联通性计算函数(20)用综合考虑节点联通性，交通功能和交通规则的限制，判断出从该条链路是否经过若干条中间链路到达目标链路，一条链路必定有两个节点，而节点可以联接若干条链路，链路到链路的访问是链路到节点到链路的数据链条；该设计道路联通性计算函数(20)的具体工作步骤是：步骤1.初始化(201)步骤2.取两端的节点Ni1，Ni2(202)执行完初始化(201)模块后，则进入取两端的节点Ni1，Ni2(202)，以该条链路Li为起点，得到其两端的节点Ni1，Ni2；步骤3.节点扩展(203)执行完取两端的节点Ni1，Ni2(202)模块后，则进入节点扩展(203)模块，参考Li的交通功能和规则限制，假如Li是专用道，那么根据数据从Ni1扩展，否则两个节点都扩展；步骤4.找联接的所有链路(204)执行完节点扩展(203)模块后，则进入找联接的所有链路(204)模块，从NiX扩展，找到与NiX联接的所有链路，根据节点的转向限制，确定从Li切换到Lj所有行驶的链路，这个Lj集合就是Li通过Ni可联通的链路集合；所述层次相邻节点转换表(30)是用不同层次中相邻的可联通的链路之间的节点叫做层次相邻节点，在路线计算过程中可利用这些节点切换不同层次的道路网络；设计该层次相邻节点转换表(30)，将每个层次的道路网络中的节点分层4个类型，包括：层次内部节点(301)；层次相邻出入节点(302)；层次相邻出节点(303)；和 层次相邻入节点(304)；所述道路网络的行政区划提取算法(40)的具体工作步骤是：步骤1.初始化(401)步骤2.设定行政区划层次(402)执行完初始化(401)模块后，则进入设定行政区划层次(402)模块，设定该个行政区划层次省、市、区县，在道路网络内找到该条属于该区划的链路，加入空集合S；步骤3.判断集合S为空(403)执行完设定行政区划层次(402)模块后，则进入判断集合S为空(403)模块 如果集合S为非空，则进入S为非空，取一条链路Li(404)模块，如果集合S非空，从中获取一条链路Li，并把Li从S减除，标记为已访问；并以Li为起点，根据当前设定的行政区划代码，通过广度优先搜索，和联通性计算得到相关的链路集合Lj，Lk，Lm，Ln，….，加入集合S；如果集合S为空，则进入S为空，结束计算(405)模块；步骤4.循环执行执行完S为非空，取一条链路Li(404)模块后，则反馈进入判断集合S为空(403)模块的输入端，重复步骤3，直到集合S为空，结束计算(405)；步骤5.S为空，结束计算(405)；所述路网出入间的最小代价算法(50)通过路网内部链路计算的路线代价来实现，该路网出入间的最小代价算法的具体工作步骤是：步骤1.初始化(501)步骤2.收集路网C所有非内部节点(502)执行完初始化(501)模块后，则进入收集路网C所有非内部节点(502)模块；收集路网C的所有非内部节点，按照入和出的功能分为两个集合，入口节点Sn，出口节点En； 步骤3.取两者不相同的节点(503)执行完收集路网C所有非内部节点(502)模块后，则进入取两者不相同的节点(503)模块，从入口节点集合中任取节点Sni，从出口节点集合中任取节点Eni，并且两者不相同；步骤4.寻找最小代价的链路(504)执行完取两者不相同的节点(503)模块后，则进入寻找最小代价的链路(504)模块，将Sni当作起点，Eni当作终点，通过路线计算方法，在本网络内寻找最小代价的链路(504)，使得Sni到Eni联通；步骤5.建立最小代价的参考条目(505)执行完寻找最小代价的链路(504)模块后，则进入建立最小代价的参考条目(505)模块，建立以入口节点集合中任取节点Sni->出口节点集合中任取节点Eni＝最小代价的参考条目；步骤6.判断是否组合计算过(506)执行完建立最小代价的参考条目(505)模块后，则进入判断是否组合计算过(506)模块 步骤7.循环执行如果非两个集合的节点都组合计算过，则反馈进入取两者不相同的节点(503)模块，重复步骤3直到两个集合的节点都组合计算过；如果是两个集合的节点都组合计算过，则进入形成最小代价参考表(507)模块；步骤8.形成最小代价参考表(507)最后形成入口节点集合中任取节点Sni到出口节点集合中任取节点Eni的最小代价参考表。