Geohash

From Rosetta Code
Geohash is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Geohashes are used to represent standard latitude and longitude coordinates as single values in the form of a simple string -- using the digits (0-9) and the letters (B-Z excluding I, L, O). They can vary in length, with more characters in the string representing more precision.


Task

Generate a Geohash with a desired precision from a coordinate represented as an array of two floating point numbers, latitude and longitude. (Ideally double precision).


Example 1:
print (encodeGeohash (for: [51.433718, -0.214126], withPrecision: 2))
// Result: "gc" (all of Ireland, most of England and Wales, small part of Scotland)
Example 2:
print (encodeGeohash (for: [51.433718, -0.214126], withPrecision: 9))
// Result: "gcpue5hp4" (the umpire's chair on Center Court at Wimbledon)


From the Wikipedia page, geohashes can be "useful in database systems where queries on a single index are much easier or faster than multiple-index queries."


Extra credit

Provide a decode function to convert a geohash code back to latitude and longitude, expressed either as ranges or in median +/- deviation format.


Reference


11l

Translation of: Python
V ch32 = Array(‘0123456789bcdefghjkmnpqrstuvwxyz’)
V bool2ch = Dict(enumerate(ch32), (i, ch) -> (bin(i).zfill(5), ch))
V ch2bool = Dict(bool2ch.items(), (k, v) -> (v, k))

F bisect(val, =mn, =mx, =bits)
   V mid = (mn + mx) / 2
   I val < mid
      bits <<= 1
      mx = mid
   E
      bits = bits << 1 [|] 1
      mn = mid

   R (mn, mx, bits)

F encoder(lat, lng, pre)
   V (latmin, latmax) = (-90.0, 90.0)
   V (lngmin, lngmax) = (-180.0, 180.0)
   V bits = Int64(0)
   L(i) 0 .< pre * 5
      I i % 2 != 0
         (latmin, latmax, bits) = bisect(lat, latmin, latmax, bits)
      E
         (lngmin, lngmax, bits) = bisect(lng, lngmin, lngmax, bits)

   V b = bin(bits).zfill(pre * 5)
   V geo = ((0 .< pre).map(i -> :bool2ch[@b[i * 5 .< (i + 1) * 5]]))

   R geo.join(‘’)

F decoder(geo)
   V (minmaxes, latlong) = ([[-90.0, 90.0], [-180.0, 180.0]], 1B)
   L(c) geo
      L(bit) :ch2bool[c]
         minmaxes[latlong][bit != ‘1’] = sum(minmaxes[latlong]) / 2
         latlong = !latlong
   R minmaxes

L(lat, lng, pre) [(51.433718, -0.214126,  2),
                  (51.433718, -0.214126,  9),
                  (57.64911,   10.40744, 11)]
   print(‘encoder(lat=#.6, lng=#.6, pre=#.) = '#.'’.format(lat, lng, pre, encoder(lat, lng, pre)))
Output:
encoder(lat=51.433718, lng=-0.214126, pre=2) = 'gc'
encoder(lat=51.433718, lng=-0.214126, pre=9) = 'gcpue5hp4'
encoder(lat=57.649110, lng=10.407440, pre=11) = 'u4pruydqqvj'

Action!

INCLUDE "H6:REALMATH.ACT"

CHAR ARRAY code32="0123456789bcdefghjkmnpqrstuvwxyz"

PROC Encode(REAL POINTER lat,lng BYTE prec CHAR ARRAY hash)
  REAL latMin,latMax,lngMin,lngMax,mid,r2,sum
  REAL POINTER v,min,max
  BYTE even,hashV,bits
  
  IntToReal(2,r2)
  ValR("-90",latMin) ValR("90",latMax)
  ValR("-180",lngMin) ValR("180",lngMax)
  
  hash(0)=0 hashV=0 even=1 bits=0
  WHILE hash(0)<prec
  DO
    IF even THEN
      v=lng min=lngMin max=lngMax
    ELSE
      v=lat min=latMin max=latMax
    FI
    RealAdd(min,max,sum)
    RealDiv(sum,r2,mid)
    hashV==LSH 1
    IF RealGreaterOrEqual(v,mid) THEN
      hashV==+1
      RealAssign(mid,min)
    ELSE
      RealAssign(mid,max)
    FI

    even=1-even
    IF bits<4 THEN
      bits==+1
    ELSE
      bits=0
      hash(0)==+1
      hash(hash(0))=code32(hashV+1)
      hashV=0
    FI
  OD
RETURN

BYTE FUNC GetCodeVal(CHAR c)
  BYTE i

  FOR i=1 TO code32(0)
  DO
    IF c=code32(i) THEN
      RETURN (i-1)
    FI
  OD
RETURN (0)

PROC Decode(CHAR ARRAY hash REAL POINTER lat,lng,latPrec,lngPrec)
  REAL latMin,latMax,lngMin,lngMax,r2,sum
  REAL POINTER min,max
  BYTE i,j,v,mask,even

  IntToReal(2,r2)
  ValR("-90",latMin) ValR("90",latMax)
  ValR("-180",lngMin) ValR("180",lngMax)

  even=1
  FOR i=1 TO hash(0)
  DO
    v=GetCodeVal(hash(i))
    mask=16
    FOR j=1 TO 5
    DO
      IF even THEN
        min=lngMin
        max=lngMax
      ELSE
        min=latMin
        max=latMax
      FI
      RealAdd(min,max,sum)
      IF (v&mask)=mask THEN
        RealDiv(sum,r2,min)
      ELSE
        RealDiv(sum,r2,max)
      FI
      even=1-even
      mask==RSH 1
    OD
  OD

  RealAdd(latMin,latMax,sum)
  RealDiv(sum,r2,lat)
  RealSub(latMax,lat,latPrec)
  RealAdd(lngMin,lngMax,sum)
  RealDiv(sum,r2,lng)
  RealSub(lngMax,lng,lngPrec)
RETURN

PROC Test(CHAR ARRAY latStr,lngStr BYTE prec)
  CHAR ARRAY hash(255)
  REAL lat,lng,resLat,resLng,latPrec,lngPrec

  ValR(latStr,lat) ValR(lngStr,lng)
  Encode(lat,lng,prec,hash)
  Decode(hash,resLat,resLng,latPrec,lngPrec)

  Print("Input:  ") PrintR(lat) Print(", ")
  PrintR(lng) PrintF(", prec=%B%E",prec)
  
  PrintF("Encode: %S%E",hash)
  
  Print("Decode: ") PrintR(resLat) Print(" (+/-") PrintR(latPrec)
  Print("), ") PrintR(resLng) Print(" (+/-") PrintR(lngPrec)
  PrintE(")") PutE()
RETURN

PROC Main()
  Put(125) PutE() ;clear the screen
  Test("51.433718","-0.214126",2)
  Test("51.433718","-0.214126",9)
  Test("57.64911","10.40744",11)
RETURN
Output:

Screenshot from Atari 8-bit computer

Input:  51.433718, -0.214126, prec=2
Encode: gc
Decode: 53.4375 (+/-2.8125), -5.625 (+/-5.625)

Input:  51.433718, -0.214126, prec=9
Encode: gcpue5hp4
Decode: 51.433717 (+/-2.15E-05), -0.21412611 (+/-2.14577E-05)

Input:  57.64911, 10.40744, prec=11
Encode: u4pruydqqvm
Decode: 57.64911 (+/-1E-06), 10.40743967 (+/-6.7E-07)

Factor

Factor comes with the geohash vocabulary. See the implementation here.

Works with: Factor version 0.99 2020-03-02
USING: formatting generalizations geohash io kernel sequences ;

: encode-geohash ( latitude longitude precision -- str )
    [ >geohash ] [ head ] bi* ;

! Encoding
51.433718 -0.214126 2
51.433718 -0.214126 9
57.649110 10.407440 11
[
    3dup encode-geohash
    "geohash for [%f, %f], precision %2d = %s\n" printf
] 3 3 mnapply nl

! Decoding
"u4pruydqqvj" dup geohash>
"coordinates for %s ~= [%f, %f]\n" printf
Output:
geohash for [51.433718, -0.214126], precision  2 = gc
geohash for [51.433718, -0.214126], precision  9 = gcpue5hp4
geohash for [57.649110, 10.407440], precision 11 = u4pruydqqvj

coordinates for u4pruydqqvj ~= [57.649110, 10.407439]

F#

// Create a geoHash String. Nigel Galloway: June 26th., 2020
let fG n g=Seq.unfold(fun(α,β)->let τ=(α+β)/2.0 in Some(if τ>g then (0,(α,τ)) else (1,(τ,b)))) n
let fLat, fLon = fG (-90.0,90.0), fG (-180.0,180.0)
let fN n g z=Seq.zip(fLat n)(fLon g)|>Seq.collect(fun(n,g)->seq{yield g;yield n})|>Seq.take(z*5)|>Seq.splitInto z
let fI=Array.fold2 (fun Σ α β->Σ+α*β) 0  [|16; 8; 4; 2; 1|]
let geoHash n g z=let N="0123456789bcdefghjkmnpqrstuvwxyz" in [|for τ in fN n g z do  yield N.[fI τ]|] |> System.String
printfn "%s\n%s\n%s" (geoHash 51.433718 -0.214126 2) (geoHash 51.433718 -0.214126 9) (geoHash 57.64911 10.40744 11)
Output:
gc
gcpue5hp4
u4pruydqqvj

Go

Translation of: Swift
package main

import (
    "fmt"
    "strings"
)

type Location struct{ lat, lng float64 }

func (loc Location) String() string { return fmt.Sprintf("[%f, %f]", loc.lat, loc.lng) }

type Range struct{ lower, upper float64 }

var gBase32 = "0123456789bcdefghjkmnpqrstuvwxyz"

func encodeGeohash(loc Location, prec int) string {
    latRange := Range{-90, 90}
    lngRange := Range{-180, 180}
    var hash strings.Builder
    hashVal := 0
    bits := 0
    even := true
    for hash.Len() < prec {
        val := loc.lat
        rng := latRange
        if even {
            val = loc.lng
            rng = lngRange
        }
        mid := (rng.lower + rng.upper) / 2
        if val > mid {
            hashVal = (hashVal << 1) + 1
            rng = Range{mid, rng.upper}
            if even {
                lngRange = Range{mid, lngRange.upper}
            } else {
                latRange = Range{mid, latRange.upper}
            }
        } else {
            hashVal <<= 1
            if even {
                lngRange = Range{lngRange.lower, mid}
            } else {
                latRange = Range{latRange.lower, mid}
            }
        }
        even = !even
        if bits < 4 {
            bits++
        } else {
            bits = 0
            hash.WriteByte(gBase32[hashVal])
            hashVal = 0
        }
    }
    return hash.String()
}

func main() {
    locs := []Location{
        {51.433718, -0.214126},
        {51.433718, -0.214126},
        {57.64911, 10.40744},
    }
    precs := []int{2, 9, 11}

    for i, loc := range locs {
        geohash := encodeGeohash(loc, precs[i])
        fmt.Printf("geohash for %v, precision %-2d = %s\n", loc, precs[i], geohash)
    }
}
Output:
geohash for [51.433718, -0.214126], precision 2  = gc
geohash for [51.433718, -0.214126], precision 9  = gcpue5hp4
geohash for [57.649110, 10.407440], precision 11 = u4pruydqqvj

J

gdigits=: '0123456789bcdefghjkmnpqrstuvwxyz'

geohash=: {{
  bits=. 3*x
  x{.gdigits{~_5 #.\,|:|.(bits#2)#:<.(2^bits)*(y+90 180)%180 360
}}

Note that the test cases suggest that rounding should never be used when generating a geohash. This guarantees that a short geohash is always a prefix of a longer geohash for the same location.

   2 geohash 51.433718 _0.214126
gc
   9 geohash 51.433718 _0.214126
gcpue5hp4
   11 geohash 57.64911 10.40744
u4pruydqqvj

And, going the other direction (producing a min and max lat and long value for the geohash):

hsahoeg=: {{
   bits=: |.|:0,~_2]\,(5#2)#:gdigits i.y
   scale=: %2^{:$bits
   lo=: scale*#.bits
   hi=: scale*(2^1+1 0*2|#y)+#.bits
   0.5*_180+360*lo,.hi
}}

This gives us:

   hsahoeg 'gc'
50.625 56.25
_5.625     0
   hsahoeg 'gcpue5hp4'
  51.4337   51.4337
_0.107074 _0.107052
   hsahoeg 'u4pruydqqvj'
57.6491 57.6491
5.20372 5.20372

Or

   9!:11]10  NB. display 10 digits of floating point precision

   hsahoeg 'gcpue5hp4'
  51.43369675   51.43373966
_0.1070737839 _0.1070523262
   hsahoeg 'u4pruydqqvj'
57.64910996  57.6491113
5.203719512 5.203720182

jq

Adapted from Wren and Python

Works with: jq

Also works with gojq, the Go implementation of jq, and with fq. Generic Utilities

def lpad($len; $c): tostring | ($len - length) as $l | ($c * $l)[:$l] + .;

def lpad($len): lpad($len; " ");

def round($digits): pow(10; $digits) as $p | . * $p | round | floor | . / $p;

# Convert the input integer to a string in the specified base (2 to 36 inclusive)
def convert(base):
  def stream:
    recurse(if . >= base then ./base|floor else empty end) | . % base ;
  [stream] | reverse
  | if   base <  10 then map(tostring) | join("")
    elif base <= 36 then map(if . < 10 then 48 + . else . + 87 end) | implode
    else error("base too large")
    end;

# counting from 0
def enumerate(s): foreach s as $x (-1; .+1; [., $x]);

def to_object(s; o):
  reduce s as $x ({}; . + ($x|o));

GeoHash

def gBase32: "0123456789bcdefghjkmnpqrstuvwxyz";

# Output: the dictionary mapping the characters in gBase32 to bitstrings:
# {"0":"00000", ... "z":"11111"}
def gBase32dict:  
  to_object( enumerate(gBase32|explode[]|[.]|implode);
             { (.[1]): (.[0]|convert(2)|lpad(5; "0")) } ) ;

def encodeGeohash($location; $prec):
  { latRange: [ -90,  90],
    lngRange: [-180, 180],
    hash: "",
    hashVal: 0,
    bits: 0,
    even: true
  }
  | until (.hash|length >= $prec;
          .val = if .even then $location[1] else $location[0] end
        | .rng = if .even then .lngRange else .latRange end
        | .mid = (.rng[0] + .rng[1]) / 2
        | if .val > .mid
          then .hashVal |= .*2 + 1
          | .rng = [.mid, .rng[1]]
          | if .even then .lngRange = [.mid, .lngRange[1]] else .latRange = [.mid, .latRange[1]] end
          else .hashVal *= 2
          | if .even then .lngRange = [.lngRange[0], .mid] else .latRange = [.latRange[0], .mid] end
          end
        | .even |= not
        | if .bits < 4 then .bits += 1
          else 
            .bits = 0
            | .hash += gBase32[.hashVal:.hashVal+1]
            | .hashVal = 0
	  end)
  | .hash;

def decodeGeohash:
  def flip: if . == 0 then 1 else 0 end;
  def chars: explode[] | [.] | implode;
  # input: a 0/1 string
  # output: a stream of 0/1 integers
  def bits: explode[] | . - 48;

  . as $geo
  | gBase32dict as $gBase32dict
  | {minmaxes: [[-90.0, 90.0], [-180.0, 180.0]], latlong: 1 }
  | reduce ($geo | chars) as $c (.;
      reduce ($gBase32dict[$c]|bits) as $bit (.;
        .minmaxes[.latlong][$bit|flip] = ((.minmaxes[.latlong] | add) / 2)
        | .latlong |= flip))
  | .minmaxes ;

def data:
    [[51.433718, -0.214126],  2],
    [[51.433718, -0.214126],  9],
    [[57.64911,  10.40744 ], 11]
;

data
| encodeGeohash(.[0]; .[1]) as $geohash
| (.[0] | map(lpad(10)) | join(",") | "[\(.)]" ) as $loc
| "geohash for \($loc), precision \(.[1]|lpad(3)) = \($geohash)",
  "  decode => \($geohash|decodeGeohash|map(map(round(6))) )"
Output:
geohash for [ 51.433718, -0.214126], precision   2 = gc
  decode => [[50.625,56.25],[-11.25,0]]
geohash for [ 51.433718, -0.214126], precision   9 = gcpue5hp4
  decode => [[51.433697,51.43374],[-0.214148,-0.214105]]
geohash for [  57.64911,  10.40744], precision  11 = u4pruydqqvj
  decode => [[57.64911,57.649111],[10.407439,10.40744]]

Julia

Translation of: Python
const ch32 = "0123456789bcdefghjkmnpqrstuvwxyz"
const bool2ch = Dict(string(i-1, base=2, pad=5) => ch for (i, ch) in enumerate(ch32))
const ch2bool = Dict(v => k for (k, v) in bool2ch)

function bisect(val, mn, mx, bits)
    mid = (mn + mx) / 2
    if val < mid
        bits <<= 1                        # push 0
        mx = mid                          # range lower half
    else
        bits = (bits << 1) | 1            # push 1
        mn = mid                          # range upper half
    end
    return mn, mx, bits
end

function encoder(lat, lng, pre)
    latmin, latmax = -90, 90
    lngmin, lngmax = -180, 180
    bits = Int128(0)
    for i in 0:5*pre-1
        if i % 2 != 0
            # odd bit: bisect latitude
            latmin, latmax, bits = bisect(lat, latmin, latmax, bits)
        else
            # even bit: bisect longitude
            lngmin, lngmax, bits = bisect(lng, lngmin, lngmax, bits)
        end
    end
    # Bits to characters
    b = string(bits, base=2, pad=5*pre)
    geo = [bool2ch[b[i*5+1:i*5+5]] for i in 0:pre-1]
    return prod(geo)
end

function decoder(geo)
    minmaxes, latlong = [[-90.0, 90.0], [-180.0, 180.0]], 2
    for c in geo, bit in ch2bool[c]
        minmaxes[latlong][bit == '1' ? 1 : 2] = sum(minmaxes[latlong]) / 2
        latlong = 3 - latlong
    end
    return minmaxes
end

for ((lat, lng), pre) in [([51.433718, -0.214126],  2),
                          ([51.433718, -0.214126],  9),
                          ([57.64911,  10.40744] , 11),
                          ([57.64911,  10.40744] , 22)]
    encoded = encoder(lat, lng, pre)
    println("encoder(lat=$lat, lng=$lng, pre=$pre) = ", encoded)
    println("decoded = ", decoder(encoded))
end
Output:
encoder(lat=51.433718, lng=-0.214126, pre=2) = gc
decoded = [[50.625, 56.25], [-11.25, 0.0]]
encoder(lat=51.433718, lng=-0.214126, pre=9) = gcpue5hp4
decoded = [[51.43369674682617, 51.43373966217041], [-0.21414756774902344, -0.21410465240478516]]
encoder(lat=57.64911, lng=10.40744, pre=11) = u4pruydqqvj
decoded = [[57.649109959602356, 57.64911130070686], [10.407439023256302, 10.40744036436081]]
encoder(lat=57.64911, lng=10.40744, pre=22) = u4pruydqqvj8pr9yc27rjr
decoded = [[57.64911, 57.64911000000001], [10.407439999999998, 10.407440000000008]]

Nim

Translation of: Python
Translation of: Julia

We omitted the test with precision 22 as it exceeds the capacity of a 64 bits integer.

import math, strformat, strutils, sugar, tables

const
  Ch32 = "0123456789bcdefghjkmnpqrstuvwxyz"
  Bool2Ch = collect(initTable, for i, ch in Ch32: {i.toBin(5): ch})
  Ch2Bool = collect(initTable, for k, v in Bool2Ch: {v: k})


func bisect(val, mn, mx: float; bits: int64): (float, float, int64) =
  var
    bits = bits
    mn = mn
    mx = mx
  let mid = (mn + mx) * 0.5
  if val < mid:
    bits = bits shl 1       # push 0.
    mx = mid                # range lower half.
  else:
    bits = bits shl 1 or 1  # push 1.
    mn = mid                # range upper half.
  result = (mn, mx, bits)


func encode(lat, long: float; pre: int64): string =
  var
    (latmin, latmax) = (-90.0, 90.0)
    (longmin, longmax) = (-180.0, 180.0)
    bits = 0i64

  for i in 0..<(5 * pre):
    if (i and 1) != 0:
      # Odd bit: bisect latitude.
      (latmin, latmax, bits) = bisect(lat, latmin, latmax, bits)
    else:
      # Even bit: bisect longitude.
      (longmin, longmax, bits) = bisect(long, longmin, longmax, bits)
    # Bits to characters.
    let b = bits.toBin(pre * 5)
    let geo = collect(newSeq, for i in 0..<pre: Bool2Ch[b[i*5..i*5+4]])
    result = geo.join()


func decode(geo: string): array[2, array[2, float]] =
  var latlong = 1
  result = [[-90.0, 90.0], [-180.0, 180.0]]
  for c in geo:
    for bit in Ch2Bool[c]:
      result[latlong][ord(bit != '1')] = sum(result[latlong]) * 0.5
      latlong = 1 - latlong


when isMainModule:
  for (lat, long, pre) in [(51.433718, -0.214126,  2),
                           (51.433718, -0.214126,  9),
                           (57.64911,  10.40744 , 11)]:
    let encoded = encode(lat, long, pre)
    echo &"encoder(lat = {lat}, long = {long}, pre = {pre}) = {encoded}"
    echo &"decoded = {decode(encoded)}
Output:
encoder(lat = 51.433718, long = -0.214126, pre = 2) = gc
decoded = [[50.625, 56.25], [-11.25, 0.0]]
encoder(lat = 51.433718, long = -0.214126, pre = 9) = gcpue5hp4
decoded = [[51.43369674682617, 51.43373966217041], [-0.2141475677490234, -0.2141046524047852]]
encoder(lat = 57.64911, long = 10.40744, pre = 11) = u4pruydqqvj
decoded = [[57.64910995960236, 57.64911130070686], [10.4074390232563, 10.40744036436081]]

Perl

Translation of: Raku
use strict;
use warnings;
use feature 'say';
use List::AllUtils qw<sum max natatime>;

my @Geo32 = <0 1 2 3 4 5 6 7 8 9 b c d e f g h j k m n p q r s t u v w x y z>;

sub geo_encode {
    my( $latitude, $longitude, $precision ) = @_;
    my @coord = ($latitude, $longitude);
    my @range = ([-90, 90], [-180, 180]);
    my($which,$value) = (1, '');
    while (length($value) < $precision * 5) {
        my $mid = sum(@{$range[$which]}) / 2;
        $value .= my $upper = $coord[$which] <= $mid ? 0 : 1;
        $range[$which][$upper ? 0 : 1] = $mid;
        $which = $which ? 0 : 1;
    }
    my $enc;
    my $iterator = natatime 5, split '', $value;
    while (my @n = $iterator->()) {
        $enc .= $Geo32[ord pack 'B8', '000' . join '', @n]; # binary to decimal, very specific to the task
    }
    $enc
}

sub geo_decode {
    my($geo) = @_;
     my @range = ([-90, 90], [-180, 180]);
     my(%Geo32,$c); $Geo32{$_} = $c++ for @Geo32;
     my $which = 1;
     for ( split '', join '', map { sprintf '%05b', $_ } @Geo32{split '', $geo} ) {
        $range[$which][$_] = sum(@{$range[$which]}) / 2;
        $which = $which ? 0 : 1;
     }
     @range
}

for ([51.433718,   -0.214126,  2, 'Ireland, most of England and Wales, small part of Scotland'],
     [51.433718,   -0.214126,  9, "the umpire's chair on Center Court at Wimbledon"],
     [51.433718,   -0.214126, 17, 'likely an individual molecule of the chair'],
     [57.649110,   10.407440, 11, 'Wikipedia test value - Råbjerg Mile in Denmark'],
     [59.115800, -151.687312,  7, 'Perl Island, Alaska'],
     [38.743586, -109.499336,  8, 'Delicate Arch, Utah'],
    ) {
    my($lat, $long, $precision, $description) = @$_;
    my $enc = geo_encode($lat, $long, $precision);
    say "\n$lat, $long, $precision ($description):" .
        "\ngeo-encoded: $enc\n" .
        'geo-decoded: ' . join ',  ',
        map {         sprintf("%.@{[max(3,$precision-3)]}f", (  -($$_[0] + $$_[1]) / 2)) .
              ' ± ' . sprintf('%.3e',                        (abs($$_[0] - $$_[1]) / 2))
            } geo_decode($enc);}
Output:
51.433718, -0.214126, 2 (Ireland, most of England and Wales, small part of Scotland):
geo-encoded: gc
geo-decoded: 53.438 ± 2.812e+00,  -5.625 ± 5.625e+00

51.433718, -0.214126, 9 (the umpire's chair on Center Court at Wimbledon):
geo-encoded: gcpue5hp4
geo-decoded: 51.433718 ± 2.146e-05,  -0.214126 ± 2.146e-05

51.433718, -0.214126, 17 (likely an individual molecule of the chair):
geo-encoded: gcpue5hp4ebnf8unc
geo-decoded: 51.43371800000523 ± 2.046e-11,  -0.21412600000303 ± 2.046e-11

57.64911, 10.40744, 11 (Wikipedia test value - Råbjerg Mile in Denmark):
geo-encoded: u4pruydqqvj
geo-decoded: 57.64911063 ± 6.706e-07,  10.40743969 ± 6.706e-07

59.1158, -151.687312, 7 (Perl Island, Alaska):
geo-encoded: bds0k38
geo-decoded: 59.1154 ± 6.866e-04,  -151.6875 ± 6.866e-04

38.743586, -109.499336, 8 (Delicate Arch, Utah):
geo-encoded: 9wfhkm11
geo-decoded: 38.74354 ± 8.583e-05,  -109.49919 ± 1.717e-04

Phix

with javascript_semantics
constant gBase32 = "0123456789bcdefghjkmnpqrstuvwxyz"
 
function encode_geohash(sequence location, integer precision)
    sequence r = {{-90,90},{-180,180}}  -- lat/long
    integer ll = 2,                     --  " " "
            hashval = 0, bits = 0
    string hash = ""
    while length(hash) < precision do
        atom mid = sum(r[ll])/2,
             gt = location[ll]>mid
        hashval = hashval*2+gt
        r[ll][2-gt] = mid
        bits += 1
        if bits=5 then
            hash &= gBase32[hashval+1]
            {hashval,bits} = {0,0}
        end if
        ll = 3-ll   -- (1 <==> 2)
    end while
    return hash
end function
 
function decode_geohash(string hash)
-- output is {{lat_lo,lat_hi},{long_lo,long_hi}}
    sequence r = {{-90,90},{-180,180}}  -- lat/long
    integer ll = 2                      --  " " "
    for h=1 to length(hash) do
        string b = sprintf("%05b",find(hash[h],gBase32)-1)
        for it=1 to 5 do
            r[ll][2-(b[it]='1')] = sum(r[ll])/2
            ll = 3-ll   -- (1 <==> 2)
        end for
    end for 
    return r
end function
 
sequence tests = {{{51.433718, -0.214126}, 2},
                  {{51.433718, -0.214126}, 9},
                  {{57.64911,  10.40744 }, 11},
                  {{57.64911,  10.40744 }, 22}}
 
for i=1 to length(tests) do
    {sequence location, integer precision} = tests[i]
    string geohash = encode_geohash(location, precision)
    printf(1,"geohash for %v, precision %d = %s\n",{location, precision, geohash})
    tests[i] = geohash
end for
 
printf(1,"\ndecode tests:\n")
tests = append(tests,"ezs42")
for i=1 to length(tests) do
    printf(1,"%-22s ==> %v\n",{tests[i],decode_geohash(tests[i])})
end for
Output:
geohash for {51.433718,-0.214126}, precision 2 = gc
geohash for {51.433718,-0.214126}, precision 9 = gcpue5hp4
geohash for {57.64911,10.40744}, precision 11 = u4pruydqqvj
geohash for {57.64911,10.40744}, precision 22 = u4pruydqqvj8pr9yc27rjr

decode tests:
gc                     ==> {{50.625,56.25},{-11.25,0}}
gcpue5hp4              ==> {{51.43369675,51.43373966},{-0.2141475677,-0.2141046524}}
u4pruydqqvj            ==> {{57.64910996,57.6491113},{10.40743902,10.40744036}}
u4pruydqqvj8pr9yc27rjr ==> {{57.64911,57.64911},{10.40744,10.40744}}
ezs42                  ==> {{42.58300781,42.62695312},{-5.625,-5.581054688}}

Not surprisingly, given the area it covers, "gc" is not even accurate to one significant digit, but a precision of 9 is accurate to 5 or 6 significant decimal digits, 11 to 6 or 7 digits, and 22 exceeds the natural 10 sig digs of %v. Note that 32-bit gives a last character of 'q' for the precision 22 test, for obvious reasons. The above results are from using the 64-bit interpreter.

PicoLisp

(scl 20)
(setq *GBASE32 (chop "0123456789bcdefghjkmnpqrstuvwxyz"))
(de encode (Lat Lng Prec)
   (let
      (Base (circ (list -180.0 180.0) (list -90.0 90.0))
         Curr (circ Lng Lat)
         Lst
         (make
            (do (* 5 Prec)
               (let
                  (B (++ Base)
                     C (++ Curr)
                     M (/ (sum prog B) 2) )
                  (if (> C M)
                     (prog (set B M) (link 1))
                     (set (cdr B) M)
                     (link 0) ) ) ) ) )
      (pack
         (make
            (for (L Lst L)
               (link
                  (get
                     *GBASE32
                     (inc (bin (pack (cut 5 'L)))) ) ) ) ) ) ) )
(println (encode 51.433718 -0.214126 2))
(println (encode 51.433718 -0.214126 9))
(println (encode 57.649110 10.407440 11))
Output:
"gc"
"gcpue5hp4"
"u4pruydqqvj"

Python

ch32 = "0123456789bcdefghjkmnpqrstuvwxyz"
bool2ch = {f"{i:05b}": ch for i, ch in enumerate(ch32)}
ch2bool = {v : k for k, v in bool2ch.items()}

def bisect(val, mn, mx, bits):
    mid = (mn + mx) / 2
    if val < mid:
        bits <<= 1                        # push 0
        mx = mid                          # range lower half
    else:
        bits = bits << 1 | 1              # push 1
        mn = mid                          # range upper half

    return mn, mx, bits

def encoder(lat, lng, pre):
    latmin, latmax = -90, 90
    lngmin, lngmax = -180, 180
    bits = 0
    for i in range(pre * 5):
        if i % 2:
            # odd bit: bisect latitude
            latmin, latmax, bits = bisect(lat, latmin, latmax, bits)
        else:
            # even bit: bisect longitude
            lngmin, lngmax, bits = bisect(lng, lngmin, lngmax, bits)
    # Bits to characters
    b = f"{bits:0{pre * 5}b}"
    geo = (bool2ch[b[i*5: (i+1)*5]] for i in range(pre))

    return ''.join(geo)

def decoder(geo):
    minmaxes, latlong = [[-90.0, 90.0], [-180.0, 180.0]], True
    for c in geo:
        for bit in ch2bool[c]:
            minmaxes[latlong][bit != '1'] = sum(minmaxes[latlong]) / 2
            latlong = not latlong

    return minmaxes

if __name__ == '__main__':
    for (lat, lng), pre in [([51.433718, -0.214126],  2),
                            ([51.433718, -0.214126],  9),
                            ([57.64911,  10.40744] , 11),
                            ([57.64911,  10.40744] , 22)]:
        print("encoder(lat=%f, lng=%f, pre=%i) = %r"
              % (lat, lng, pre, encoder(lat, lng, pre)))
Output:
encoder(lat=51.433718, lng=-0.214126, pre=2) = 'gc'
encoder(lat=51.433718, lng=-0.214126, pre=9) = 'gcpue5hp4'
encoder(lat=57.649110, lng=10.407440, pre=11) = 'u4pruydqqvj'
encoder(lat=57.649110, lng=10.407440, pre=22) = 'u4pruydqqvj8pr9yc27rjr'

Note: The precision can be increased but would need latitude and longitude expressed with more precision than floats, such as fractions or decimals, for more accurate results. Due to duck typing, the encoder function would not need changing, though.

Raku

Module based

Reference: Used this for verification.

#20200615 Raku programming solution

use Geo::Hash;

# task example 1 : Ireland, most of England and Wales, small part of Scotland
say geo-encode(51.433718e0, -0.214126e0, 2);

# task example 2 : the umpire's chair on Center Court at Wimbledon
say geo-encode(51.433718e0, -0.214126e0, 9);

# Lake Raku is an artificial lake in Tallinn, Estonia
# https://goo.gl/maps/MEBXXhiFbN8WMo5z8
say geo-encode(59.358639e0, 24.744778e0, 4);

# Village Raku is a development committee in north-western Nepal
# https://goo.gl/maps/33s7k2h3UrHCg8Tb6
say geo-encode(29.2021188e0, 81.5324561e0, 4);
Output:
gc
gcpue5hp4
ud99
tv1y

Roll your own

Alternately, a roll-your-own version that will work with any Real coordinate, not just floating point values, and thus can return ridiculous precision. The geo-decode routine returns the range in which the actual value will be found; converted here to the mid-point with the interval size. Probably better to specify an odd precision so the error interval ends up the same for both latitude and longitude.

my @Geo32 = <0 1 2 3 4 5 6 7 8 9 b c d e f g h j k m n p q r s t u v w x y z>;

sub geo-encode ( Rat(Real) $latitude, Rat(Real) $longitude, Int $precision = 9 ) {
    my @coord = $latitude, $longitude;
    my @range = [-90, 90], [-180, 180];
    my $which = 1;
    my $value = '';
    while $value.chars < $precision * 5 {
        my $mid = @range[$which].sum / 2;
        $value ~= my $upper = +(@coord[$which] > $mid);
        @range[$which][not $upper] = $mid;
        $which = not $which;
    }
    @Geo32[$value.comb(5)».parse-base(2)].join;
}

sub geo-decode ( Str $geo ) {
     my @range = [-90, 90], [-180, 180];
     my $which = 1;
     my %Geo32 = @Geo32.antipairs;
     for %Geo32{$geo.comb}».fmt('%05b').join.comb {
         @range[$which][$_] = @range[$which].sum / 2;
         $which = not $which;
     }
     @range
}

# TESTING

for 51.433718,   -0.214126,  2, # Ireland, most of England and Wales, small part of Scotland
    51.433718,   -0.214126,  9, # the umpire's chair on Center Court at Wimbledon
    51.433718,   -0.214126, 17, # likely an individual molecule of the chair
    57.649110,   10.407440, 11, # Wikipedia test value - Råbjerg Mile in Denmark
    59.358639,   24.744778,  7, # Lake Raku in Estonia
    29.2021188, 81.5324561,  7  # Village Raku in Nepal
  -> $lat, $long, $precision {
     say "$lat, $long, $precision:\ngeo-encoded: ",
     my $enc = geo-encode $lat, $long, $precision;
     say 'geo-decoded: ', geo-decode($enc).map( {-.sum/2 ~ ' ± ' ~
          (abs(.[0]-.[1])/2).Num.fmt('%.3e')} ).join(',  ') ~ "\n";
}
51.433718, -0.214126, 2:
geo-encoded: gc
geo-decoded: 53.4375 ± 2.813e+00,  -5.625 ± 5.625e+00

51.433718, -0.214126, 9:
geo-encoded: gcpue5hp4
geo-decoded: 51.4337182 ± 2.146e-05,  -0.21412611 ± 2.146e-05

51.433718, -0.214126, 17:
geo-encoded: gcpue5hp4ebnf8unc
geo-decoded: 51.43371800000523 ± 2.046e-11,  -0.21412600000303 ± 2.046e-11

57.64911, 10.40744, 11:
geo-encoded: u4pruydqqvj
geo-decoded: 57.64911063 ± 6.706e-07,  10.407439694 ± 6.706e-07

59.358639, 24.744778, 7:
geo-encoded: ud99ejf
geo-decoded: 59.358444 ± 6.866e-04,  24.744644 ± 6.866e-04

29.2021188, 81.5324561, 7:
geo-encoded: tv1ypk4
geo-decoded: 29.202347 ± 6.866e-04,  81.532974 ± 6.866e-04

RPL

Translation of: Python
Works with: HP version 48
« ROT ROT DUP ∑LIST 2 /
  ROT OVER < 
  ROT OVER 1 + 4 ROLL PUT
  ROT SL ROT NOT R→B OR
» 'BISECT' STO   @ ( val (mn,mx) bits → (a,b) bits )

« "0123456789bcdefghjkmnpqrstuvwxyz" "" → coord pre ch32 hash
  « { -90 90 } { -180 180 } #0
    0 pre 5 * 1 - FOR j
       IF j 2 MOD THEN
          coord 1 GET 4 ROLL ROT BISECT ROT SWAP
       ELSE
          coord 2 GET ROT ROT BISECT
       END
    NEXT
    1 pre START
       ch32 OVER #31d AND B→R 1 + DUP SUB 
       'hash' STO+ 32 / 
    NEXT
    3 DROPN hash
» » '→GEOH' STO   @ ( { lat long } pre → "geohash" )   

« "0123456789bcdefghjkmnpqrstuvwxyz" "" → hash ch32
  « "" BIN 
    1 hash SIZE FOR j
       ch32 hash j DUP SUB POS
       1 - 32 + R→B →STR 4 OVER SIZE 1 - SUB +
    NEXT
    'hash' STO
    { {-90,90} {-180,180} }
    1 hash SIZE FOR j
       j 2 MOD 1 + DUP2 GET
       hash j DUP SUB "0" == 1 +
       OVER ∑LIST 2 / PUT PUT
    NEXT
» » 'GEOH→' STO   @ ( "geohash" → { { latmin latmax } { longmin longmax ) }  
{ 51.433718 -0.214126 } 2 GEOH→
{ 51.433718 -0.214126 } 9 GEOH→
{ 57.649110 10.407440 } 11 GEOH→
Output:
3: "gc"
2: "gcpuxe0rj"
1: "u4pruydqqvj"

RPL floating-point numbers have only 12 significant digits, which could explain the error in the second case.

"gc" GEOH→
"gcpue5hp4" GEOH→
"u4pruydqqvj" GEOH→
Output:
3: { { 50.625 56.25 } { -11.25 0 } }
2: { { 51.4336967465 51.433739662 } { -.21414756775 -.214104652406 } }
1: { { 57.6491099595 57.649111301 } { 10.4074390233 10.4074403644 } }


Scala

Translation of: Swift
object Base32 {
  val base32 = "0123456789bcdefghjkmnpqrstuvwxyz" // no "a", "i", "l", or "o"
}

case class Coordinate(latitude: Double, longitude: Double) {
  override def toString: String = {
    val latitudeHemisphere = if (latitude < 0) " S" else " N"
    val longitudeHemisphere = if (longitude < 0) " W" else " E"
    s"${math.abs(latitude)}$latitudeHemisphere, ${math.abs(longitude)}$longitudeHemisphere"
  }
}

object GeoHashEncoder {
  def encodeGeohash(coordinate: Coordinate, precision: Int = 9): String = {
    var latitudeRange: (Double, Double) = (-90.0, 90.0)
    var longitudeRange: (Double, Double) = (-180.0, 180.0)

    var hash = ""
    var hashVal = 0
    var bits = 0
    var even = true

    while (hash.length < precision) {
      val valCoord = if (even) coordinate.longitude else coordinate.latitude
      val (rangeStart, rangeEnd) = if (even) longitudeRange else latitudeRange
      val mid = (rangeStart + rangeEnd) / 2

      if (valCoord > mid) {
        hashVal = (hashVal << 1) + 1
        if (even) longitudeRange = (mid, rangeEnd) else latitudeRange = (mid, rangeEnd)
      } else {
        hashVal = (hashVal << 1)
        if (even) longitudeRange = (rangeStart, mid) else latitudeRange = (rangeStart, mid)
      }

      even = !even

      if (bits < 4) {
        bits += 1
      } else {
        bits = 0
        hash += Base32.base32.charAt(hashVal)
        hashVal = 0
      }
    }
    hash
  }
}

object Main extends App {
  val coordinate1 = Coordinate(51.433718, -0.214126)
  val coordinate2 = Coordinate(57.649110, 10.407440)

  println(s"Geohash for: ${coordinate1.toString}, precision = 5 : ${GeoHashEncoder.encodeGeohash(coordinate1, 5)}")
  println(s"Geohash for: ${coordinate1.toString}, precision = 9 : ${GeoHashEncoder.encodeGeohash(coordinate1)}")
  println(s"Geohash for: ${coordinate2.toString}, precision = 11 : ${GeoHashEncoder.encodeGeohash(coordinate2, 11)}")
}
Output:
Geohash for: 51.433718 N, 0.214126 W, precision = 5 : gcpue
Geohash for: 51.433718 N, 0.214126 W, precision = 9 : gcpue5hp4
Geohash for: 57.64911 N, 10.40744 E, precision = 11 : u4pruydqqvj

Swift

let base32 = "0123456789bcdefghjkmnpqrstuvwxyz" // no "a", "i", "l", or "o"

extension String {
  subscript(i: Int) -> String {
    String(self[index(startIndex, offsetBy: i)])
  }
}

struct Coordinate {
  var latitude: Double
  var longitude: Double

  func toString() -> String {
    var latitudeHemisphere = ""
    var longitudeHemisphere = ""

    latitudeHemisphere = latitude < 0 ? " S" : " N"
    longitudeHemisphere = longitude < 0 ? " W" : " E"

    return "\(abs(latitude))\(latitudeHemisphere), \(abs(longitude))\(longitudeHemisphere)"
  }
}

func encodeGeohash (for coordinate: Coordinate, withPrecision precision: Int = 9) -> String {
  var latitudeRange = -90.0...90.0
  var longitudeRange = -180...180.0

  var hash = ""
  var hashVal = 0
  var bits = 0
  var even = true

  while (hash.count < precision) {
    let val     = even ? coordinate.longitude: coordinate.latitude
    var range   = even ? longitudeRange : latitudeRange
    let mid     = (range.lowerBound + range.upperBound) / 2

    if (val > mid) {
      hashVal = (hashVal << 1) + 1
      range = mid...range.upperBound

      if even { longitudeRange = mid...longitudeRange.upperBound }
      else    {  latitudeRange = mid...latitudeRange.upperBound }
    } else {
      hashVal = (hashVal << 1) + 0
      range   = range.lowerBound...mid

      if even { longitudeRange = longitudeRange.lowerBound...mid }
      else    {  latitudeRange =  latitudeRange.lowerBound...mid }
    }

    even = !even

    if (bits < 4) {
      bits += 1
    } else {
      bits = 0
      hash += base32[hashVal]
      hashVal = 0
    }
  }
  return hash
}

let coordinate1 = Coordinate(latitude: 51.433718, longitude: -0.214126)
let coordinate2 = Coordinate(latitude: 57.649110, longitude: 10.407440)

print ("Geohash for: \(coordinate1.toString()), precision = 5 : \(encodeGeohash(for: coordinate, withPrecision: 5))")
print ("Geohash for: \(coordinate1.toString()), precision = 9 : \(encodeGeohash(for: coordinate))")
print ("Geohash for: \(coordinate2.toString()), precision = 11 : \(encodeGeohash(for: coordinate, withPrecision: 11))")
Output:
Geohash for: 51.433718 N, 0.214126 W, precision = 5 : gcpue
Geohash for: 51.433718 N, 0.214126 W, precision = 9 : gcpue5hp4
Geohash for: 57.64911 N, 10.40744 E, precision = 11 : u4pruydqqvj

V (Vlang)

Translation of: go
struct Location {
    lat f64
    lng f64
}
 
fn (loc Location) str() string { return "[$loc.lat, $loc.lng]" }
 
struct Range {
    lower f64
    upper f64
}
 
const g_base32 = "0123456789bcdefghjkmnpqrstuvwxyz"
 
fn encode_geo_hash(loc Location, prec int) string {
    mut lat_range := Range{-90, 90}
    mut lng_range := Range{-180, 180}
    mut hash := ''
    mut hash_val := u32(0)
    mut bits := 0
    mut even := true
    for hash.len < prec {
        mut val := loc.lat
        mut rng := lat_range
        if even {
            val = loc.lng
            rng = lng_range
        }
        mid := (rng.lower + rng.upper) / 2
        if val > mid {
            hash_val = (hash_val << 1) + 1
            rng = Range{mid, rng.upper}
            if even {
                lng_range = Range{mid, lng_range.upper}
            } else {
                lat_range = Range{mid, lat_range.upper}
            }
        } else {
            hash_val <<= 1
            if even {
                lng_range = Range{lng_range.lower, mid}
            } else {
                lat_range = Range{lat_range.lower, mid}
            }
        }
        even = !even
        if bits < 4 {
            bits++
        } else {
            bits = 0
            hash+=g_base32[hash_val..hash_val+1]
            hash_val = u32(0)
        }
    }
    return hash.str()
}
 
fn main() {
    locs := [Location{51.433718, -0.214126},
        Location{51.433718, -0.214126},
        Location{57.64911, 10.40744},
    ]
    precs := [2, 9, 11]
 
    for i, loc in locs {
        geohash := encode_geo_hash(loc, precs[i])
        println("geohash for $loc, precision ${precs[i]:-2} = $geohash")
    }
}
Output:
geohash for [51.433718, -0.214126], precision 2  = gc
geohash for [51.433718, -0.214126], precision 9  = gcpue5hp4
geohash for [57.649110, 10.407440], precision 11 = u4pruydqqvj

Wren

Translation of: Swift
Library: Wren-fmt
import "./fmt" for Fmt

var gBase32 = "0123456789bcdefghjkmnpqrstuvwxyz"

var encodeGeohash = Fn.new { |location, prec|
    var latRange = -90..90
    var lngRange = -180..180
    var hash = ""
    var hashVal = 0
    var bits = 0
    var even = true
    while (hash.count < prec) {
        var val = even ? location[1] : location[0]
        var rng = even ? lngRange : latRange
        var mid = (rng.from + rng.to) / 2
        if (val > mid) {
            hashVal = hashVal*2 + 1
            rng = mid..rng.to
            if (even) lngRange = mid..lngRange.to else latRange = mid..latRange.to
        } else {
            hashVal = hashVal * 2
            if (even) lngRange = lngRange.from..mid else latRange = latRange.from..mid
        }
        even = !even
        if (bits < 4) {
            bits = bits + 1
        } else {
            bits = 0
            hash = hash + gBase32[hashVal]
            hashVal = 0
        }
    }
    return hash
}

var data = [
    [[51.433718, -0.214126], 2],
    [[51.433718, -0.214126], 9],
    [[57.64911,  10.40744 ], 11]
]

for (d in data) {
    var geohash = encodeGeohash.call(d[0], d[1])
    var loc = "[%(Fmt.f(9, d[0][0], 6)), %(Fmt.f(9, d[0][1], 6))]"
    System.print("geohash for %(loc), precision %(Fmt.d(-2, d[1])) = %(geohash)")
}
Output:
geohash for [51.433718, -0.214126], precision 2  = gc
geohash for [51.433718, -0.214126], precision 9  = gcpue5hp4
geohash for [57.649110, 10.407440], precision 11 = u4pruydqqvj