Module: OverpassGraph

Defined in:
lib/overpass_graph.rb,
lib/overpass_graph/get_roads.rb,
lib/overpass_graph/create_vertex_set.rb,
lib/overpass_graph/create_adjacency_hash.rb

Constant Summary collapse

TIMEOUT =

in seconds (15m)

900
MAXSIZE =

about 1 GB (server may abort for queries near the uppper end of this range, especially at peak hours)

1_073_741_824

Class Method Summary collapse

Class Method Details

.create_adjacency_hash(roads, vertices, directed, metric) ⇒ Object 



5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
# 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) ⇒ Object 



5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# 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) ⇒ Object 



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# 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) ⇒ Object 



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# 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