一种基于改进的连通图遍历算法的路径图生成方法

摘要

本发明公开了一种基于改进的连通图遍历算法的路径图生成方法，其特征包括：1、该方法应用于未知路径图的地下停车场，并将地下停车场路径图简化为连通图；2、初始化连通图，建立坐标系；3、在当前遍历点处，确定下一个遍历点方向；4、根据当前遍历点坐标和下一个遍历点方向，移动单位长度l的距离达到下一个遍历点，获得下一个遍历点坐标；5、到达下一个遍历点处，判断移动过程中是否存在顶点；6、不断更新当前遍历点，循环遍历，直至遍历完成生成路径图。本发明通过地下停车场内改进的路径遍历方法，来优化地下停车场路径图的生成过程，使得生成过程简洁化、高效化、规模化；更加丰富当前电子地图信息，将更多路径信息呈现给出行者。

说明书

技术领域

本发明涉及连通图遍历算法和路径图生成领域，具体地说是一种基于改进的连通图遍历算法的路径图生成方法。

背景技术

近几年来，随着人们生活水平的提高，汽车数量在家庭中急剧增加。在车辆出行的过程中，人们对于道路等级的要求大大提升，对于道路信息的需求也大幅度提高。对于道路信息的需求中，最基本的就是行车的路径图。目前一般的室外地图已经非常完善，可以通过电子地图获取路径图，通过GPS进行导航，获得出发地到目的地的最短路径，道路上的超速、限速信息以及危险地段提示等。但是GPS导航技术是基于已有的电子地图并且在室外无遮挡的环境下才能进行，所以当前的电子地图以及GPS导航存在室内环境下，尤其是地下停车场内，具有一定的缺失。

现在的地下停车场的路径图大多数使用停车场建设时的规划图纸或者停车场建成后的人工绘制图纸，更新困难并且修正效率低下，难以应用于大规模的地下停车场路径图的创建中，更加无法与当前的室外电子地图衔接，以补充当前电子地图的缺失。此外，目前也有很多的室内定位技术,例如基于wifi、惯性定位等的室内定位技术，都能够进行室内定位，但是这一类的定位技术仅仅应用于够获得目标的位置信息，无法确定整个室内路径状况。

发明内容

本发明是为了克服现有技术存在的不足之处，提供一种基于改进的连通图遍历算法的路径图生成方法，以期通过地下停车场内改进的路径遍历方法，来优化地下停车场地图的生成过程，使得地下停车场地图的生成过程更加简洁化、高效化、规模化，从而保证了地下停车场路径图与当前的电子地图互相衔接，更加丰富当前电子地图信息，为用户的出行提供所需的路径信息。

本发明为达到上述发明目的，采用如下技术方案：

本发明一种基于改进的连通图遍历算法的路径图生成方法的特点是应用于未知路径图的地下停车场中，并按如下步骤进行：

步骤1、初始化连通图，建立坐标系；

步骤1.1、将地下停车场的未知路径图定义为连通图G＝(V,E)，V表示顶点集；E表示边集；定义顶点集V中任意一个顶点为v_q，q表示顶点的数量；定义边集E中任意一条边为e_k，k表示边的数量；

步骤1.2、基于连通图G，定义遍历点集，则遍历点集中所有遍历点所组成的坐标集合为W；遍历点集中的所有遍历点能组成连通图G；

定义遍历点集中每个遍历点的度所组成的集合为N；定义集合N中任意一个遍历点的度为n；

定义遍历点集中每个遍历点的未遍历的关联边数量所组成的集合为M；定义集合M中任意一个遍历点的未遍历的关联边数量为m；

定义连通图G的邻接矩阵为A；

步骤1.3、以地下停车场的入口位置为原点O，以原点O为中心，并以地下停车场入口方向作为X轴正方向，以X轴方向向左旋转90°的方向作为Y轴正方向，以向上垂直于平面XOY的方向为Z轴正方向，建立三维坐标系O-XYZ；

步骤1.4、初始化连通图G、遍历点集W、所有遍历点的度所组成的集合N、关联边数量所组成的集合M、邻接矩阵A均为空集；

步骤2、基于当前连通图，在当前遍历点处，确定下一个遍历点方向；

步骤2.1、定义遍历次数为p；初始化p＝1、q＝1、k＝1、L_k＝0；

步骤2.2、以入口位置为第p次遍历点，遍历的单位长度为l；

步骤2.3、记录第p次遍历点的坐标为w_p；将第p次遍历点加入到遍历点集中，从而获得更新后的遍历点集和及其坐标集合W′；获取第p次遍历点的度n_p；

步骤2.4、判断p＝1是否成立；若成立，则初始化第p次遍历点的未遍历的关联边数量m_p为n_p；若不成立，则初始化第p次遍历点的未遍历的关联边数量m_p为n_p-1；

步骤2.5、判断在遍历点集W中是否存在与第p次遍历点的坐标w_p相同的遍历点的坐标w_r；若存在，则将相同的遍历点的度n_r赋值给第p次遍历点的度n_p，将相同的遍历点的未遍历的关联边数量m_r赋值给第p次遍历点的未遍历的关联边数量m_p；

若不存在，则第p次遍历点的度n_p保持不变，第p次遍历点的未遍历的关联边数量m_p保持不变；

步骤2.6、将第p次遍历点的度n_p加入到遍历点度的集合N中，从而获得更新后的遍历点度的集合N′；将第p次遍历点的未遍历的关联边数量m_p加入到遍历点的未遍历的关联边数量集合M中，从而获得更新后的遍历点的未遍历的关联边数量集合M′；

步骤2.7、根据第p次遍历点的度n_p，判断第p次遍历点的类型；

若第p次遍历点的度n_p为2，则表示第p次遍历点为边e_k上的点；将第p次遍历点加入到边e_k中，从而获得更新后的边e′_k；并执行步骤2.9；

若第p次遍历点的度n_p不为2，则表示第p次遍历点为顶点；将第p次遍历点的坐标w_p赋值给顶点v_q的坐标，同时记录下顶点v_q所对应的第p次遍历点的遍历次数，从而获得更新后的顶点集V′，将q+1赋值给q；并执行步骤2.8；

步骤2.8、判断更新后的顶点集V′中的顶点个数q是否小于3；

若q小于3，则保持边e_k不变，保持边集E不变；

若q不小于3，由边e_k中的遍历点个数计算获得边e_k的长度L_k；将边e_k加入到边集E中，从而获得更新后的边集E′；由更新后的顶点集V′和更新后的边集E′，更新当前连通图为G_k；将k+1赋值给k；计算更新后的顶点集V′中的各个顶点之间的长度，从而更新邻接矩阵为A′；

步骤2.9、根据第p次遍历点的未遍历的关联边数量m_p，判断第p+1次遍历点的方向；

若第p次遍历点的未遍历的关联边数量m_p不为0，则从第p次的遍历点的未遍历的关联边中随机选取任一关联边的方向作为第p+1次遍历点的方向；将m_p-1赋值给m_p，从而获得再次更新的未遍历的关联边数量集合M″，并转步骤3；

若第p次遍历点的未遍历的关联边数量m_p为0，则判断未遍历的关联边数量集合M′中是否存在未遍历的关联边数量不为0的其他顶点；若存在，则转步骤2.10；否则，终止遍历，并根据前p次遍历点的坐标连接成地下停车场的路径图；

步骤2.10、根据更新后的邻接矩阵A′，运用最短路径算法从顶点集V′中选取与第p次遍历点距离最近且未遍历的关联边数量不为0的顶点v_s作为第p次遍历点，并将顶点v_s的坐标赋值给第p次遍历点的坐标w_p，返回步骤2.3；

步骤3、从第p次遍历点出发，根据第p+1次遍历点的方向，移动单位长度l的距离后达到第p+1次遍历点，通过惯性定位法获得第p+1次遍历点的坐标w_p+1；

步骤4、在第p+1次遍历点处，判断从第p次遍历点出发，移动到第p+1次遍历点路程中是否存在顶点；

若存在，则从第p+1次遍历点处移动至相应顶点处，并通过惯性定位法获得相应顶点的坐标，将相应顶点作为第p+1次遍历点；

若不存在，第p+1次遍历点保持不变；

步骤5、将p+1赋值给p，将W′赋值给W，将V′赋值给V，将N′赋值给N，将M″赋值给M，将A′赋值给A；并返回步骤2.3。

与已有技术相比，本发明的有益技术效果体现在：

1、本发明中运用了改进的连通图遍历算法，将生成地下停车场地图的遍历过程完全展现，通过改进运筹学中的深度遍历算法和广度遍历算法，形成了对于未知连通图的新的遍历算法，更加简洁、高效的遍历地下停车场，获得路径的坐标信息和其他路径相关信息，最终生成地下停车场地图，从而保证了地下停车场路径图与当前的电子地图互相衔接，更加丰富当前电子地图信息，为用户的出行提供所需的路径信息。

2、本发明的步骤1.1中，将地下停车场的未知地图抽象成连通图，即可运用连通图的相关特性来优化遍历地下停车场的过程，更加高效的生成地下停车场路径图。

3、本发明的步骤1.3中，通过建立三维坐标系，不仅仅描述了地下停车场径图在平面内的特征，还可以凸显路径的空间变化。

4、本发明的步骤2.3中，通过运用点的度的特性来判断遍历点的类型，将不同类型确的遍历点分类，分别构成连通图的顶点和边，继而形成了连通图，实现了遍历过程中由点构成边，由边和顶点构成连通图的逐步形成过程，使运用改进的连通图遍历算法的路径图生成过程具体化、结构化。

5、本发明的步骤2.4中，定义遍历点的未遍历的关联边数量来确定下一个遍历点的方向，使遍历过程中下一个遍历点可选择方向的数量明确，每个遍历点的选择过程清晰明了。

6、本发明的步骤2.10中，通过定义的连通图的邻接矩阵利用最短路径算法，获得下一个遍历点方向，有效减少了重复遍历，提高了遍历连通图的效率。

附图说明

图1为本发明流程图；

图2为本发明流程图细节图；

图3为本发明实例中遍历过程中随机生成的路径图a；

图4为本发明实例中遍历过程中随机生成的路径图b；

图5为本发明实例中遍历完成后的路径图。

具体实施方式

在应用本方法生成路径图的过程，为了获得相应的数据，需要一定的路径图生成设备。实例中以车辆作为载体，在车辆上装有路径图生成所需的装置，包括：单线激光雷达、广角摄像头、三轴加速度计、三轴陀螺仪、主控计算机和LED显示屏。单线激光雷达扫描并获取载体车辆所处的地下停车场内的环境信息；广角摄像头，用于获取载体车辆周围的地面图像数据；三轴加速度计和三轴陀螺仪属于惯性定位装置，用来采集载体车辆在地下停车场内移动时的三轴加速度和三轴角速度；主控计算机，用于存储单线激光雷达、广角摄像头、三轴加速度计和三轴陀螺仪采集的数据，在采集数据后并对数据进行处理，可以获得载体车辆在地下停车场内的定位坐标，地下停车场内路径坡度、转弯角度等信息，采集处理完成后运行地下停车场的路径图生成算法，生成地下停车场的路径图；LED显示屏用于显示生成的地下停车场路径图。车辆以地下停车场入口处位起点，开启路径图生成装置，进行地下停车场路径图的生成。图3和图4为某地下停车场路径生成过程中载体车辆在地下停车场内的遍历过程图，图5为遍历完成后由所有遍历点坐标生成的图，将图5中的点连接后就生成了地下停车场的路径图。在图3、图4，图5中仅显示了坐标点位置，并没有显示其他相关路径信息。

本实施例中，如图1所示，一种基于改进的连通图遍历算法的路径图生成方法，应用于未知路径图的地下停车场中，并按如下步骤进行：

步骤1、初始化连通图，建立坐标系；

步骤1.1、将地下停车场的未知路径图定义为连通图G＝(V,E)，V表示顶点集；E表示边集；定义顶点集V中任意一个顶点为v_q，q表示顶点的数量；定义边集E中任意一条边为e_k；k表示边的数量；

遍历地下停车场之前，将即将生成的路径图简化定义为连通图，并将路径中的信息也依照连通图的特征进行定义，以便于在遍历过程中利用连通图的特性提高便利效率。将路径图定义为连通图忽略了路径的宽度以及路面标线，但在实际遍历过程中可以通过在载体车辆上安装单线激光雷达、广角摄像头等装置来获取载体车辆所处地下停车场的环境信息和载体车辆周围的路面图像数据。在以车辆作为载体的实际应用中，所有定义的数据、数据集合等都由主控计算机存储和更新，数据的计算处理等也由主控计算机完成。

步骤1.2、基于连通图G，定义遍历点集，则遍历点集中所有遍历点所组成的坐标集合为W；遍历点集中的所有遍历点能组成连通图G；

定义遍历点集中每个遍历点的度所组成的集合为N；定义集合N中任意一个遍历点的度为n；

定义遍历点集中每个遍历点的未遍历的关联边数量所组成的集合为M；定义集合M中任意一个遍历点的未遍历的关联边数量为m；

定义连通图G的邻接矩阵为A；定义的邻接矩阵A为动态矩阵，每遍历得到一个顶点增加一个维数，以连通图G中边的长度作为邻接矩阵A的元素。

步骤1.3、以地下停车场的入口位置为原点O，以原点O为中心，并以地下停车场入口方向作为X轴正方向，以X轴方向向左旋转90°的方向作为Y轴正方向，以向上垂直于平面XOY的方向为Z轴正方向，建立三维坐标系O-XYZ；

建立三维坐标系是以便于凸显路径在空间位置上的变化，可以反映出路径的坡度变化，在多层的大型地下停车场内也可以反映出路径图所处的不同高度、不同楼层。实例中选取的是比较理想化的地下停车场，忽略了坡度和多层问题，所以图3、图4、图5都为平面图。

步骤1.4、初始化连通图G、遍历点集W、所有遍历点的度所组成的集合N、关联边数量所组成的集合M、邻接矩阵A均为空集；

步骤2、基于当前连通图，在当前遍历点处，确定下一个遍历点方向；如图2所示，步骤2作为路径图生成过程中遍历算法的核心部分，其步骤细节如下，以图3、图4为例：

步骤2.1、定义遍历次数为p；初始化p＝1、q＝1、k＝1、L_k＝0；

步骤2.2、以入口位置为第p次遍历点，遍历的单位长度为l；在利用车辆作为载体时，每次遍历单位长度可以通过控制车辆速度和时间间隔来完成，以固定的时间间隔匀速行驶就能保证每次遍历单位长度。在图3中，入口处位置为顶点即V₁位置，在坐标系中时原点位置，三个方向的坐标都可以为0，或者由于入口处位置处于室外也可由GPS进行定位获得坐标。

步骤2.3、记录第p次遍历点的坐标为w_p；w_p位置如图3；将第p次遍历点加入到遍历点集中，从而获得更新后的遍历点集和及其坐标集合W′；获取第p次遍历点的度n_p；

利用连通图中点的度来提供遍历方向，每个遍历点有几个度就有几个遍历方向。第p次循环下的遍历起点的度n_p的获得方式是，通过已有的图像识别技术，拍摄地下停车场路径图片，将图片与具有不同度的连通图图片对比，找出与拍摄的地下停车场路径图片最相近的对照图片，对照图片中点的度即为第p次循环下的遍历起点的度，从而获得连通图G中各个遍历点的度。

步骤2.4、遍历点的未遍历的关联边数量即在遍历点处可选择的下一遍历点的方向数，数量上等于遍历点的度减去该遍历点上已经遍历的方向数；判断p＝1是否成立；若成立，则初始化第p次遍历点的未遍历的关联边数量m_p为n_p；在第1次遍历点处，遍历点没有遍历过任何方向，所以初始化遍历点的未遍历的关联边数量等于度的大小。图3中，V₁处初始化的未遍历的关联边数量即为度的大小1；若不成立，则初始化第p次遍历点的未遍历的关联边数量m_p为n_p-1；除去第1次遍历点处，以后的其他遍历点，都会因为上一遍历点移动到该遍历点而减少一个遍历方向，所以初始化的未遍历的关联边数量等于度减去一个遍历方向。在图3中，V₂、V₃等点处，初始化的未遍历的关联边数量为度的大小减1，即V₂处初始化的未遍历的关联边数量为3。

步骤2.5、判断在遍历点坐标集W′中是否存在与第p次遍历点的坐标w_p相同的遍历点的坐标w_r；若遍历点是顶点，则会有多个遍历方向那么这个遍历点就会重复遍历，重复遍历时就要及时更新遍历点的信息。若存在，则将相同的遍历点的度n_r赋值给第p次遍历点的度n_p，将相同的遍历点的未遍历的关联边数量m_r赋值给第p次遍历点的未遍历的关联边数量m_p；在图3中，顶点V₂处就会遍历三次，每次重复遍历时，初始化后顶点V₂处的未遍历的关联边数量都为3，但实际上并不是，有可能顶点V₂处的未遍历的关联边数量已经为1，所以需要重新更新V₂处的未遍历的关联边数量；

若不存在，则第p次遍历点的度n_p保持不变，第p次遍历点的未遍历的关联边数量m_p保持不变；

步骤2.6、将第p次遍历点的度n_p加入到遍历点度的集合N中，从而获得更新后的遍历点度的集合N′；将第p次遍历点的未遍历的关联边数量m_p加入到遍历点的未遍历的关联边数量集合M中，从而获得更新后的遍历点的未遍历的关联边数量集合M′；

步骤2.7、根据第p次遍历点的度n_p，判断第p次遍历点的类型；

若第p次遍历点的度n_p为2，则表示第p次遍历点为边e_k上的点；将第p次遍历点加入到边e_k中，从而获得更新后的边e′_k；并执行步骤2.9；

若第p次遍历点的度n_p不为2，则表示第p次遍历点为顶点；遍历时，顶点由于有多个遍历方向可选择，所以每个顶点都会进行多次遍历，每次遍历顶点后顶点名称也会发生变化，但是多个不同的名称都代表同一顶点；在图3中，当遍历完成顶点V₆到顶点V₃之间的边后，遍历点再次到达顶点V₃处，则再次对遍历点进行判定，判定为顶点后顶点V₃处也是顶点V₇处。将第p次遍历点的坐标w_p赋值给顶点v_q的坐标的同时，记录下顶点v_q所对应的第p次遍历点的遍历次数，从而获得更新后的顶点集V′，将q+1赋值给q；并执行步骤2.8；

步骤2.8、判断更新后的顶点集V′中的顶点个数q是否小于3；通过顶点集中顶点数目的变化来判断是否有新的边形成。

若q小于3，则保持边e_k不变，保持边集E不变；在图3中，刚遍历完第一次遍历点后就可以判定出入口处位置为顶点V₁，此时经过赋值后q＝2，所以在若q小于3的情况下都不会形成边。

若q不小于3，如果顶点数目大于等于3，那么遍历了一次顶点后就会生成一条边。在图3中，当顶点V₂已经判定后，此时经过赋值后q＝3，满足若q不小于3的条件，此时顶点V₂和顶点V₁之间形成了边e₁。由边e_k中的遍历点个数计算获得边e_k的长度L_k；可以计算e₁的长度L₁。更新邻接矩阵为A′，邻接矩阵由A＝(0)变成了将边e_k加入到边集E中，从而获得更新后的边集E′；当顶点V₂已经判定后，边集E由空集变成E′＝{e₁}，当顶点V₆已经判定后，边集为E′＝{e₁、e₂、e₃、e₄、e₅}；此时由更新后的顶点集V′和更新后的边集E′，更新当前连通图为G_k；连通图G是由顶点集和边集组成的，所以当遍历了一个顶点并形成一条边以后，连通图就发生了变化，也要进行更新；将k+1赋值给k；在图3中，当边e₁形成后，则k＝2；

步骤2.9、根据第p次遍历点的未遍历的关联边数量m_p，判断第p+1次遍历点的方向；

若第p次遍历点的未遍历的关联边数量m_p不为0，则从第p次的遍历点的未遍历的关联边中随机选取任一关联边的方向作为第p+1次遍历点的方向；在图3中w_p点位置上，此时第p次遍历点的未遍历的关联边数量m_p＝1，随机选择也只有一个方向，但是之前当遍历顶点V₆处时，顶点V₆对应的遍历点w_p处未遍历的关联边数量m_p＝3，即当顶点V₆处为第p次遍历点时向第p+1次遍历点遍历时，可以从3个方向中随机选择，由图3可已看出随机选择的是顶点V₃的方向；将m_p-1赋值给m_p，由于已经随机选择顶点V₃的方向，所以未遍历的关联边数量要减少一个；从而获得再次更新的未遍历的关联边数量集合M″，并转步骤3；

若第p次遍历点的未遍历的关联边数量m_p为0，则判断未遍历的关联边数量集合M′中是否存在未遍历的关联边数量不为0的遍历点；若存在，则所述遍历点为顶点，转步骤2.10；图3与图4的区别就是，图3在顶点V₆处随机选择了顶点V₄方向作为第p+1次遍历点方向而图4中在顶点V₆处随机选择了顶点V₄方向作为第p+1次遍历点方向；在图4中当遍历到顶点V₄位置时，顶点V₄处即为第p次遍历点，同时也是顶点V₇；从图中可以看出在顶点V₄处已经没有可向下一遍历点的遍历的遍历方向，m_p＝0；否则，终止遍历，图5中则是已经无法找到未遍历的关联边数量不为0的遍历点，所以表明遍历终止；并根据前p次遍历点的坐标连接成地下停车场的路径图；将图5中的遍历点连接起来就是地下停车场的路径图；

步骤2.10、根据更新后的邻接矩阵A′，运用最短路径算法从顶点集V′中选取与第p次遍历点距离最近且未遍历的关联边数量不为0的顶点v_s作为第p次遍历点，并将顶点v_s的坐标赋值给第p次遍历点的坐标w_p，返回步骤2.3；

以图4为例，在第p次遍历点即顶点V₄处，需要寻找未遍历的关联边数量不为0的顶点，满足条件的顶点是V₂、V₃、V₅、V₆，以更新后的邻接矩阵A′为依据，运用最短路径算法即可找到距离最近的顶点是顶点V₆，所以顶点V₆将作为第p次遍历点，从顶点V₄处移动到顶点V₆处的过程是载体车辆依据生成的最短路径直接一定，这一过程中没有遍历点的生成；

步骤3、根据第p+1次遍历点的方向，从第p次遍历点出发，移动单位长度l的距离后达到第p+1次遍历点，通过惯性定位法获得第p+1次遍历点的坐标w_p+1；

步骤4、在第p+1次遍历点处，判断从第p次遍历点出发，移动到第p+1次遍历点路程中是否存在顶点；这一步骤是为了防止移动单位距离l的过程中错过某个顶点的位置；判断从第p次循环下的遍历起点出发，移动到第p+1次遍历点处的这一过程中，是否存在顶点的方法，通过已有的图像识别技术，在移动长度为l的距离过程中拍摄地下停车场中的路径图片，将所有图片与具有不同度的连通图图片对比，找出与拍摄的地下停车场路径图片最相近的对照图片，通过对照图片中点的度，找出在移动长度为l的距离过程中是否存在顶点。

若存在，则从第p+1次遍历点处移动至相应顶点处，并通过惯性定位法获得相应顶点的坐标，将相应顶点作为第p+1次遍历点；

若不存在，第p+1次遍历点保持不变；

步骤5、将p+1赋值给p，将W′赋值给W，将V′赋值给V，将N′赋值给N，将M″赋值给M，将A′赋值给A；并返回步骤2.3。