hilbert-curves2

How to convert between Hilbert Curve QuadTree and S2 Geometry CellId

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.

Solution

  • 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

    position encoding

    level encoding