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   # array of 64 chars to encode 6 bits. this is almost like base64 encoding, but
   9   # the symbolic chars are different, as base64's + and / aren't very
  10   # URL-friendly.
  11   ARRAY = ("A".."Z").to_a + ("a".."z").to_a + ("0".."9").to_a + ["_", "~"]
  12
  13   ##
  14   # Given a string encoding a location, returns the [lon, lat, z] tuple of that
  15   # location.
  16   def self.decode(str)
  17     x = 0
  18     y = 0
  19     z = 0
  20     z_offset = 0
  21
  22     # keep support for old shortlinks which use the @ character, now
  23     # replaced by the ~ character because twitter is horribly broken
  24     # and we can't have that.
  25     str.gsub!("@", "~")
  26
  27     str.each_char do |c|
  28       t = ARRAY.index c
  29       if t.nil?
  30         z_offset -= 1
  31       else
  32         3.times do
  33           x <<= 1
  34           x |= 1 unless (t & 32).zero?
  35           t <<= 1
  36
  37           y <<= 1
  38           y |= 1 unless (t & 32).zero?
  39           t <<= 1
  40         end
  41         z += 3
  42       end
  43     end
  44     # pack the coordinates out to their original 32 bits.
  45     x <<= (32 - z)
  46     y <<= (32 - z)
  47
  48     # project the parameters back to their coordinate ranges.
  49     [(x * 360.0 / 2**32) - 180.0,
  50      (y * 180.0 / 2**32) - 90.0,
  51      z - 8 - (z_offset % 3)]
  52   end
  53
  54   ##
  55   # given a location and zoom, return a short string representing it.
  56   def self.encode(lon, lat, z)
  57     code = interleave_bits(((lon + 180.0) * 2**32 / 360.0).to_i,
  58                            ((lat +  90.0) * 2**32 / 180.0).to_i)
  59     str = ""
  60     # add eight to the zoom level, which approximates an accuracy of
  61     # one pixel in a tile.
  62     ((z + 8) / 3.0).ceil.times do |i|
  63       digit = (code >> (58 - 6 * i)) & 0x3f
  64       str << ARRAY[digit]
  65     end
  66     # append characters onto the end of the string to represent
  67     # partial zoom levels (characters themselves have a granularity
  68     # of 3 zoom levels).
  69     ((z + 8) % 3).times { str << "-" }
  70
  71     str
  72   end
  73
  74   private
  75
  76   ##
  77   # interleaves the bits of two 32-bit numbers. the result is known
  78   # as a Morton code.
  79   def self.interleave_bits(x, y)
  80     c = 0
  81     31.downto(0) do |i|
  82       c = (c << 1) | ((x >> i) & 1)
  83       c = (c << 1) | ((y >> i) & 1)
  84     end
  85     c
  86   end
  87 end