2021-06-14

Rube: A Geo Hash

Earth's circumference is the distance around Earth. Measured around the Equator, it is 40,075.017 km (24,901.461 mi). Measured around the poles, the circumference is 40,007.863 km (24,859.734 mi). — Wikipedia

Post ref: Wikipedia — GeoHash

js
return 40075017 / Math.pow(2,25)
txtUpdated 54w ago
1.1943285763263702

The circumference c of the earth at the equator in meters, divided by two, twenty five times is roughly one point two meters s.

js
const c = 40075017
const s = 1.1943285763263702
const n = c / s
const dlon = 360 / n
return `${n} segments of ${dlon} degrees longitude`
txtUpdated 54w ago
33554432 segments of 0.000010728836059570312 degrees longitude

If for each division we stored "left" (0) or "right" (1) as a binary with 25 bits

Which if we always picked the "right" half of the split would give a maximum binary string like so:

js
return parseInt("111111111111111111111111", 2);
txtUpdated 54w ago
16777215

Coincidentally the max hex representation. is then:

js
return (16777215).toString(16)
txtUpdated 54w ago
ffffff
js
const mLon = 40075017
const mLat = 40007863
const x = 25
const n = Math.pow(2, x)
const dLon = 360 / n
const dLat = 180 / n

const binToInt = str => parseInt(str,2)
const intToHex = num => num.toString(16)

const normLat = lat => lat + 90
const normLon = lon => lon + 180

const geo2hash = (lat,lon) => {
  const bins = ['','']
  let [a,b] = [normLat(lat), normLon(lon)]
  console.log({normalised: [a,b]})
  let [minLatS,maxLatS,minLonS,maxLonS] = [0,180,0,360]
  for (var I=0;I<x;I++) {
    const latDiv = minLatS + (maxLatS-minLatS)/2
    const lonDiv = minLonS + (maxLonS-minLonS)/2
    //console.log({I, d: [minLatS,maxLatS,minLonS,maxLonS], divs:[latDiv,lonDiv]})
    if (a < latDiv){
      maxLatS = latDiv
      bins[0] += "0"
    } else {
      minLatS = latDiv
      bins[0] += "1"
    }
    if (b < lonDiv){
      maxLonS = lonDiv
      bins[1] += "0"
    } else {
      minLonS = lonDiv
      bins[1] += "1"
    }
    //console.log(bins)
  }
  const ints = bins.map( bin => binToInt(bin))
  const hexs = ints.map( i => intToHex(i))
  console.log({lat,lon,dLon,dLat,n,x,ints,hexs, bins})
  return hexs.join('x')
}
const hash = geo2hash(30,30)
return {hash}
txtUpdated 54.0w ago
{ normalised: [ 120, 210 ] }
{ lat: 30,
  lon: 30,
  dLon: 0.000010728836059570312,
  dLat: 0.000005364418029785156,
  n: 33554432,
  x: 25,
  ints: [ 22369621, 19573418 ],
  hexs: [ '1555555', '12aaaaa' ],
  bins: [ '1010101010101010101010101', '1001010101010101010101010' ] }
{ hash: '1555555x12aaaaa' }
js
const mLon = 40075017
const mLat = 40007863
const x = 25
const n = Math.pow(2, x)
const dLon = 360 / n
const dLat = 180 / n
const blank = Array(x).fill("0").join('')

const hash2geo = (hash, x = 25) => {
  const hexs = hash.split('x')
  const ints = hexs.map(h => parseInt(h,16))
  const bins = ints.map( i => i.toString(2)).map(b => blank.slice(0, 0-b.length) + b)
  
  let [minLat,maxLat] = [0, 180]
  let [minLon,maxLon] = [0, 360]
  
  for (var I=0;I<x;I++) {
    const a = parseInt(bins[0][I])
    const b = parseInt(bins[1][I])
    const latDiv = minLat + (maxLat-minLat)/2
  const lonDiv = minLon + (maxLon-minLon)/2
    //console.log({I,a,b,d: [minLat,maxLat,minLon,maxLon]})
    if (a) {
       minLat = latDiv
    } else {
       maxLat = latDiv
    }
    if (b) {
       minLon = lonDiv
    } else {
       maxLon = lonDiv
    }
  }
  // console.log({d: [minLat,maxLat,minLon,maxLon]})
  // console.log(minLat-90, maxLat-90, minLon-180,maxLon-180)
  minLat = minLat - 90
  maxLat = maxLat - 90
  minLon = minLon - 180
  maxLon = maxLon - 180
  
  return {x, hash, ints, hexs, bins, minLat, maxLat, minLon, maxLon}
}
return [
   "To within a meter (25 divisions)",hash2geo("1555555x12aaaaa"), 
   "Only 5 divisions (tbd precision)",hash2geo("1555555x12aaaaa", 5)
]
txtUpdated 54.0w ago
[ 'To within a meter (25 divisions)',
  { x: 25,
    hash: '1555555x12aaaaa',
    ints: [ 22369621, 19573418 ],
    hexs: [ '1555555', '12aaaaa' ],
    bins: [ '1010101010101010101010101', '1001010101010101010101010' ],
    minLat: 29.999998211860657,
    maxLat: 30.000003576278687,
    minLon: 29.999992847442627,
    maxLon: 30.000003576278687 },
  'Only 5 divisions (tbd precision)',
  { x: 5,
    hash: '1555555x12aaaaa',
    ints: [ 22369621, 19573418 ],
    hexs: [ '1555555', '12aaaaa' ],
    bins: [ '1010101010101010101010101', '1001010101010101010101010' ],
    minLat: 28.125,
    maxLat: 33.75,
    minLon: 22.5,
    maxLon: 33.75 } ]
js
// what precision is 5 divisions (at the equator in longitude, in km)
return 40075017 / Math.pow(2,5) / 1000
txtUpdated 54.0w ago
1252.34428125

Ignore But, but, but... we get the same hash... is the above just a rubegoldberg machine!?

This was an intermediary implementation which naively converts to a hex hash and does not divide progressively as above.

js
const geo2hash = (lat,lon, x = 25) => {
  const n = Math.pow(2, x)
  const dLon = 360 / n
  const dLat = 180 / n
  const nLat = Math.floor((lat+90)/dLat)
  const nLon = Math.floor((lon+180)/dLon)
  const hash = `${nLat.toString(16)}x${nLon.toString(16)}`
  //console.log({hash,nLat,nLon})
  return hash
}
const hash2geo = (hash, x = 25) => {
  const n = Math.pow(2, x)
  const dLon = 360 / n
  const dLat = 180 / n
  const [hLat,hLon] = hash.split('x').map(x=>parseInt(x,16))
  const lat = (hLat * dLat) - 90
  const lon = (hLon * dLon) - 180
  return { lat: [lat, lat+dLat], lon: [lon,lon+dLon]}
}

const lat = 30
const lon = 30
const hash = geo2hash(lat,lon)
const geo25 = hash2geo(hash)
const hash5 = geo2hash(lat,lon,5)
const geo5 = hash2geo(hash5, 5)
return {lat,lon,hash,geo25,hash5,geo5}
txtUpdated 54.0w ago
{ lat: 30,
  lon: 30,
  hash: '1555555x12aaaaa',
  geo25: 
   { lat: [ 29.999998211860657, 30.000003576278687 ],
     lon: [ 29.999992847442627, 30.000003576278687 ] },
  hash5: '15x12',
  geo5: { lat: [ 28.125, 33.75 ], lon: [ 22.5, 33.75 ] } }

... so far, I'm thinking yes 😞

it's worth noting though that in its current form you would need to have gotten the hash at the desired precision before storing, as a hash25 cant be decoded to a geo5 (in its current state) ...

Also since it's based in degrees, bins will not be of uniform size... which is likely desired.