module OverpassGraph
Constants
- MAXSIZE
- TIMEOUT
Public Class Methods
create_adjacency_hash(roads, vertices, directed, metric)
click to toggle source
# File lib/overpass_graph/create_adjacency_hash.rb, line 5 def self.create_adjacency_hash(roads, vertices, directed, metric) """ Creates an adjacency hash from a list of roads and set of vertices. The graph is represented as a hash of hashes, where the keys are coordinate pairs [lat, lon] (as a list), and the values are hashes that contain neighbor coordinate pairs as keys and edge lengths as values. If an edge exists from a coordinate pair, x, to coordinate pair, y, of length z, then adj[x][y] will equal z. Here's an example: { [lat1, lon1] => { [lat2, lon2] => distance1, [lat3, lon3] => distance2 } } In this example, there is an edge from [lat1, lon1] to [lat2, lon2] of length distance1 and an edge from [lat1, lon1] to [lat3, lon3] of length distance2. :return: adjacency hash representation of a graph """ adj = {} roads.each do |road| road_nodes = road[:geometry] start_vertex = [road_nodes[0][:lat], road_nodes[0][:lon]] if !adj.has_key?(start_vertex) adj[start_vertex] = {} end # Need to keep track of the distance travelled along road, the previous node (to increment distance) # and the previous vertex. Upon discovering a new vertex in the iteration, an edge is created from # the previous vertex to the discovered vertex (and if the road is two-way, from the discovered # vertex back to the previous vertex) distance = 0 prev_node = { coords: start_vertex, distance: distance } prev_vertex = { coords: start_vertex, distance: distance } (1..road_nodes.length - 1).each do |i| current = [road_nodes[i][:lat], road_nodes[i][:lon]] # updating distance with previous node and current node if !metric distance += Haversine.distance(prev_node[:coords][0], prev_node[:coords][1], current[0], current[1]).to_miles else distance += Haversine.distance(prev_node[:coords][0], prev_node[:coords][1], current[0], current[1]).to_km end # if the current node is in the set of vertices, calculate the distance between it and the previous vertex. # Then add an edge of that length from the previous vertex to the current node. If the road is two-way, also add an edge # from the current node back to the previous vertex. if vertices === current distance_between = distance - prev_vertex[:distance] if road[:tags][:oneway] != 'yes' || !directed if adj.has_key?(current) adj[current][prev_vertex[:coords]] = distance_between else adj[current] = { prev_vertex[:coords] => distance_between } end end if adj.has_key?(prev_vertex[:coords]) adj[prev_vertex[:coords]][current] = distance_between else adj[prev_vertex[:coords]] = { current => distance_between } end prev_vertex = {coords: current, distance: distance} end # previous node kept track of to calculate distance along the road prev_node = {coords: current, distance: distance} end end return adj end
create_vertex_set(roads)
click to toggle source
# File lib/overpass_graph/create_vertex_set.rb, line 5 def self.create_vertex_set(roads) ''' Function to process a list of road hashes and return the set of vertex coordinates from that list. Vertices are any coordinates that either: a) begin or end a road or b) are found within at least two roads (i.e. intersections) :return: a set of vertices ''' # frequency map of times a given node appears in all roads node_count = {} roads.each do |road| road_nodes = road[:geometry] start_vertex = [road_nodes[0][:lat], road_nodes[0][:lon]] end_vertex = [road_nodes[-1][:lat], road_nodes[-1][:lon]] # this ensures that each start and end vertex will be included in the set of returned # vertices, because post iteration they'll both have at least 2 in node_count if !node_count.has_key?(start_vertex) node_count[start_vertex] = 1 end if !node_count.has_key?(end_vertex) node_count[end_vertex] = 1 end # this will pick up any nodes that form intersections (i.e. are nodes in multiple roads), # but aren't the starting or ending nodes of any road road_nodes.each do |node| current = [node[:lat], node[:lon]] if !node_count.has_key?(current) node_count[current] = 1 else node_count[current] += 1 end end end return Set.new( node_count.filter{ |node, num| num > 1 }.keys ) end
get_roads(north, east, south, west, allowed_values, disallowed_values)
click to toggle source
# File lib/overpass_graph/get_roads.rb, line 8 def self.get_roads(north, east, south, west, allowed_values, disallowed_values) ''' Gets roads by querying the Overpass API. :return: a list of hashes with information about all the roads in the bounding box ''' if 90 < north || 90 < south || north < -90 || south < -90 raise "Latitudes in bounding boxes must be between -90.0 and 90.0" end if 180 < east || 180 < west || east < -180 || west < -180 raise "Longitudes in bounding boxes must be between -180.0 and 180.0" end if north < south raise "Northern latitude is less than southern latitude.\nDid you mean 'overpass_graph(#{south}, #{east}, #{north}, #{west}...)" end if east < west puts "OVERPASS_GRAPH WARNING: Eastern longitude is less than western longitude.\n"\ "In most cases this is not intended by the developer.\n"\ "Perhaps you meant 'overpass_graph(#{north}, #{west}, #{south}, #{east}...)'?\n"\ "Find out more here: https://dev.overpass-api.de/overpass-doc/en/full_data/bbox.html" end options = { bbox: { s: south, n: north, w: west, e: east }, timeout: TIMEOUT, maxsize: MAXSIZE } allowed_string = allowed_values.map{|allowed_value| "[highway=#{allowed_value}]" }.join() disallowed_string = disallowed_values.map{|disallowed_value| "[highway!=#{disallowed_value}]" }.join() # query for all highways within the bounding box overpass = OverpassAPI::QL.new(options) query = "way[highway]#{allowed_string}#{disallowed_string};(._;>;);out geom;" begin response = overpass.query(query) rescue # try again if first request is denied, if second request is denied, throw the exception response = overpass.query(query) end # filter out all partial roads and return the filtered hash elements = response[:elements] return elements.filter { |element| element[:type] == "way" } end
graph(north, east, south, west, directed: true, filter_by_allowing: true, filtered_values:[], metric: false)
click to toggle source
# File lib/overpass_graph.rb, line 7 def self.graph(north, east, south, west, directed: true, filter_by_allowing: true, filtered_values:[], metric: false) ''' Primary function for the library. The user may specify whether to filter by allowing or not, in addition to a few other options. If they choose to filter by allowing certain road types, the get roads function will be passed an empty array for disallowed values. If they choose to filter by disallowing certain road types, the get roads function will be passed an empty array for allowed values. :return: adjacency map representation of a graph ''' allowed_values = [] disallowed_values = [] filter_by_allowing ? allowed_values = filtered_values : disallowed_values = filtered_values roads = get_roads(north, east, south, west, allowed_values, disallowed_values) vertices = create_vertex_set(roads) return create_adjacency_hash(roads, vertices, directed, metric) end