How to convert between Hilbert Curve QuadTree and S2 Geometry CellId

Question

Problem

Let's say I know the Hilbert Curve Face and Quadtree, such as 4/032212303102122 (face 4, level 15).

Or perhaps I know the S2 Geometry CellId, such as 9749618424903892992.

How can I convert from the one to the other?

Application

(this is the kind of thing you need to do for Pokemon GO and Ingress maps)

Exploration

I'm trying to do this in JavaScript and a library exists for manipulating 64-bit integers (long.js) as well as for S2CellIds (s2-geometry.js).

Also, I'm feeling pretty good about walking the hilbert curve simply by adding or subtracting the base four numbers (except when crossing faces, but that happens rarely enough that I'll be fine... for a while...), just not sure how to go back and forth with the 64-bit id.

Answer 1

It turns out that it's much, much, much easier to do it with strings than with binary - and since this is JavaScript where bitshifting with the long.js would take significantly more time, it's actually faster!

Code Example:

From s2-geometry-javascript:

'use strict';

var Long = require('long');
var S2 = {};

S2.FACE_BITS = 3;
S2.MAX_LEVEL = 30;
S2.POS_BITS = (2 * S2.MAX_LEVEL) + 1;

S2.fromFacePosLevel = function (faceN, posS, levelN) {
  var Long = exports.dcodeIO && exports.dcodeIO.Long || require('long');

  if (!levelN) {
    levelN = posS.length;
  }
  if (posS.length > levelN) {
    posS = posS.substr(0, levelN);
  }

  var posB = Long.fromString(posS, true, 4).toString(2);
  while (posB.length < (2 * levelN)) {
    posB = '0' + posB;
  }
  var bin = Long.fromString(faceN.toString(10), true, 10).toString(2);
  while (bin.length < S2.FACE_BITS) {
    bin = '0' + bin;
  }
  bin += posB;
  bin += '1';
  while (bin.length < (S2.FACE_BITS + S2.POS_BITS)) {
    bin += '0';
  }

  return Long.fromString(bin, true, 2).toString(10);
};

Explanation:

Here's a quick 'n' dirty breakdown of the bits

id encoding

Note that + means concat and NOT add

(padding + face bits) + (padding + position bits) + (lsb marker + padding)

// quadkey       4/032212303102210
// id (base 10)  9749618446378729472
// base 4        10    032212303102210                   1000000000000000
// base 2       100    001110100110110011010010100100    1000000000000000000000000000000

face encoding

• "human readable" form is base 10
• 3-bit - i.e. an unfolded 6-sided cube with base 10 face representations of 0,1,2,3,4,5
• 6 and 7 are unused and invalid
• 3 binary characters - i.e. 000, 001, 010, 011, 100, 101
• 110 and 111 are unused and invalid
• left-padded to 3-bits with '0's (i.e. 001)

position encoding

• "human readable" form is base 4 (quadkey)
• 61-bit
• 60 data bits, 1 bit for lsb marker
• left-padded to LEVEL with '0's (i.e. 00322130 for level 8)

level encoding

• "human readable" form is base 10
• the length of hilbert curve quadkey / quadtree string is the level
• calculated from the least significant bit in binary form
• lsb (least-significant bit) marker is '1', just to right of position
• right-padded to MAX_LEVEL*2 (after lsb marker) with a leading '0's
  • (i.e. '1' for level 30, '1000' for level 27)