Geohash-16: how to

Question

Situation:

I have JavaScript code that creates geohash with base-32 system.

var BASE32_CODES = "0123456789bcdefghjkmnpqrstuvwxyz";
var BASE32_CODES_DICT = {};
for (var i = 0; i < BASE32_CODES.length; i++) {
  BASE32_CODES_DICT[BASE32_CODES.charAt(i)] = i;
}

var ENCODE_AUTO = 'auto';

var SIGFIG_HASH_LENGTH = [0, 5, 7, 8, 11, 12, 13, 15, 16, 17, 18];

var encode = function (latitude, longitude, numberOfChars) {
  if (numberOfChars === ENCODE_AUTO) {
    if (typeof(latitude) === 'number' || typeof(longitude) === 'number') {
      throw new Error('string notation required for auto precision.');
    }
    var decSigFigsLat = latitude.split('.')[1].length;
    var decSigFigsLong = longitude.split('.')[1].length;
    var numberOfSigFigs = Math.max(decSigFigsLat, decSigFigsLong);
    numberOfChars = SIGFIG_HASH_LENGTH[numberOfSigFigs];
  } else if (numberOfChars === undefined) {
    numberOfChars = 9;
  }

  var chars = [],
  bits = 0,
  bitsTotal = 0,
  hash_value = 0,
  maxLat = 90,
  minLat = -90,
  maxLon = 180,
  minLon = -180,
  mid;
  while (chars.length < numberOfChars) {
    if (bitsTotal % 2 === 0) {
      mid = (maxLon + minLon) / 2;
      if (longitude > mid) {
        hash_value = (hash_value << 1) + 1;
        minLon = mid;
      } else {
        hash_value = (hash_value << 1) + 0;
        maxLon = mid;
      }
    } else {
      mid = (maxLat + minLat) / 2;
      if (latitude > mid) {
        hash_value = (hash_value << 1) + 1;
        minLat = mid;
      } else {
        hash_value = (hash_value << 1) + 0;
        maxLat = mid;
      }
    }

    bits++;
    bitsTotal++;
    if (bits === 5) {
      var code = BASE32_CODES[hash_value];
      chars.push(code);
      bits = 0;
      hash_value = 0;
    }
  }
  return chars.join('');
};

Actually, I took it from ngeohash npm module (source code).

Problem:

I'm not good at numeral systems binary data, etc. I don't know how to change encoding to the base-16 system ('0123456789abcdef'). I'll be happy if someone changes it or just points me what do I need to change. Thanks.

Answer 1

So I think you'll only have to change three things:

• The alphabet definition (BASE32_CODES in your snippet), to have the base 16 character set instead.
• The number of bits to collect before writing a character (use 4 instead of 5)
• The number of total characters to output (since each character carries less info, you'll need more of them to carry the same data).

Since we're moving from 5 -> 4 bits per char, we would need additional characters to reach the same precision (5bits/char * 9chars = 45bits, so we need at least 12 characters in base 16 for the same precision (4bits/char * 12chars = 48bits, so we actually get some extra precision with that character count)

So your snippet would become:

var BASE16_CODES = "0123456789abcdef"; // <-- changed this
var BASE16_CODES_DICT = {};
for (var i = 0; i < BASE16_CODES.length; i++) {
  BASE16_CODES_DICT[BASE16_CODES.charAt(i)] = i;
}

var ENCODE_AUTO = 'auto';

var SIGFIG_HASH_LENGTH = [0, 5, 7, 8, 11, 12, 13, 15, 16, 17, 18];

var encode = function (latitude, longitude, numberOfChars) {
  if (numberOfChars === ENCODE_AUTO) {
    if (typeof(latitude) === 'number' || typeof(longitude) === 'number') {
      throw new Error('string notation required for auto precision.');
    }
    var decSigFigsLat = latitude.split('.')[1].length;
    var decSigFigsLong = longitude.split('.')[1].length;
    var numberOfSigFigs = Math.max(decSigFigsLat, decSigFigsLong);
    numberOfChars = SIGFIG_HASH_LENGTH[numberOfSigFigs];
  } else if (numberOfChars === undefined) {
    numberOfChars = 12; // <-- and this
  }

  var chars = [],
  bits = 0,
  bitsTotal = 0,
  hash_value = 0,
  maxLat = 90,
  minLat = -90,
  maxLon = 180,
  minLon = -180,
  mid;
  while (chars.length < numberOfChars) {
    if (bitsTotal % 2 === 0) {
      mid = (maxLon + minLon) / 2;
      if (longitude > mid) {
        hash_value = (hash_value << 1) + 1;
        minLon = mid;
      } else {
        hash_value = (hash_value << 1) + 0;
        maxLon = mid;
      }
    } else {
      mid = (maxLat + minLat) / 2;
      if (latitude > mid) {
        hash_value = (hash_value << 1) + 1;
        minLat = mid;
      } else {
        hash_value = (hash_value << 1) + 0;
        maxLat = mid;
      }
    }

    bits++;
    bitsTotal++;
    if (bits === 4) { // <-- and finally this
      var code = BASE16_CODES[hash_value];
      chars.push(code);
      bits = 0;
      hash_value = 0;
    }
  }
  return chars.join('');
};

console.log(encode(...[40.676843, -73.935769]))

EDIT: Come to think of it, if you're using the ENCODE_AUTO feature that this function has, you'll need to increase the values in the SIGFIG_HASH_LENGTH array as well (for the same reason as before, more chars are needed for the same or greater precision). So it should end up as:

var SIGFIG_HASH_LENGTH = [0, 7, 9, 10, 14, 15, 17, 19, 20, 22, 23]