大型栅格地图两点之间连通性检测方法、设备及存储介质

摘要

本发明提供了一种大型栅格地图两点之间连通性检测方法、设备及存储介质，该方法包括：连接栅格地图模型中的起点和终点，得到起点至终点的线段；计算得到栅格地图模型中障碍物的边界线；计算得到线段与障碍物的交界点；判断交界点的个数，若交界点的个数等于0，则起点和终点连通；若交界点的个数大于0，则从交界点中选取一个沿障碍物的边界线进行配对，若配对成功，则删除配对成功的交界点，并返回继续判断交界点的个数；若配对不成功，则起点和终点不连通。该方法只需遍历地图上一些固定特征的点即可判断地图上两点之间连通性。在针对超大地图的中起点和终点和连通性判断，在时间消耗和内存消耗都优于目前以深度遍历或者广度遍历为主的算法。