module IbottaGeohash

Pure ruby geohash library

Based on: pr_geohash
https://github.com/masuidrive/pr_geohash
Yuichiro MASUI
Geohash library for pure ruby
Distributed under the MIT License

Based library is

// github.com/davetroy/geohash-js/blob/master/geohash.js // geohash.js // Geohash library for Javascript // © 2008 David Troy // Distributed under the MIT License

Constants

BASE32
BITS

needed for geohash encoding

BORDERS
DEG_LAT_IN_METERS
DEG_TO_RAD
EARTH_RADIUS_IN_METERS

needed for bounding box calculations

MERCATOR

not sure min is needed

NEIGHBORS
RAD_TO_DEG
VERSION

Public Class Methods

adjacent(geohash, dir) click to toggle source

calculate one adjacent neighbor

@param [String] geohash
@param [Symbol] dir which direction (top, right, bottom left)
@return [String] neighbor in that direction (or nil if invalid)
# File lib/ibotta_geohash.rb, line 138
def adjacent(geohash, dir)
  #stop recursion if empty
  return if geohash.nil? || geohash.empty?
  #get last character
  base, lastChr = geohash[0..-2], geohash[-1,1]
  type = (geohash.length % 2)==1 ? :odd : :even
  #if bit is border, get adjacency of base hash
  if BORDERS[dir][type].include?(lastChr)
    base = adjacent(base, dir)
    if base.nil?
      return if dir == :top || dir == :bottom
      base = ''
    end
  end
  #add back new neighbor character
  base + BASE32[NEIGHBORS[dir][type].index(lastChr),1]
end
areas_by_radius(lat, lon, radius_meters) click to toggle source

get geohashes covering a radius

@param [Float] lat
@param [Flaot] lon
@param [Float] radius_meters
@return [Array<String>] hashes (neighbors and center) covering radius in clockwise (top, topright, right, ...). neighbors not covering radius are excluded
# File lib/ibotta_geohash.rb, line 161
def areas_by_radius(lat, lon, radius_meters)
  #get min/max latitude and longitude of radius around point
  min_lat, min_lon, max_lat, max_lon = radius_box = bounding_box(lat, lon, radius_meters)

  #estimate the size of boxes to target
  steps = estimate_steps_by_radius(radius_meters)
  #re-encode point using steps
  #the geohashes are composed of 32 distinct numbers/letters, basically base 32
  #bits are composed of 1s and 0s, base 2 or binary
  #steps is the length of the binary number for longitude and latitude, and the combined length of the binary string (which interleaves both the longitude and latitude) is 2*steps
  # since 32 is 2^5, while 2 is 2^1, the length of a base 32 number will be the length of a binary number divided by 5 and plus 1 (32 base 10 = 10000 base 2 = 10 base 32).
  str_len = steps*2/5 + 1
  hash = encode(lat, lon, str_len)

  #get neighbors of box
  neighbors = neighbors(hash)
  neighbors_neighbors = neighbors.each_with_object([]) {|neighbor, nb| nb << neighbors(neighbor)}

  # 25 geohashes surrounding the original
  nb = neighbors_neighbors.flatten.uniq

  # remove those geohashes that are outside the bounding box
  nb.each do |neighbor|
    n_latlng_low, n_latlng_high = decode(neighbor)
    if n_latlng_low[0] > max_lat or n_latlng_low[1] > max_lon or n_latlng_high[0] < min_lat or n_latlng_high[1] < min_lon
      nb -= [neighbor]
    end
  end

  #return remaining neighbor list
  nb
end
bounding_box(lat, lon, radius_meters) click to toggle source

get bounding box around a radius

NOTE: this breaks down at the poles (which is fine, we stop geocoding at the poles too)
NOTE: this this is not WGS84 accurate (does not take into account oblong latitude). But as this is used for
  estimation anyway, thats probably fine
@todo  reorder return to match decode?
@param [Float] lat
@param [Float] lon
@param [Flaot] radius_meters
@return [Array] min_lat, min_long, max_lat, max_long
# File lib/ibotta_geohash.rb, line 217
def bounding_box(lat, lon, radius_meters)
  radius_meters  = radius_meters.to_f
  delta_lat = radius_meters / DEG_LAT_IN_METERS
  delta_lon = radius_meters / (DEG_LAT_IN_METERS * Math.cos(lat * DEG_TO_RAD))
  [
    lat - delta_lat,
    lon - delta_lon,
    lat + delta_lat,
    lon + delta_lon
  ]
end
decode(geohash) click to toggle source

decode bounding box from geohash string

@todo  reorder bounds?
@todo  see if faster way (less array access?)
@param [String] geohash string
@return [Array<Array>] decoded bounding box [[south latitude, west longitude],[north latitude, east longitude]]
# File lib/ibotta_geohash.rb, line 62
def decode(geohash)
  #starting bounding box (as if entire world)
  latlng = [[-90.0, 90.0], [-180.0, 180.0]]
  #alternate lat/long (starting at long)
  is_lng = 1
  geohash.downcase.each_char do |c|
    BITS.each do |mask|
      #working on low or high bits?
      lowhigh = (BASE32.index(c) & mask) == 0 ? 1 : 0
      #calculate as half of current box
      latlng[is_lng][lowhigh] = (latlng[is_lng][0] + latlng[is_lng][1]) / 2
      #flip longitude bits
      is_lng ^= 1
    end
  end
  #transpose to low, high lat/long
  latlng.transpose
end
decode_center(geohash) click to toggle source

decode center of geohash area

@todo  see if faster way? other libs do this first, calc bounding from it
@param [String] geohash string
@return [Array<Float>] latitude, longitude of center
# File lib/ibotta_geohash.rb, line 85
def decode_center(geohash)
  res = decode(geohash)
  #get center of each set
  [((res[0][0] + res[1][0]) / 2), ((res[0][1] + res[1][1]) / 2)]
end
encode(latitude, longitude, precision=12) click to toggle source

Encode latitude and longitude into geohash string

@todo  see if faster way? less array access?
@param [Float] latitude
@param [Float] longitude
@param [Integer] precision number of characters
@return [String] encoded
# File lib/ibotta_geohash.rb, line 97
def encode(latitude, longitude, precision=12)
  latlng = [latitude, longitude]
  #start at whole world
  points = [[-90.0, 90.0], [-180.0, 180.0]]
  #alternate lat/long (starting at long)
  is_lng = 1
  #for each character
  (0...precision).map do
    #character value is ch
    ch = 0
    5.times do |bit|
      #get midpoints of current calculation
      mid = (points[is_lng][0] + points[is_lng][1]) / 2
      #min or max value
      minmax = latlng[is_lng] > mid ? 0 : 1
      points[is_lng][minmax] = mid
      #add bits to character
      ch |= BITS[bit] if latlng[is_lng] > mid
      #flip bits
      is_lng ^= 1
    end
    #map value to character
    BASE32[ch,1]
  end.join
end
estimate_steps_by_radius(radius_meters) click to toggle source

estimate steps needed to cover radius

@param [Float] radius_meters
@return [Integer] steps required
# File lib/ibotta_geohash.rb, line 197
def estimate_steps_by_radius(radius_meters)
  step = 1
  v = radius_meters
  while v < MERCATOR.max
    v *= 2
    step += 1
  end
  step -= 1
  step
end
geohash_area(geohash) click to toggle source
# File lib/ibotta_geohash.rb, line 244
def geohash_area(geohash)
  latlngmin, latlngmax = decode(geohash)
  delta_lat_meters = (latlngmax[0] - latlngmin[0]) * DEG_LAT_IN_METERS
  delta_lng_meters = (latlngmax[1] - latlngmin[1]) * (DEG_LAT_IN_METERS * Math.cos(latlngmax[0] * DEG_TO_RAD))
  area = delta_lat_meters * delta_lng_meters
end
haversine_distance(lat1, lon1, lat2, lon2) click to toggle source

haversine distance (distance between two coordinate points) in meters

# File lib/ibotta_geohash.rb, line 230
def haversine_distance(lat1, lon1, lat2, lon2)
  r = EARTH_RADIUS_IN_METERS
  phi1 = lat1 * DEG_TO_RAD
  phi2 = lat2 * DEG_TO_RAD
  delta_phi= (lat2-lat1) * DEG_TO_RAD
  delta_lambda = (lon2-lon1) * DEG_TO_RAD

  a = Math.sin(delta_phi/2) ** 2 +
      Math.cos(phi1) * Math.cos(phi2) *
      Math.sin(delta_lambda/2) ** 2
  c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a))
  d = r * c
end
neighbors(geohash) click to toggle source

Calculate each 8 direction neighbors as geohash @param [String] geohash @return [Array<String>] neighbors in clockwise (top, topright, right, …). Invalid regions at the poles are excluded

# File lib/ibotta_geohash.rb, line 126
def neighbors(geohash)
  #get all adjacencies (going around)
  [[:top, :right], [:right, :bottom], [:bottom, :left], [:left, :top]].map do |dirs|
    point = adjacent(geohash, dirs[0])
    [point, adjacent(point, dirs[1])]
  end.flatten.compact
end