source: subversion/applications/routing/pyroute-dev/pyroute.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:executable set to *
  • Property svn:keywords set to Rev
File size: 8.7 KB
Line 
1#!/usr/bin/env python
2# -*- coding: utf-8 -*-
3
4"""pyRoute, a routing program for OpenStreetMap-style data
5
6Usage:
7 pyroute.py [input OSM file] [start node] [end node]
8"""
9
10__version__ = "$Rev: 18454 $"
11__license__ = """This program is free software: you can redistribute it and/or modify
12it under the terms of the GNU General Public License as published by
13the Free Software Foundation, either version 3 of the License, or
14(at your option) any later version.
15
16This program is distributed in the hope that it will be useful,
17but WITHOUT ANY WARRANTY; without even the implied warranty of
18MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19GNU General Public License for more details.
20
21You should have received a copy of the GNU General Public License
22along with this program. If not, see <http://www.gnu.org/licenses/>."""
23_debug = 0
24
25
26import sys
27import cairo
28import math
29from xml.sax import make_parser, handler
30
31class GetRoutes(handler.ContentHandler):
32        """Parse an OSM file looking for routing information, and do routing with it"""
33        def __init__(self):
34                """Initialise an OSM-file parser"""
35                self.routing = {}
36                self.nodes = {}
37                self.minLon = 180
38                self.minLat = 90
39                self.maxLon = -180
40                self.maxLat = -90
41        def startElement(self, name, attrs):
42                """Handle XML elements"""
43                if name in('node','way','relation'):
44                        if name == 'node':
45                                """Nodes need to be stored"""
46                                id = int(attrs.get('id'))
47                                lat = float(attrs.get('lat'))
48                                lon = float(attrs.get('lon'))
49                                self.nodes[id] = (lat,lon)
50                                if lon < self.minLon:
51                                        self.minLon = lon
52                                if lat < self.minLat:
53                                        self.minLat = lat
54                                if lon > self.maxLon:
55                                        self.maxLon = lon
56                                if lat > self.maxLat:
57                                        self.maxLat = lat
58                        self.tags = {}
59                        self.waynodes = []
60                elif name == 'nd':
61                        """Nodes within a way -- add them to a list"""
62                        self.waynodes.append(int(attrs.get('ref')))
63                elif name == 'tag':
64                        """Tags - store them in a hash"""
65                        k,v = (attrs.get('k'), attrs.get('v'))
66                        if not k in ('created_by'):
67                                self.tags[k] = v
68        def endElement(self, name):
69                """Handle ways in the OSM data"""
70                if name == 'way':
71                        last = -1
72                        highway = self.tags.get('highway', '')
73                        railway = self.tags.get('railway', '')
74                        oneway = self.tags.get('oneway', '')
75                        reversible = not oneway in('yes','true','1')
76                        cyclable = highway in ('primary','secondary','tertiary','unclassified','minor','cycleway','residential', 'service')
77                        if cyclable:
78                                for i in self.waynodes:
79                                        if last != -1:
80                                                #print "%d -> %d & v.v." % (last, i)
81                                                self.addLink(last, i)
82                                                if reversible:
83                                                        self.addLink(i, last)
84                                        last = i
85
86        def addLink(self,fr,to):
87                """Add a routeable edge to the scenario"""
88                # Look for existing
89                try:
90                        if to in self.routing[fr]:
91                                #print "duplicate %d from %d" % (to,fr)
92                                return
93                        # Try to add to list. If list doesn't exist, create it
94                        self.routing[fr].append(to)
95                except KeyError:
96                        self.routing[fr] = [to]
97
98        def initProj(self,w,h, lat,lon, scale=1):
99                """Setup an image coordinate system"""
100                self.w = w
101                self.h = h
102                self.clat = lat
103                self.clon = lon
104                self.dlat = (self.maxLat - self.minLat) / scale
105                self.dlon = (self.maxLon - self.minLon) / scale
106
107        def project(self, lat, lon):
108                """Convert from lat/long to image coordinates"""
109                x = self.w * (0.5 + 0.5 * (lon - self.clon) / (0.5 * self.dlon))
110                y = self.h * (0.5 - 0.5 * (lat - self.clat) / (0.5 * self.dlat))
111                return(x,y)
112
113        def markNode(self,node,r,g,b):
114                """Mark a node on the map"""
115                self.ctx.set_source_rgb(r,g,b)
116                lat = self.nodes[node][0]
117                lon = self.nodes[node][1]
118                x,y = self.project(lat,lon)
119                self.ctx.arc(x,y,2, 0,2*3.14)
120                self.ctx.fill()
121
122        def markLine(self,n1,n2,r,g,b):
123                """Draw a line on the map between two nodes"""
124                self.ctx.set_source_rgba(r,g,b,0.3)
125                lat = self.nodes[n1][0]
126                lon = self.nodes[n1][1]
127                x,y = self.project(lat,lon)
128                self.ctx.move_to(x,y)
129                lat = self.nodes[n2][0]
130                lon = self.nodes[n2][1]
131                x,y = self.project(lat,lon)
132                self.ctx.line_to(x,y)
133                self.ctx.stroke()
134
135        def distance(self,n1,n2):
136                """Calculate distance between two nodes"""
137                lat1 = self.nodes[n1][0]
138                lon1 = self.nodes[n1][1]
139                lat2 = self.nodes[n2][0]
140                lon2 = self.nodes[n2][1]
141                # TODO: projection issues
142                dlat = lat2 - lat1
143                dlon = lon2 - lon1
144                dist2 = dlat * dlat + dlon * dlon
145                return(math.sqrt(dist2))
146
147        def doRouting(self, routeFrom, routeTo):
148                """Wrapper around the routing function, which creates the output image, etc"""
149                size = 800
150                scalemap = 5 # the bigger this is, the more the map zooms-in
151                # Centre the map halfway between start and finish
152                ctrLat = (self.nodes[routeFrom][0] + self.nodes[routeTo][0]) / 2
153                ctrLon = (self.nodes[routeFrom][1] + self.nodes[routeTo][1]) / 2
154                self.initProj(size, size, ctrLat, ctrLon, scalemap)
155                surface = cairo.ImageSurface(cairo.FORMAT_RGB24, self.w, self.h)
156
157                self.ctx = cairo.Context(surface)
158                # Dump all the nodes onto the map, to give the routes some context
159                self.ctx.set_source_rgb(1.0, 0.0, 0.0)
160                self.ctx.set_line_cap(cairo.LINE_CAP_ROUND)
161                for id,n in self.nodes.items():
162                        x,y = self.project(n[0], n[1])
163                        self.ctx.move_to(x,y)
164                        self.ctx.line_to(x,y)
165                        self.ctx.stroke()
166
167                # Do the routing itself
168                self.doRoute(routeFrom, routeTo)
169
170                # Highlight which nodes were the start and end
171                self.markNode(routeFrom,1,1,1)
172                self.markNode(routeTo,1,1,0)
173
174                # Image is complete
175                surface.write_to_png("output.png")
176
177        def doRoute(self,start,end):
178                """Do the routing"""
179                self.searchEnd = end
180                closed = [start]
181                self.queue = []
182
183                # Start by queueing all outbound links from the start node
184                blankQueueItem = {'end':-1,'distance':0,'nodes':str(start)}
185                for i in self.routing[start]:
186                        self.addToQueue(start,i, blankQueueItem)
187
188                # Limit for how long it will search (also useful for debugging step-by-step)
189                maxSteps = 10000
190                while maxSteps > 0:
191                        maxSteps = maxSteps - 1
192                        try:
193                                nextItem = self.queue.pop(0)
194                        except IndexError:
195                                print "Failed to find any route"
196                                return
197                        x = nextItem['end']
198                        if x in closed:
199                                continue
200                        self.markNode(x,0,0,1)
201                        if x == end:
202                                print "Success!"
203                                self.printRoute(nextItem)
204                                return
205                        closed.append(x)
206                        try:
207                                for i in self.routing[x]:
208                                        if not i in closed:
209                                                self.addToQueue(x,i,nextItem)
210                        except KeyError:
211                                pass
212                else:
213                        self.debugQueue()
214
215        def debugQueue(self):
216                """Display some information about the state of our queue"""
217                print "Queue now %d items long" % len(self.queue)
218                # Display on map
219                for i in self.queue:
220                        self.markNode(i['end'],0,0.5,0)
221
222        def printRoute(self,item):
223                """Output stage, for printing the route once found"""
224
225                # Route is stored as text initially. Split into a list
226                print "Route: %s" % item['nodes']
227                listNodes = [int(i) for i in item['nodes'].split(",")]
228
229                # Display the route on the map
230                last = -1
231                for i in listNodes:
232                        if last != -1:
233                                self.markLine(last,i,0.5,1.0,0.5)
234                        self.markNode(i,0.5,1.0,0.5)
235                        last = i
236
237                # Send the route to an OSM file
238                fout = open("route.osm", "w")
239                fout.write("<?xml version='1.0' encoding='UTF-8'?>");
240                fout.write("<osm version='0.5' generator='route.py'>");
241
242                for i in listNodes:
243                        fout.write("<node id='%d' lat='%f' lon='%f'>\n</node>\n" % ( \
244                                i,
245                                self.nodes[i][0],
246                                self.nodes[i][1]))
247
248                fout.write("<way id='1'>\n")
249                for i in listNodes:
250                        fout.write("<nd ref='%d' lat='%f' lon='%f' />\n" % ( \
251                                i,
252                                self.nodes[i][0],
253                                self.nodes[i][0]))
254                fout.write("</way>\n")
255                fout.write("</osm>")
256                fout.close()
257
258        def addToQueue(self,start,end, queueSoFar):
259                """Add another potential route to the queue"""
260
261                # If already in queue
262                for test in self.queue:
263                        if test['end'] == end:
264                                return
265                distance = self.distance(start, end)
266
267                # Create a hash for all the route's attributes
268                queueItem = {}
269                queueItem['distance'] = queueSoFar['distance'] + distance
270                queueItem['maxdistance'] = queueItem['distance'] + self.distance(end, self.searchEnd)
271                queueItem['nodes'] = queueSoFar['nodes'] + ","+str(end)
272                queueItem['end'] = end
273
274                # Try to insert, keeping the queue ordered by decreasing worst-case distance
275                count = 0
276                for test in self.queue:
277                        if test['maxdistance'] > queueItem['maxdistance']:
278                                self.queue.insert(count,queueItem)
279                                break
280                        count = count + 1
281                else:
282                        self.queue.append(queueItem)
283
284                # Show on the map
285                self.markLine(start,end,0.5,0.5,0.5)
286
287# Parse the supplied OSM file
288print "Loading data..."
289obj = GetRoutes()
290parser = make_parser()
291parser.setContentHandler(obj)
292parser.parse(sys.argv[1])
293print "Routing..."
294# Do routing between the two specified nodes
295obj.doRouting(int(sys.argv[2]), int(sys.argv[3]))
296
Note: See TracBrowser for help on using the repository browser.