source: subversion/applications/routing/pyroutelib2/route.py @ 30586

Last change on this file since 30586 was 8114, checked in by ojw, 12 years ago

move weighting to a module

File size: 4.5 KB
Line 
1#!/usr/bin/python
2#----------------------------------------------------------------
3# Routing for OSM data
4#
5#------------------------------------------------------
6# Usage as library:
7#   datastore = loadOsm('transport type')
8#   router = Router(datastore)
9#   result, route = router.doRoute(node1, node2)
10#
11# (where transport is cycle, foot, car, etc...)
12#------------------------------------------------------
13# Copyright 2007-2008, Oliver White
14#
15# This program is free software: you can redistribute it and/or modify
16# it under the terms of the GNU General Public License as published by
17# the Free Software Foundation, either version 3 of the License, or
18# (at your option) any later version.
19#
20# This program is distributed in the hope that it will be useful,
21# but WITHOUT ANY WARRANTY; without even the implied warranty of
22# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23# GNU General Public License for more details.
24#
25# You should have received a copy of the GNU General Public License
26# along with this program.  If not, see <http://www.gnu.org/licenses/>.
27#------------------------------------------------------
28import sys
29import math 
30from loadOsm import *
31
32class Router:
33  def __init__(self, data):
34    self.data = data
35  def distance(self,n1,n2):
36    """Calculate distance between two nodes"""
37    lat1 = self.data.rnodes[n1][0]
38    lon1 = self.data.rnodes[n1][1]
39    lat2 = self.data.rnodes[n2][0]
40    lon2 = self.data.rnodes[n2][1]
41    # TODO: projection issues
42    dlat = lat2 - lat1
43    dlon = lon2 - lon1
44    dist2 = dlat * dlat + dlon * dlon
45    dist = math.sqrt(dist2)
46    return(dist)
47 
48  def doRoute(self,start,end):
49    """Do the routing"""
50    self.searchEnd = end
51    closed = [start]
52    self.queue = []
53   
54    # Start by queueing all outbound links from the start node
55    blankQueueItem = {'end':-1,'distance':0,'nodes':str(start)}
56
57    try:
58      for i, weight in self.data.routing[start].items():
59        self.addToQueue(start,i, blankQueueItem, weight)
60    except KeyError:
61      return('no_such_node',[])
62
63    # Limit for how long it will search
64    count = 0
65    while count < 1000000:
66      count = count + 1
67      try:
68        nextItem = self.queue.pop(0)
69      except IndexError:
70        # Queue is empty: failed
71        # TODO: return partial route?
72        return('no_route',[])
73      x = nextItem['end']
74      if x in closed:
75        continue
76      if x == end:
77        # Found the end node - success
78        routeNodes = [int(i) for i in nextItem['nodes'].split(",")]
79        return('success', routeNodes)
80      closed.append(x)
81      try:
82        for i, weight in self.data.routing[x].items():
83          if not i in closed:
84            self.addToQueue(x,i,nextItem, weight)
85      except KeyError:
86        pass
87    else:
88      return('gave_up',[])
89 
90  def addToQueue(self,start,end, queueSoFar, weight = 1):
91    """Add another potential route to the queue"""
92
93    # getArea() checks that map data is available around the end-point,
94    # and downloads it if necessary
95    #
96    # TODO: we could reduce downloads even more by only getting data around
97    # the tip of the route, rather than around all nodes linked from the tip
98    end_pos = self.data.rnodes[end]
99    self.data.getArea(end_pos[0], end_pos[1])
100   
101    # If already in queue, ignore
102    for test in self.queue:
103      if test['end'] == end:
104        return
105    distance = self.distance(start, end)
106    if(weight == 0):
107      return
108    distance = distance / weight
109   
110    # Create a hash for all the route's attributes
111    distanceSoFar = queueSoFar['distance']
112    queueItem = { \
113      'distance': distanceSoFar + distance,
114      'maxdistance': distanceSoFar + self.distance(end, self.searchEnd),
115      'nodes': queueSoFar['nodes'] + "," + str(end),
116      'end': end}
117   
118    # Try to insert, keeping the queue ordered by decreasing worst-case distance
119    count = 0
120    for test in self.queue:
121      if test['maxdistance'] > queueItem['maxdistance']:
122        self.queue.insert(count,queueItem)
123        break
124      count = count + 1
125    else:
126      self.queue.append(queueItem)
127
128if __name__ == "__main__":
129  # Test suite - do a little bit of easy routing in birmingham
130  data = LoadOsm("cycle")
131
132  node1 = data.findNode(52.552394,-1.818763)
133  node2 = data.findNode(52.563368,-1.818291)
134
135  print node1
136  print node2
137
138  router = Router(data)
139  result, route = router.doRoute(node1, node2)
140  if result == 'success':
141    # list the nodes
142    print route
143
144    # list the lat/long
145    for i in route:
146      node = data.rnodes[i]
147      print "%d: %f,%f" % (i,node[0],node[1])
148  else:
149    print "Failed (%s)" % result
150
Note: See TracBrowser for help on using the repository browser.