一种路径快速规划方法

摘要

本发明为一种路径快速规划方法，包括以下步骤：S1)将道路网络按道路等级建立空间分层，并对每一层道路网络划分网格区域、依据道路数据建立道路网络的拓扑结构；S2)在低层次道路网络的起点、终点位置分别进行升层探索，搜索进入高层次道路网络的跃点位置；S3)在高层次道路网络上起点和终点的跃点间按最短路径算法规划路径。本发明以道路合并、双向升层探索等方法规划导航路径，能满足现有导航系统快速计算、规划最佳路径的需要。

主权项

一种路径快速规划方法，其特征在于包括以下步骤：S1）将道路网络按道路等级建立空间分层，并对每一层道路网络划分网格区域、依据道路数据建立道路网络的拓扑结构；S2）在低层次道路网络的起点、终点位置分别进行升层探索，搜索进入高层次道路网络的跃点位置；S3）在高层次道路网络上起点和终点的跃点间按最短路径算法规划路径；道路网络空间分层是根据道路等级从高到低进行分层次，低层次道路包含高层次道路，各层次道路相对独立而且连通；所述升层探索的方法是：1）如果起点和终点分别所在的网格之间隔一个网格以上，进行升层规划；2）在0层或1层内，如果起点和终点分别所在的网格之间隔一个网格，执行步骤3），如果起点和终点分别所在的网格为对角相邻，则执行步骤4），如果起点和终点分别所在在网格相邻，则执行步骤5）；3）起点和终点所跨的九个网格范围，内缩四分之一个网格形成一个矩形范围，如果起点和终点都在该矩形范围内，则加载矩形范围所在的9个网格，在该层规划，否则升层规划；4）起点终点所跨四个网格内缩四分之一网格形成一个矩形范围，如果起点和终点都落在该矩形范围内，则在该层规划,否则升层规划；5）以起点和终点的中点所在网格进行扩展0.75个网格形成一个矩形范围，起点和终点都落在该矩形范围内，则在该层规划，否则升层规划;6）在2层内，如果起点和终点分别所在的网格为相邻或对角相邻的关系，则将起点和终点所跨的四个网格，内缩四分之一个网格形成一个矩形范围，如果起点和终点在该矩形范围内，则加载这四个网格，在2层规划，否则升到3层规划；7）在2层内，如果起点和终点在同一个网格内，则以该网格的相邻对称网格为基础的四个网格，内缩四分之一个网格形成一个矩形分为，如果启点和终点在该矩形范围内，在加载这四个网格，在2层规划，否则升到三层规划；8）在2层内，如果起点或终点至少有一点位于17、23、24这三个网格中，直接升到三层规划。