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