Geohash: Difference between revisions
Add Scala implementation
m (add decoder) |
(Add Scala implementation) |
||
(24 intermediate revisions by 15 users not shown) | |||
Line 17:
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.
Line 22 ⟶ 26:
* [[wp:Geohash|Wikipedia article - Geohash]].
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">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)))</syntaxhighlight>
{{out}}
<pre>
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'
</pre>
=={{header|Action!}}==
{{libheader|Action! Tool Kit}}
{{libheader|Action! Real Math}}
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Geohash.png Screenshot from Atari 8-bit computer]
<pre>
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)
</pre>
=={{header|Factor}}==
Factor comes with the <code>geohash</code> vocabulary. See the implementation [https://docs.factorcode.org/content/vocab-geohash.html here].
{{works with|Factor|0.99 2020-03-02}}
<
: encode-geohash ( latitude longitude precision -- str )
Line 42 ⟶ 238:
! Decoding
"u4pruydqqvj" dup geohash>
"coordinates for %s ~= [%f, %f]\n" printf</
{{out}}
<pre>
Line 52 ⟶ 248:
</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
// 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)
</syntaxhighlight>
{{out}}
<pre>
gc
gcpue5hp4
u4pruydqqvj
</pre>
=={{header|Go}}==
{{trans|Swift}}
<
import (
Line 124 ⟶ 336:
fmt.Printf("geohash for %v, precision %-2d = %s\n", loc, precs[i], geohash)
}
}</
{{out}}
Line 131 ⟶ 343:
geohash for [51.433718, -0.214126], precision 9 = gcpue5hp4
geohash for [57.649110, 10.407440], precision 11 = u4pruydqqvj
</pre>
=={{header|J}}==
<syntaxhighlight lang=J>gdigits=: '0123456789bcdefghjkmnpqrstuvwxyz'
geohash=: {{
bits=. 3*x
x{.gdigits{~_5 #.\,|:|.(bits#2)#:<.(2^bits)*(y+90 180)%180 360
}}</syntaxhighlight>
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.
<syntaxhighlight lang=J> 2 geohash 51.433718 _0.214126
gc
9 geohash 51.433718 _0.214126
gcpue5hp4
11 geohash 57.64911 10.40744
u4pruydqqvj</syntaxhighlight>
And, going the other direction (producing a min and max lat and long value for the geohash):
<syntaxhighlight lang=J>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
}}</syntaxhighlight>
This gives us:
<syntaxhighlight lang=J> 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</syntaxhighlight>
Or
<syntaxhighlight lang=J> 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</syntaxhighlight>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]] and [[#Python|Python]]'''
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq, and with fq.'''
'''Generic Utilities'''
<syntaxhighlight lang=jq>
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));
</syntaxhighlight>
'''GeoHash'''
<syntaxhighlight lang=jq>
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))) )"
</syntaxhighlight>
{{output}}
<pre>
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]]
</pre>
=={{header|Julia}}==
{{trans|Python}}
<
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)
Line 187 ⟶ 552:
println("decoded = ", decoder(encoded))
end
</
<pre>
encoder(lat=51.433718, lng=-0.214126, pre=2) = gc
Line 199 ⟶ 564:
</pre>
=={{header|
{{trans|Python}}
{{trans|Julia}}
We omitted the test with precision 22 as it exceeds the capacity of a 64 bits integer.
<syntaxhighlight lang="nim">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)}</syntaxhighlight>
{{out}}
<pre>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]]</pre>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">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);}</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">gBase32</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"0123456789bcdefghjkmnpqrstuvwxyz"</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">encode_geohash</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">location</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">precision</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">90</span><span style="color: #0000FF;">,</span><span style="color: #000000;">90</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">180</span><span style="color: #0000FF;">,</span><span style="color: #000000;">180</span><span style="color: #0000FF;">}}</span> <span style="color: #000080;font-style:italic;">-- lat/long</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ll</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- " " "</span>
<span style="color: #000000;">hashval</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">hash</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hash</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">precision</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">])/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">gt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">location</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">]></span><span style="color: #000000;">mid</span>
<span style="color: #000000;">hashval</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">hashval</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">gt</span>
<span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">gt</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span>
<span style="color: #000000;">bits</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">bits</span><span style="color: #0000FF;">=</span><span style="color: #000000;">5</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">hash</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">gBase32</span><span style="color: #0000FF;">[</span><span style="color: #000000;">hashval</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">hashval</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bits</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">ll</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ll</span> <span style="color: #000080;font-style:italic;">-- (1 <==> 2)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">hash</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">decode_geohash</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">hash</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- output is {{lat_lo,lat_hi},{long_lo,long_hi}}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">90</span><span style="color: #0000FF;">,</span><span style="color: #000000;">90</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">180</span><span style="color: #0000FF;">,</span><span style="color: #000000;">180</span><span style="color: #0000FF;">}}</span> <span style="color: #000080;font-style:italic;">-- lat/long</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ll</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span> <span style="color: #000080;font-style:italic;">-- " " "</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hash</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%05b"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hash</span><span style="color: #0000FF;">[</span><span style="color: #000000;">h</span><span style="color: #0000FF;">],</span><span style="color: #000000;">gBase32</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">it</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">5</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">it</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'1'</span><span style="color: #0000FF;">)]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ll</span><span style="color: #0000FF;">])/</span><span style="color: #000000;">2</span>
<span style="color: #000000;">ll</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ll</span> <span style="color: #000080;font-style:italic;">-- (1 <==> 2)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">51.433718</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">0.214126</span><span style="color: #0000FF;">},</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">51.433718</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">0.214126</span><span style="color: #0000FF;">},</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">57.64911</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10.40744</span> <span style="color: #0000FF;">},</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">57.64911</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10.40744</span> <span style="color: #0000FF;">},</span> <span style="color: #000000;">22</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">location</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">precision</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">geohash</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">encode_geohash</span><span style="color: #0000FF;">(</span><span style="color: #000000;">location</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">precision</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"geohash for %v, precision %d = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">location</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">precision</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">geohash</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">geohash</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\ndecode tests:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ezs42"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%-22s ==> %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">decode_geohash</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 267 ⟶ 786:
ezs42 ==> {{42.58300781,42.62695312},{-5.625,-5.581054688}}
</pre>
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
=={{header|PicoLisp}}==
<syntaxhighlight lang="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))</syntaxhighlight>
{{out}}
<pre>
"gc"
"gcpue5hp4"
"u4pruydqqvj"
</pre>
=={{header|Python}}==
<
bool2ch = {f"{i:05b}": ch for i, ch in enumerate(ch32)}
ch2bool = {v : k for k, v in bool2ch.items()}
Line 317 ⟶ 871:
([57.64911, 10.40744] , 22)]:
print("encoder(lat=%f, lng=%f, pre=%i) = %r"
% (lat, lng, pre, encoder(lat, lng, pre)))</
{{out}}
Line 325 ⟶ 879:
encoder(lat=57.649110, lng=10.407440, pre=22) = 'u4pruydqqvj8pr9yc27rjr'</pre>
Note: The precision can be increased but would need
=={{header|Raku}}==
===Module based===
Reference: Used [https://www.movable-type.co.uk/scripts/geohash.html this] for verification.
<syntaxhighlight lang="raku"
use Geo::Hash;
Line 346 ⟶ 900:
# Village Raku is a development committee in north-western Nepal
# https://goo.gl/maps/33s7k2h3UrHCg8Tb6
say geo-encode(29.2021188e0, 81.5324561e0, 4);</
{{out}}
<pre>gc
Line 359 ⟶ 913:
to specify an odd precision so the error interval ends up the same for both latitude and longitude.
<syntaxhighlight lang="raku"
sub geo-encode ( Rat(Real) $latitude, Rat(Real) $longitude, Int $precision = 9 ) {
Line 399 ⟶ 953:
say 'geo-decoded: ', geo-decode($enc).map( {-.sum/2 ~ ' ± ' ~
(abs(.[0]-.[1])/2).Num.fmt('%.3e')} ).join(', ') ~ "\n";
}</
<pre>51.433718, -0.214126, 2:
geo-encoded: gc
Line 423 ⟶ 977:
geo-encoded: tv1ypk4
geo-decoded: 29.202347 ± 6.866e-04, 81.532974 ± 6.866e-04
</pre>
=={{header|RPL}}==
{{trans|Python}}
{{works with|HP|48}}
« ROT ROT DUP ∑LIST 2 /
ROT OVER <
ROT OVER 1 + 4 ROLL PUT
ROT SL ROT NOT R→B OR
» '<span style="color:blue">BISECT</span>' STO <span style="color:grey">''@ ( val (mn,mx) bits → (a,b) bits )''</span>
« "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 <span style="color:blue">BISECT</span> ROT SWAP
'''ELSE'''
coord 2 GET ROT ROT <span style="color:blue">BISECT</span>
'''END'''
'''NEXT'''
1 pre '''START'''
ch32 OVER #31d AND B→R 1 + DUP SUB
'hash' STO+ 32 /
'''NEXT'''
3 DROPN hash
» » '<span style="color:blue">→GEOH</span>' STO <span style="color:grey">''@ ( { lat long } pre → "geohash" )''</span>
« "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'''
» » '<span style="color:blue">GEOH→</span>' STO <span style="color:grey">''@ ( "geohash" → { { latmin latmax } { longmin longmax ) }''</span>
{ 51.433718 -0.214126 } 2 <span style="color:blue">GEOH→</span>
{ 51.433718 -0.214126 } 9 <span style="color:blue">GEOH→</span>
{ 57.649110 10.407440 } 11 <span style="color:blue">GEOH→</span>
{{out}}
<pre>
3: "gc"
2: "gcpuxe0rj"
1: "u4pruydqqvj"
</pre>
RPL floating-point numbers have only 12 significant digits, which could explain the error in the second case.
"gc" <span style="color:blue">GEOH→</span>
"gcpue5hp4" <span style="color:blue">GEOH→</span>
"u4pruydqqvj" <span style="color:blue">GEOH→</span>
{{out}}
<pre>
3: { { 50.625 56.25 } { -11.25 0 } }
2: { { 51.4336967465 51.433739662 } { -.21414756775 -.214104652406 } }
1: { { 57.6491099595 57.649111301 } { 10.4074390233 10.4074403644 } }
</pre>
=={{header|Scala}}==
{{trans|Swift}}
<syntaxhighlight lang="Scala">
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)}")
}
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Swift}}==
<
extension String {
Line 498 ⟶ 1,184:
print ("Geohash for: \(coordinate2.toString()), precision = 11 : \(encodeGeohash(for: coordinate, withPrecision: 11))")
</syntaxhighlight>
{{out}}
Line 506 ⟶ 1,192:
Geohash for: 57.64911 N, 10.40744 E, precision = 11 : u4pruydqqvj
</pre>
=={{header|V (Vlang)}}==
{{trans|go}}
<syntaxhighlight lang="v (vlang)">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")
}
}</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Wren}}==
{{trans|Swift}}
{{libheader|Wren-fmt}}
<
var gBase32 = "0123456789bcdefghjkmnpqrstuvwxyz"
Line 555 ⟶ 1,317:
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)")
}</
{{out}}
|