source: subversion/applications/routing/pyroute-dev/route.py @ 18454

Last change on this file since 18454 was 18454, checked in by buerste, 10 years ago

-further updates of spaces to tabs

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