lib/short_link.rb

   1 ##
   2 # Encodes and decodes locations from Morton-coded "quad tile" strings. Each
   3 # variable-length string encodes to a precision of one pixel per tile (roughly,
   4 # since this computation is done in lat/lon coordinates, not mercator).
   5 # Each character encodes 3 bits of x and 3 of y, so there are extra characters
   6 # tacked on the end to make the zoom levels "work".
   7 module ShortLink
   8
   9   # array of 64 chars to encode 6 bits. this is almost like base64 encoding, but
  10   # the symbolic chars are different, as base64's + and / aren't very
  11   # URL-friendly.
  12   ARRAY = ('A'..'Z').to_a + ('a'..'z').to_a + ('0'..'9').to_a + ['_','@']
  13
  14   ##
  15   # Given a string encoding a location, returns the [lon, lat, z] tuple of that
  16   # location.
  17   def self.decode(str)
  18     x = 0
  19     y = 0
  20     z = 0
  21     z_offset = 0
  22
  23     str.each_char do |c|
  24       t = ARRAY.index c
  25       if t.nil?
  26         z_offset -= 1
  27       else
  28         3.times do
  29           x <<= 1; x = x | 1 unless (t & 32).zero?; t <<= 1
  30           y <<= 1; y = y | 1 unless (t & 32).zero?; t <<= 1
  31         end
  32         z += 3
  33       end
  34     end
  35     # pack the coordinates out to their original 32 bits.
  36     x <<= (32 - z)
  37     y <<= (32 - z)
  38
  39     # project the parameters back to their coordinate ranges.
  40     [(x * 360.0 / 2**32) - 180.0,
  41      (y * 180.0 / 2**32) - 90.0,
  42      z - 8 - (z_offset % 3)]
  43   end
  44
  45   ##
  46   # given a location and zoom, return a short string representing it.
  47   def self.encode(lon, lat, z)
  48     code = interleave_bits(((lon + 180.0) * 2**32 / 360.0).to_i,
  49                            ((lat +  90.0) * 2**32 / 180.0).to_i)
  50     str = ""
  51     # add eight to the zoom level, which approximates an accuracy of
  52     # one pixel in a tile.
  53     ((z + 8)/3.0).ceil.times do |i|
  54       digit = (code >> (58 - 6 * i)) & 0x3f
  55       str << ARRAY[digit]
  56     end
  57     # append characters onto the end of the string to represent
  58     # partial zoom levels (characters themselves have a granularity
  59     # of 3 zoom levels).
  60     ((z + 8) % 3).times { str << "=" }
  61
  62     return str
  63   end
  64
  65   private
  66
  67   ##
  68   # interleaves the bits of two 32-bit numbers. the result is known
  69   # as a Morton code.
  70   def self.interleave_bits(x, y)
  71     c = 0
  72     31.downto(0) do |i|
  73       c = (c << 1) | ((x >> i) & 1)
  74       c = (c << 1) | ((y >> i) & 1)
  75     end
  76     c
  77   end
  78
  79 end