Hi,The attached work-in-progress patch, when applied in the sites/rails_port directory of an SVN checkout, should result in working routing within the main rails site, based on a route_info table. The attached (equally work-in-progress) tarball contains a small Java app for generating the route_info table.
What it does do: - Uses David Earl's Namefinder to find ways - Finds a shortest car route between those ways using A* - Spits that route out What it doesn't do:- Proper directions. This seems like the easy part once efficient routing is done. - Work very quickly. It's fine for short routes, very slow for longer ones. - Map overlays, anything pretty like that. Again, I'd like to get the core routing sorted first.
- Bike routes, etc. Easy to do once the core of the thing's worked out. - Fastest routes. Trivial modification once the core etc...I'd planned to clean the code up more before posting, but the strains on my free time are not becoming less.
I'm now reading about highway hierarchies as an alternative to A*, since A* is not sufficiently performant for long routes, even with this (reasonably) optimised implementation.
You can try it out at http://ensued.net:3000/route/plan - please be gentle, the server's not going to deal well with lots of simultaneous route planning.
-- Jon Bright Silicon Circus Ltd. http://www.siliconcircus.com
Index: app/helpers/route_helper.rb
===================================================================
--- app/helpers/route_helper.rb (revision 0)
+++ app/helpers/route_helper.rb (revision 0)
@@ -0,0 +1,2 @@
+module RouteHelper
+end
Index: app/models/route_info.rb
===================================================================
--- app/models/route_info.rb (revision 0)
+++ app/models/route_info.rb (revision 0)
@@ -0,0 +1,6 @@
+class RouteInfo < ActiveRecord::Base
+# belongs_to :next_node, :foreign_key => 'next_node', :class_name => 'Node'
+ def dist
+ return self.distance.to_f / 1000000
+ end
+end
Index: app/controllers/route_controller.rb
===================================================================
--- app/controllers/route_controller.rb (revision 0)
+++ app/controllers/route_controller.rb (revision 0)
@@ -0,0 +1,353 @@
+class Numeric
+ def to_radians
+ (self * Math::PI) / 180
+ end
+end
+
+Node.new # Cause Rails to go away and work out there's a Node class before
+ # we try and extend it. There's probably a better way to do this?
+
+class Node
+
+ def radlat
+ if not defined? @radlat
+ @radlat = lat.to_radians
+ end
+ @radlat
+ end
+
+ def radlon
+ if not defined? @radlon
+ @radlon = lon.to_radians
+ end
+ @radlon
+ end
+
+ def calc_distance(other)
+ if not defined? @@radius
+ avglat = (radlat + other.radlat) / 2.0
+ @@radius = 6378.0 - 21.0 * Math.sin(avglat)
+ end
+
+# latdiff = other.lat - lat
+# londiff = other.lon - lon
+# x = (londiff)*Math.cos(radlat)*Math::PI/180
+# y = (latdiff)*Math::PI/180
+# d = @@radius * Math.sqrt(x*x + y*y)
+# return d
+
+ # Haversine
+ latdiff = other.radlat - radlat
+ londiff = other.radlon - radlon
+
+ sinlat = Math.sin(latdiff/2.0)
+ sinlon = Math.sin(londiff/2.0)
+
+ a = (sinlat*sinlat)+Math.cos(radlat)*Math.cos(other.radlat)*(sinlon*sinlon)
+
+ b = Math.sqrt(a)
+
+ if (b>1.0)
+ b = 1.0
+ end
+
+ c = 2.0*Math.asin(b)
+
+ @@radius*c
+ end
+end
+
+Way.new # Cause Rails to go away and work out there's a Way class before
+ # we try and extend it. There's probably a better way to do this?
+
+class Way
+ def appropriate?(logger, asc)
+ if not tags.has_key? "highway"
+# logger.info("No highway")
+ return false
+ end
+
+ allowed = [ "motorway", "motorway_link", "primary", "primary_link",
"secondary", "tertiary", "unclassified", "residential" ]
+ if not allowed.include? tags["highway"]
+# logger.info("Wrong highway type: "+tags["highway"])
+ return false
+ end
+
+ if (tags["highway"]=="motorway" or tags["highway"]=="motorway_link" or
tags.has_key? "oneway") and not asc
+ false
+ else
+ true
+ end
+
+ true
+ end
+end
+
+class RouteController < ApplicationController
+ layout 'site'
+
+ def plan
+ end
+
+ class RoutePart
+ def initialize(end_node, dest_node, distance, prev_part, way)
+ @dest_node = dest_node
+ @distance = distance
+ @next_parts = []
+ @heuristic = end_node.calc_distance(dest_node)[EMAIL PROTECTED]
+ @prev_part = prev_part
+ @way = way
+ end
+ def dest_node
+ @dest_node
+ end
+ def distance
+ @distance
+ end
+ def distance=(distance)
+ @distance=distance
+ end
+ def next_parts
+ @next_parts
+ end
+ def next_parts=(parts)
+ @next_parts = parts
+ end
+ def heuristic
+ @heuristic
+ end
+ def prev_part=(part)
+ @prev_part = part
+ end
+ def prev_part
+ @prev_part
+ end
+ def way=(w)
+ @way=w
+ end
+ def way
+ @way
+ end
+ include Comparable
+ def <=>(other)
+ @heuristic <=> other.heuristic
+ end
+ def appropriate?(way_id, asc)
+ tags = WayTag.find(:all, :conditions => ["id=? and k in
(\"highway\",\"oneway\")", way_id])
+ if tags.length==0
+ return false
+ end
+ if tags.length==2
+ if tags[0].k=="highway"
+ highway=tags[0].v
+ oneway=tags[1].v
+ else
+ oneway=tags[0].v
+ highway=tags[1].v
+ end
+ elsif tags.length==1
+ if tags[0].k=="oneway"
+ return false
+ end
+ highway=tags[0].v
+ oneway=nil
+ end
+
+ allowed = [ "motorway", "motorway_link", "primary", "primary_link",
"secondary", "tertiary", "unclassified", "residential" ]
+ if not allowed.include? highway
+ return false
+ end
+
+ if (highway=="motorway" or highway=="motorway_link" or not oneway.nil?)
and not asc
+ false
+ else
+ true
+ end
+
+ true
+ end
+ def progress(end_node,orig_dist,logger)
+ nxt = []
+ if @prev_part.nil?
+ prev_node=0
+ else
+ [EMAIL PROTECTED]
+ end
+ steps = RouteInfo.find(:all, :conditions => ["node_id=? AND
next_node!=?", @dest_node, prev_node ])
+ steps.each do |s|
+# if not appropriate?(s.way_id, s.rightway)
+# next
+# end
+# nxt << RoutePart.new(end_node, Node.find(s.next_node),
@distance+s.dist, self, s.way_id)
+ p = RoutePart.new(end_node, Node.find(s.next_node), @distance+s.dist,
self, s.way_id)
+ if p.heuristic-p.distance > orig_dist*1.02
+ logger.info "Throwing out"
+ next
+ end
+ nxt << p
+# nxt << RoutePart.new(end_node, s.next_node, @distance+s.dist, self,
s.way_id)
+ end
+ nxt
+ end
+ def propagate_distance_change(change)
+ @next_parts.each do |p|
+ p.distance=p.distance+change
+ if p.distance<=0
+ raise "Invalid distance"
+ end
+ p.propagate_distance_change(change)
+ end
+ end
+ end
+
+ def calculate
+#require 'ruby-prof'
+#RubyProf.start
+
+ ActiveRecord::Base.connection.execute 'SET NAMES UTF8' # This shouldn't
really be necessary here, I think
+
+ @start = Time.new
+ @start_node = find_name(params[:route][:start])
+ @end_node = find_name(params[:route][:end])
+ @distance = @start_node.calc_distance(@end_node)
+
+ @found_names = Time.new
+ part = RoutePart.new(@end_node, @start_node, 0, nil, nil)
+
+ routes = [ part ]
+ visited = { @start_node => part }
+ iterations = 0
+
+ until routes.length==0 or [EMAIL PROTECTED] or iterations==100000
+ if iterations%100==0
+ logger.info "Done #{iterations} iterations, best
#{routes[0].distance}/#{routes[0].heuristic}, total #{routes.length}"
+ end
+
+ nxt = routes[0].progress(@end_node,@distance,logger)
+ nxt.each do |s|
+ if visited.has_key? s.dest_node
+ # We've already reached this route part's dest node
+ other_part = visited[s.dest_node]
+
+ next if other_part.distance < s.distance # If the other route to the
dest node is shorter, skip our current route part
+
+ unless routes.delete(other_part).nil?
+ # If the other, longer route to the dest node was in the routes
array, add this route part to the routes array
+ i = 1 # Don't start at 0, since that element will shortly be removed
+ while i<routes.length and routes[i].heuristic<s.heuristic
+ i = i + 1
+ end
+ if i==routes.length
+ routes << s
+ else
+ routes.insert(i, s)
+ end
+ else
+ # If it wasn't, then it must have progressed. Take over its
progressions.
+ s.next_parts=other_part.next_parts
+ s.next_parts.each do |part|
+ part.prev_part=s
+ end
+ if other_part.prev_part.next_parts.delete(other_part).nil?
+ raise "Structure inconsistency"
+ end
+ other_part.next_parts=[]
+
+ s.propagate_distance_change(s.distance-other_part.distance) #
Reduce the distance of the progressions by the amount we've saved
+ end
+ else
+ # We haven't visited this route part's dest node yet. Add ourselves
to the routes array.
+ i = 1 # Don't start at 0, since that element will shortly be removed
+ while i<routes.length and routes[i].heuristic<s.heuristic
+ i = i + 1
+ end
+ if i==routes.length
+ routes << s
+ else
+ routes.insert(i, s)
+ end
+ end
+ # If we get here, then we're the best visitor to this node so far
+ visited[s.dest_node] = s
+
+ # ...and we're one of the next parts of route 0
+ routes[0].next_parts << s
+ end
+ # OK, all done, remove element 0 from the routes array, since it's
somehow progressed (even if the progression was "all dead ends")
+ routes.delete_at(0)
+
+ iterations = iterations + 1
+ end
+ @end = Time.new
+#result=RubyProf.stop
+#sio = StringIO.new
+#printer = RubyProf::GraphHtmlPrinter.new(result)
+#printer.print(sio, 0)
+# @profile=sio.string
+
+ if routes.length==0
+ flash[:error] = "Sorry, there doesn't seem to be a route between those
places"
+ redirect_to :controller => 'route', :action => 'plan'
+ elsif [EMAIL PROTECTED]
+ flash[:error] = "Sorry, I couldn't find a route between those places
even after trying #{iterations} times"
+ redirect_to :controller => 'route', :action => 'plan'
+ else
+ logger.info "Done #{iterations} iterations, best
#{routes[0].distance}/#{routes[0].heuristic}, total #{routes.length}"
+ last_part = routes[0]
+ @parts = []
+ until last_part.prev_part.nil?
+ @parts << last_part
+ last_part.way=Way.find(last_part.way)
+ last_part = last_part.prev_part
+ end
+ @parts.reverse!
+ end
+ end
+
+ protected
+
+ def find_name(name)
+ # ATM, we fetch results from David's name finder via HTTP. When a ruby
implementation
+ # of this is available in the future, we can deal with it directly.
+
+ require 'net/http'
+ require 'uri'
+
+ response =
Net::HTTP.get_response(URI.parse(URI.escape('http://www.frankieandshadow.com/osm/search.xml?find='+name)))
+ results = REXML::Document.new(response.body)
+ if results.root.attributes['error']
+ flash[:error] = 'Sorry, I couldn\'t find the place you meant by
"'+name+'"'
+ redirect_to :controller => 'route', :action => 'plan'
+ end
+ node = nil
+ results.root.elements.each do |element|
+ if element.name=='named' and element.attributes['type']=='way'
+ way = Way.find(element.attributes['id'])
+ logger.info "Found way #{way.id}"
+ way.nds.each do |n|
+ logger.info "Checking node #{n}"
+ if RouteInfo.exists?(:node_id => n)
+ node = Node.find(n)
+ logger.info "Looks good, breaking"
+ break
+ end
+ logger.info "No joy"
+ end
+ break
+ elsif element.name=='named' and element.attributes['type']=='node'
+ node = Node.find(element.attributes['id'])
+ break
+ end
+ end
+ if node.nil?
+ # Nothing useful found
+ logger.info "Nil node, giving up"
+ flash[:error] = 'Sorry, I couldn\'t find the place you meant by
"'+name+'"'
+ redirect_to :controller => 'route', :action => 'plan'
+ end
+# Way.find(:all, :conditions => [ "
+ logger.info "Returning node #{node.id}"
+ node
+ end
+
+end
Index: app/views/route/plan.rhtml
===================================================================
--- app/views/route/plan.rhtml (revision 0)
+++ app/views/route/plan.rhtml (revision 0)
@@ -0,0 +1,7 @@
+<h1>Plan a route</h1>
+<p style="color: red"><%= flash[:error] %></p>
+<% form_tag '/route/calculate' do %>
+ <p>Start from? <%= text_field 'route', 'start', :size => 40 -%></p>
+ <p>Where to? <%= text_field 'route', 'end', :size => 40 -%></p>
+ <p><%= submit_tag 'Go forth!' -%></p>
+<% end %>
Index: app/views/route/calculate.rhtml
===================================================================
--- app/views/route/calculate.rhtml (revision 0)
+++ app/views/route/calculate.rhtml (revision 0)
@@ -0,0 +1,43 @@
+<h1>Route calculation</h1>
+<p>s→e <%= @distance -%></p>
+<p>Found start node <%= @start_node.id.to_s+", "[EMAIL PROTECTED]", "[EMAIL
PROTECTED] -%></p>
+<p>Found end node <%= @end_node.id.to_s+", "[EMAIL PROTECTED]", "[EMAIL
PROTECTED] -%></p>
+<p>Found start way <%= @start_way -%></p>
+<p>Found end way <%= @end_way -%></p>
+<p>Spent <%= @[EMAIL PROTECTED] %>s finding names, <%= @[EMAIL PROTECTED] %>
routing.</p>
+<%
+last_name="xyzzy"
+last_ref=nil
[EMAIL PROTECTED] do |part|
+ name=part.way.tags["name"]
+ ref=part.way.tags["ref"]
+ if ref.nil?
+ ref=part.way.tags["nat_ref"]
+ if ref.nil?
+ ref=part.way.tags["reg_ref"]
+ if ref.nil?
+ ref=part.way.tags["loc_ref"]
+ end
+ end
+ end
+ if ref==name
+ ref = nil
+ end
+ if name==last_name and ref==last_ref
+ next
+ end
+ last_name=name
+ last_ref=ref -%>
+<% if not name.nil? and not ref.nil? -%>
+<p><%=h name -%> (<%=h ref -%>), <%= part.distance -%>km</p>
+<% elsif not name.nil? -%>
+<p><%=h name -%>, <%= part.distance -%>km</p>
+<% elsif not ref.nil? -%>
+<p><%=h ref -%>, <%= part.distance -%>km</p>
+<% elsif part.way.tags["highway"]=="motorway_link" or
part.way.tags["highway"]=="primary_link" -%>
+<p>Slip road, <%= part.distance -%>km</p>
+<% else %>
+<p>Unnamed street, <%= part.distance -%>km</p>
+<% end %>
+<% end %>
+<%= @profile %>
Index: app/views/layouts/site.rhtml
===================================================================
--- app/views/layouts/site.rhtml (revision 5254)
+++ app/views/layouts/site.rhtml (working copy)
@@ -36,14 +36,17 @@
viewclass = ''
editclass = ''
traceclass = ''
+ routeclass = ''
viewclass = 'active' if params['controller'] == 'site' and
params['action'] == 'index'
editclass = 'active' if params['controller'] == 'site' and
params['action'] == 'edit'
editclass = 'active' if params['controller'] == 'campaign'
traceclass = 'active' if params['controller'] == 'trace'
+ routeclass = 'active' if params['controller'] == 'route'
%>
<li><%= link_to 'View', {:controller => 'site', :action => 'index'},
{:id => 'viewanchor', :title => 'view maps', :class => viewclass } %></li>
<li><%= link_to 'Edit', {:controller => 'site', :action => 'edit'},
{:id => 'editanchor', :title => 'edit maps', :class => editclass } %></li>
<li><%= link_to 'GPS traces', {:controller => 'trace', :action =>
'list'}, {:id => 'traceanchor', :title => 'manage traces', :class => traceclass
} %></li>
+ <li><%= link_to 'Route', {:controller => 'route', :action => 'plan'},
{:id => 'routeanchor', :title => 'plan routes', :class => routeclass } %></li>
</ul>
</div>
Index: config/routes.rb
===================================================================
--- config/routes.rb (revision 5254)
+++ config/routes.rb (working copy)
@@ -32,8 +32,6 @@
map.connect "api/#{API_VERSION}/map", :controller => 'api', :action => 'map'
map.connect "api/#{API_VERSION}/trackpoints", :controller => 'api', :action
=> 'trackpoints'
-
- map.connect "api/#{API_VERSION}/changes", :controller => 'api', :action =>
'changes'
map.connect "api/#{API_VERSION}/search", :controller => 'search', :action =>
'search_all'
map.connect "api/#{API_VERSION}/ways/search", :controller => 'search',
:action => 'search_ways'
@@ -92,10 +90,13 @@
map.connect '/user/:display_name/traces/:id/picture', :controller =>
'trace', :action => 'picture'
map.connect '/user/:display_name/traces/:id/icon', :controller => 'trace',
:action => 'icon'
+ # routes
+ map.connect '/route/plan', :controller => 'route', :action => 'plan'
+ map.connect '/route/calculate', :controller => 'route', :action =>
'calculate'
+
# user pages
+ map.connect '/user/:display_name/make_friend', :controller => 'user',
:action => 'make_friend'
map.connect '/user/:display_name', :controller => 'user', :action => 'view'
- map.connect '/user/:display_name/make_friend', :controller => 'user',
:action => 'make_friend'
- map.connect '/user/:display_name/remove_friend', :controller => 'user',
:action => 'remove_friend'
map.connect '/user/:display_name/diary', :controller => 'diary_entry',
:action => 'list'
map.connect '/user/:display_name/diary/:id', :controller => 'diary_entry',
:action => 'list', :id => /\d+/
map.connect '/user/:display_name/diary/rss', :controller => 'diary_entry',
:action => 'rss'
Index: config/environment.rb
===================================================================
--- config/environment.rb (revision 5254)
+++ config/environment.rb (working copy)
@@ -37,7 +37,7 @@
# Force all environments to use the same logger level
# (by default production uses :info, the others :debug)
- # config.log_level = :debug
+ config.log_level = :info
# Use our custom logger
config.logger = OSMLogger.new(config.log_path)
jrouteosm.tar.gz
Description: application/gzip
_______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
