[原创]南水之源导航算法思想

注:由于每条路上的点的数量较多。

所以 将每条路都分成 startID , endID , ID ,lenth 进行计算。

数据库的建立为:

a路点信息:(用于记录路上每个点的位置信息和路点的标志位)

       lat, lon, altitude;(位置信息,经纬度,海拔高)

       pointID 标志位。(路点的标志)

b路点连接信息:(用于记录哪两个点连接,以及从属于那条路和险段的标志位)

      startID,endID那两个点相连成直线(a中的标志位);

      roadID这个线属于哪个路(c中的标志位);

      lineID此线段的标志位。

c路的信息:(用于记录路的起始结束点,以及路的标志位和路的实际长度)

      startID,endID路的两头端点(a中的标志位);

      roadID路的标志位;

      lenth路的实际长度。

1.首先将所有c中的 startID 与 endID相连得到一张简体地图JTMap

2.计算出起点到目标点最近的路线。

  通过JTMap计算到起点最近的N条路。

  通过JTMap计算到终点最近的N条路。

注:取N条路是因为每条路都不是直线,所以没办法确定那一条路上的其中一条直线离起点或者终点最近。

  将距离起点最近的N条路,对应从b中取出的N个直线集合QDJH。用QDJH计算离起点最近的一个直线以及此条直线上距离起点最近的点QD。

  将距离终点最近的N条路,对应从b中取出的N个直线集合ZDJH。用ZDJH计算离起点最近的一个直线以及此条直线上距离起点最近的点ZD。 

  将QD,ZD直接连接本身路的端点加入JTMap。

3.现在就是求出QD到ZD的最短路径JTShort。(参照之前博客写的A星算法)

  将这条最短路径JTShort上所有经过的路的roadID从b中获取完整的线,制作成完整的路径地图NavigateRoadMap。

    除了头尾外每两个相邻的两个点ID可以从c中获取roadID。

    头尾点的roadID值是固定的,可以直接从b中获得。(路端点的roadID不固定,是因为一个端点可能多有多个roadID)。

    然后根据roadID从b中获取所有的线相连。所有连接的线组成了NavigateRoadMap。

  将NavigateRoadMap做简单的A星计算可以得到导航路径shortest!

原文地址:https://www.cnblogs.com/lyggqm/p/4789379.html