source: subversion/applications/routing/pyroute/route.py @ 20924

Last change on this file since 20924 was 5495, checked in by ojw, 12 years ago

Changes from the weekend

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