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

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的最小代价参考表。
2.根据权利要求1所述的一种导航用道路拓扑数据模型和计算 方法，其特征在于：所述的道路联通性计算函数(20)中的专用道 或为单向道路或为单向禁止行驶；所述的道路联通性计算函数(20) 中的数据从Ni1扩展或为从Ni2扩展，否则两个节点都扩展。

暂无