基于GIS数据库的道路匹配及路径规划算法

基于GIS数据库的道路匹配及路径规划算法

技术领域

本发明以基于图形学的地图匹配算法，以将无人车实时行驶位置快速、准确地匹配到GIS数据库的地图上，随后由构建好的GIS数据库为无人车提供其当前所在道路的局部环境信息，如：道路名称、道路等级、道路长度、车道线数量、限速值、路口地面标识、前方红绿灯距离等，为无人车识别与决策模块的高效工作奠定基础。

背景技术

近年来，地图匹配算法的研究工作主要集中在确定候选路段方面，一些学者针对确定候选路段集的问题提出了不同的筛选方法，以提高匹配速度、优化算法的实时性；主要对地图进行分割得到若干个面积较小的待匹配区域，然后分别计算车辆当前待定位点到各个待匹配区域边界的距离，将待定位点到边界距离最短的待匹配区域作为地图匹配的候选区域，该区域内的路段即为候选匹配路段；对地图进行逻辑分区，这种方法的基本思想是将地图按照一定的逻辑(如距离权重大小)划分为不同的区域，然后计算待定位点到其周围区域的逻辑距离，将距离最短的区域作为匹配算法的候选区域，落在该区域内的路段即组成候选路段集合；上述方法都需要划分地图以得到候选区域，对于与候选区域相交的路段是以扩展筛选范围的方法确保候选路段集的置信度，因而导致了地图匹配算法的实时性没有得到进一步地优化。

发明内容

本发明的解决方案是在直接投影法的基础上，利用图形学中判断线段与多边形相交的算法提出一种基于图形学的地图匹配算法；由于这种判定算法只使用非数值计算，因而计算量较小，将其应用在候选路段筛选过程中能够有效地改善匹配算法的实时性；基于图形学的地图匹配算法首先对接收机接收到的GPS定位数据进行处理，包括剔除异常数据以及GPS数据的坐标转换；接着确定定位误差区域，并根据判断线段与多边形相交的算法确定候选路段集合，减小之后的匹配运算量；最后计算各候选路段的匹配度，选择匹配度值最小的路段作为最佳匹配路段，并将无人车在该路段上的投影点作为车辆当前行驶的位置。

具体实施方式

本发明实施如下，利用快速排斥实验和跨立实验可以确定候选路段集合，接下来要讨论最佳匹配路段的确定；为了方便描述，定义无人车当前定位点P距第i个候选路段的投影距离为id，而无人车当前行驶方向与第i个候选路段方向的夹角为i；通过分析可知，id与i越小的候选路段成为最佳匹配路段的可能性就越大，反之亦然；因此，本文确定最佳匹配路段的思想就是定义候选路段匹配度为投影距离id与方向夹角i的加权和，依次计算候选路段集中每个路段的匹配度，将匹配度最小的路段选作最佳匹配路段，并将获得的定位数据投影到该路段上，投影点即为无人车的匹配位置。