本⽂要求读者具备如下知识和技术背景:1 熟悉Java开发,知道如何正确的编译运⾏Java代码;2 知道GIS的基本概念,知道地图导航的基本概念;3 对GeoTools有⼀定的认识。
⼀开始先来明确我们的任务:在基本的路径查询基础上1 实现单⾏道限制2 实现左右拐弯限制3 实现动态路况限制4 选择最短距离和最短时间
图和图的搜索
要想了解路径查询的算法,⾸先得了解⼀下它的数学模型“图”。简⽽⾔之,图就是⼀系列的点和点之间的连接关系。【】
所谓路径查询,可以简化成对⼀个图的搜索。例如:从点6到点1的最短路径是,6-4-5-1,或者6-4-3-2-1,⼜或者6-4-5-2-3-4-5-1。如你所见,从6到1之间可以有许多条路径,其中第⼀条和第⼆条我们认为是合理的,第三条是不合理的,因为它有重复路段。所以查询节点间路径的算法就显得⾄关重要了。经典的查询算法有:和它的改进版本。这两个算法的实现各种语⾔都有,也很成熟了,我们不需要⾃⼰去写,但是最为⼀种训练,有兴趣的读者可以⾃⼰试着实现。
我在这⾥只介绍⼀下基本概念。从前⾯的例⼦我们看到两点间可以有多条路径,但是实际上我们⼀般只关⼼⼀条路径,就拿开车来说,我们关⼼驾驶时间最少的路。⼀般情况下,实际距离短驾驶时间就少,所以我们先从实际距离⼊⼿。作为搜索算法如何确定距离最短呢。6-4-5-1⼀定⽐6-4-3-2-1距离短吗。显然我们不能仅仅根据节点的个数来判断距离。事实是我们除了拥有点和点之间的连接外,还需要连接的属性,这⾥就是距离。⽤上⾯的例⼦我们来指定距离:6-4距离104-5距离75-1距离64-3距离23-2距离42-1距离1
6-4-5-1距离10+7+6=236-4-3-2-1距离10+2+4+1=17
显然第⼆条路虽然节点多但是距离短。这⾥需要引⼈⼀个概念“开销”,在这个例⼦中⽬前我们使⽤路径距离来代表开销。我们总是选择开销⼩的路径。现实中影响驾驶时间的因素除了距离还有道路拥堵情况,所以我们增加属性,叫拥堵系数,假设距离乘上系数才是我们需要的开销:
6-4距离10 拥堵14-5距离7 拥堵2
5-1距离6 拥堵14-3距离2 拥堵133-2距离4 拥堵112-1距离1 拥堵11
6-4-5-1距离10*1+7*2+6*1=30
6-4-3-2-1距离10*1+2*13+4*11+1*11=91
可以看到,虽然第⼆条路的实际距离短,但是由于拥堵情况严重,它的开销远⼤于第⼀条路。在这种情况下我们应该选择实际距离长的第⼀条路。我们可以不断对上⾯的计算进⾏完善,增加更多的属性来应对更复杂的实际情况。
分析任务
有了上⾯的知识我们来看看我们的任务:1 实现单⾏道限制
我们可以给连接增加属性叫“⾏驶⽅向限制”,有三个值,分别是:“正向通⾏”,“反向通⾏”,“双向通⾏”。然后在计算开销的时候,判断当前⽅向是否与连接节点的⽅向⼀致,然后根据“⾏驶⽅向限制”的值来决定是否允许通⾏,如果不允许则返回⼀个极⼤值代表开销。2 实现左右拐弯限制
在实现单⾏线的基础上就可以实现拐弯限制,但是需要在数据制作上做⽂章:
我们不能⽤⼀条线来代表⼀个路段,⽽应该⽤并⾏且⽅向相反的两条线,这样拐弯的地⽅也⾃然变成了单⾏线的⼀部分了。3 实现动态路况限制
这个在上⼀节介绍图的时候已经说明了不在赘述。4 选择最短距离和最短时间
这个在上⼀节介绍图的时候已经说明了不在赘述。
代码实现
路⽹改程序要求:
1 路⽹数据是Shapfile格式保存的线段数据2 属性必须提供两个: id 整数
type 整数 只有三个值 1:正向通⾏;-1:反向通⾏;0:双向通⾏
程序采⽤Java编写,利⽤GeoTools 11软件包中的graph扩展实现图的搜索。程序启动后需要先选择路⽹数据,然后可见主界⾯,在主界⾯地图上点击设置起⽌位置。不同⽅向会选择不同道路,如图:
因篇幅问题不能全部显示,请点此查看更多更全内容