source: subversion/sites/rails_port/lib/short_link.rb @ 17044

Last change on this file since 17044 was 16271, checked in by zere, 10 years ago

Changed shortlink zoom level correction char to '-', as this seems to fare better with twitter et al.'s URL highlighting. Decoder is backwards-compatible with the old system.

File size: 2.2 KB
Line 
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".
7module 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
79end
Note: See TracBrowser for help on using the repository browser.