Geohash

From Rosetta Code
Revision as of 09:29, 15 June 2020 by rosettacode>Paddy3118 (→‎{{header|Python}}: Add Python solution)
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 doubles, latitude and longitude.


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."


Reference


Factor

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

Works with: Factor version 0.99 2020-03-02

<lang factor>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</lang>

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]

Go

Translation of: Swift

<lang go>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)
   }

}</lang>

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


Phix

<lang Phix>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}}

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,"%-12s ==> %v\n",{tests[i],decode_geohash(tests[i])})

end for</lang>

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

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}}
ezs42        ==> {{42.58300781,42.62695312},{-5.625,-5.581054688}}

Not surprisingly, "gc" is not even accurate to one significant digit, but a precision of 9 is accurate to 5 or 6 significant digits, and 11 to 6 or 7 digits.

Python

<lang python>ch32 = "0123456789bcdefghjkmnpqrstuvwxyz" bool2ch = {f"{i:05b}": ch for i, ch in enumerate(ch32)}


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)


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)))</lang>
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 lattitude and longitude expressed with more precision than floats, e.g. fractions or decimals for more accurate results. (but the encoder function would not need changing due to Duck Typing).

Swift

<lang 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))")

</lang>

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

Wren

Translation of: Swift
Library: Wren-fmt

<lang ecmascript>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)")

}</lang>

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