[发明专利]一种面向虚拟地球的最短路径分层规划方法

摘要

本发明提供一种面向虚拟地球的最短路径分层规划方法，包括面向虚拟地球的数据预处理过程和最短路径分层规划过程，所述面向虚拟地球的数据预处理过程，包括路网数据分层分块组织，记录格网点，上层瓦片局部最短路径预存；所述最短路径分层规划过程，包括在分层路网的上层确定入点和出点，在上层路网中获取入点和出点之间的最短路径，在下层中确定入点和出点对应的格网点，在下层路网中获取起点和入点之间、出点和终点之间的最短路径，将上下两层中的最短路径连接起来，作为最终的最优路径输出。本发明在虚拟地球中运用最优路径分层规划方法，实现了大规模路网的最短路径分析，同能够实现大规模路网和最短路径的高效可视化。

主权项

一种面向虚拟地球的最短路径分层规划方法，其特征在于：包括面向虚拟地球的数据预处理过程和最短路径分层规划过程，所述面向虚拟地球的数据预处理过程包括以下步骤，步骤1.1，路网数据分层分块组织，包括基于比例尺的方式，将大比例尺路网放置在金字塔的上层，小比例尺路网放置在金字塔的下层；采用等经纬度格网进行路网的分块划分，首先获取整个矢量道路网数据的经纬度范围，然后计算出在全球经纬度格网中的行列号范围，如果道路要素跨越多个格网，则记录与格网边界的交点，将交点称为格网点，并按上下左右分为四类；步骤1.2，上层瓦片局部最短路径预存，包括计算上层瓦片中各个格网点之间的最短路径，形成一条新的格网点之间的弧段，称为格网弧段，然后存储格网弧段的起止格网点、长度和坐标点数据；所述最短路径分层规划过程包括以下步骤，步骤2.1，在分层路网的上层确定入点和出点，实现方式如下，首先确定路径规划中起止点对的分布情况，如果起止点的经度差大于纬度差，则为横向分布；如果起止点的纬度差大于经度差，则为纵向分布；如果起止点为横向分布，则在起止点邻列格网的左格网点集合或者右格网点集合中选取出入点，邻列的行范围由起止点所在行确定；如果起止点为纵向分布，则在起止点邻行格网的上格网点集合或者下格网点集合中选取出入点，邻行的列范围由起止点所在列确定；确定出入点的选择范围之后，分别比较起点与入点选择范围中的点的连线与直线的夹角，终点与出点选择范围中点的连线与直线的夹角，选择构成夹角最小的点作为出入点；步骤2.2，在上层路网中获取入点和出点之间的最短路径；步骤2.3，在下层中确定入点和出点对应的格网点；步骤2.4，在下层路网中获取起点和入点之间、出点和终点之间的最短路径，将上下两层中的最短路径连接起来，作为最终的最优路径输出。