Geohash: Difference between revisions
Alextretyak (talk | contribs) (Added 11l) |
(Add Scala implementation) |
||
(16 intermediate revisions by 10 users not shown) | |||
Line 30: | Line 30: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">V ch32 = Array(‘0123456789bcdefghjkmnpqrstuvwxyz’) |
||
V bool2ch = Dict(enumerate(ch32), (i, ch) -> (bin(i).zfill(5), ch)) |
V bool2ch = Dict(enumerate(ch32), (i, ch) -> (bin(i).zfill(5), ch)) |
||
V ch2bool = Dict(bool2ch.items(), (k, v) -> (v, k)) |
V ch2bool = Dict(bool2ch.items(), (k, v) -> (v, k)) |
||
Line 71: | Line 71: | ||
(51.433718, -0.214126, 9), |
(51.433718, -0.214126, 9), |
||
(57.64911, 10.40744, 11)] |
(57.64911, 10.40744, 11)] |
||
print(‘encoder(lat=#.6, lng=#.6, pre=#.) = '#.'’.format(lat, lng, pre, encoder(lat, lng, pre)))</ |
print(‘encoder(lat=#.6, lng=#.6, pre=#.) = '#.'’.format(lat, lng, pre, encoder(lat, lng, pre)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 78: | Line 78: | ||
encoder(lat=51.433718, lng=-0.214126, pre=9) = 'gcpue5hp4' |
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=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> |
</pre> |
||
Line 83: | Line 222: | ||
Factor comes with the <code>geohash</code> vocabulary. See the implementation [https://docs.factorcode.org/content/vocab-geohash.html here]. |
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}} |
{{works with|Factor|0.99 2020-03-02}} |
||
< |
<syntaxhighlight lang="factor">USING: formatting generalizations geohash io kernel sequences ; |
||
: encode-geohash ( latitude longitude precision -- str ) |
: encode-geohash ( latitude longitude precision -- str ) |
||
Line 99: | Line 238: | ||
! Decoding |
! Decoding |
||
"u4pruydqqvj" dup geohash> |
"u4pruydqqvj" dup geohash> |
||
"coordinates for %s ~= [%f, %f]\n" printf</ |
"coordinates for %s ~= [%f, %f]\n" printf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 110: | Line 249: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Create a geoHash String. Nigel Galloway: June 26th., 2020 |
// 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 fG n g=Seq.unfold(fun(α,β)->let τ=(α+β)/2.0 in Some(if τ>g then (0,(α,τ)) else (1,(τ,b)))) n |
||
Line 118: | Line 257: | ||
let geoHash n g z=let N="0123456789bcdefghjkmnpqrstuvwxyz" in [|for τ in fN n g z do yield N.[fI τ]|] |> System.String |
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) |
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> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 127: | Line 266: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Swift}} |
{{trans|Swift}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 197: | Line 336: | ||
fmt.Printf("geohash for %v, precision %-2d = %s\n", loc, precs[i], geohash) |
fmt.Printf("geohash for %v, precision %-2d = %s\n", loc, precs[i], geohash) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 204: | Line 343: | ||
geohash for [51.433718, -0.214126], precision 9 = gcpue5hp4 |
geohash for [51.433718, -0.214126], precision 9 = gcpue5hp4 |
||
geohash for [57.649110, 10.407440], precision 11 = u4pruydqqvj |
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> |
</pre> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">const ch32 = "0123456789bcdefghjkmnpqrstuvwxyz" |
||
const bool2ch = Dict(string(i-1, base=2, pad=5) => ch for (i, ch) in enumerate(ch32)) |
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) |
const ch2bool = Dict(v => k for (k, v) in bool2ch) |
||
Line 260: | Line 552: | ||
println("decoded = ", decoder(encoded)) |
println("decoded = ", decoder(encoded)) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
encoder(lat=51.433718, lng=-0.214126, pre=2) = gc |
encoder(lat=51.433718, lng=-0.214126, pre=2) = gc |
||
Line 276: | Line 568: | ||
{{trans|Julia}} |
{{trans|Julia}} |
||
We omitted the test with precision 22 as it exceeds the capacity of a 64 bits integer. |
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 |
const |
||
Line 333: | Line 625: | ||
let encoded = encode(lat, long, pre) |
let encoded = encode(lat, long, pre) |
||
echo &"encoder(lat = {lat}, long = {long}, pre = {pre}) = {encoded}" |
echo &"encoder(lat = {lat}, long = {long}, pre = {pre}) = {encoded}" |
||
echo &"decoded = {decode(encoded)}</ |
echo &"decoded = {decode(encoded)}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 345: | Line 637: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 397: | Line 689: | ||
map { sprintf("%.@{[max(3,$precision-3)]}f", ( -($$_[0] + $$_[1]) / 2)) . |
map { sprintf("%.@{[max(3,$precision-3)]}f", ( -($$_[0] + $$_[1]) / 2)) . |
||
' ± ' . sprintf('%.3e', (abs($$_[0] - $$_[1]) / 2)) |
' ± ' . sprintf('%.3e', (abs($$_[0] - $$_[1]) / 2)) |
||
} geo_decode($enc);}</ |
} geo_decode($enc);}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>51.433718, -0.214126, 2 (Ireland, most of England and Wales, small part of Scotland): |
<pre>51.433718, -0.214126, 2 (Ireland, most of England and Wales, small part of Scotland): |
||
Line 424: | Line 716: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>constant gBase32 = "0123456789bcdefghjkmnpqrstuvwxyz" |
|||
<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> |
|||
function encode_geohash(sequence location, integer precision) |
|||
sequence r = {{-90,90},{-180,180}} -- lat/long |
|||
<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> |
|||
integer ll = 2, -- " " " |
|||
<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> |
|||
hashval = 0, bits = 0 |
|||
<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> |
|||
string hash = "" |
|||
<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> |
|||
while length(hash) < precision do |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">hash</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span> |
|||
atom mid = sum(r[ll])/2, |
|||
<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> |
|||
gt = location[ll]>mid |
|||
<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> |
|||
hashval = hashval*2+gt |
|||
<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> |
|||
r[ll][2-gt] = mid |
|||
<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> |
|||
bits += 1 |
|||
<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> |
|||
if bits=5 then |
|||
<span style="color: #000000;">bits</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
hash &= gBase32[hashval+1] |
|||
<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> |
|||
{hashval,bits} = {0,0} |
|||
<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> |
|||
end if |
|||
<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> |
|||
ll = 3-ll -- (1 <==> 2) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<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> |
|||
return hash |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">hash</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function decode_geohash(string hash) |
|||
-- output is {{lat_lo,lat_hi},{long_lo,long_hi}} |
|||
<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> |
|||
sequence r = {{-90,90},{-180,180}} -- lat/long |
|||
<span style="color: #000080;font-style:italic;">-- output is {{lat_lo,lat_hi},{long_lo,long_hi}}</span> |
|||
integer ll = 2 -- " " " |
|||
<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> |
|||
for h=1 to length(hash) do |
|||
<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> |
|||
string b = sprintf("%05b",find(hash[h],gBase32)-1) |
|||
<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> |
|||
for it=1 to 5 do |
|||
<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> |
|||
r[ll][2-(b[it]='1')] = sum(r[ll])/2 |
|||
<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> |
|||
ll = 3-ll -- (1 <==> 2) |
|||
<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> |
|||
end for |
|||
<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> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
return r |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
sequence tests = {{{51.433718, -0.214126}, 2}, |
|||
{{51.433718, -0.214126}, 9}, |
|||
<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> |
|||
{{57.64911, 10.40744 }, 11}, |
|||
<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> |
|||
{{57.64911, 10.40744 }, 22}} |
|||
<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> |
|||
for i=1 to length(tests) do |
|||
{sequence location, integer precision} = tests[i] |
|||
<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> |
|||
string geohash = encode_geohash(location, precision) |
|||
<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> |
|||
printf(1,"geohash for %v, precision %d = %s\n",{location, precision, geohash}) |
|||
<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> |
|||
tests[i] = geohash |
|||
<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> |
|||
end for |
|||
<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> |
|||
printf(1,"\ndecode tests:\n") |
|||
tests = append(tests,"ezs42") |
|||
<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> |
|||
for i=1 to length(tests) do |
|||
<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> |
|||
printf(1,"%-22s ==> %v\n",{tests[i],decode_geohash(tests[i])}) |
|||
<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> |
|||
end for</lang> |
|||
<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}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 494: | Line 789: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(scl 20) |
||
(setq *GBASE32 (chop "0123456789bcdefghjkmnpqrstuvwxyz")) |
(setq *GBASE32 (chop "0123456789bcdefghjkmnpqrstuvwxyz")) |
||
(de encode (Lat Lng Prec) |
(de encode (Lat Lng Prec) |
||
Line 520: | Line 815: | ||
(println (encode 51.433718 -0.214126 2)) |
(println (encode 51.433718 -0.214126 2)) |
||
(println (encode 51.433718 -0.214126 9)) |
(println (encode 51.433718 -0.214126 9)) |
||
(println (encode 57.649110 10.407440 11))</ |
(println (encode 57.649110 10.407440 11))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 529: | Line 824: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">ch32 = "0123456789bcdefghjkmnpqrstuvwxyz" |
||
bool2ch = {f"{i:05b}": ch for i, ch in enumerate(ch32)} |
bool2ch = {f"{i:05b}": ch for i, ch in enumerate(ch32)} |
||
ch2bool = {v : k for k, v in bool2ch.items()} |
ch2bool = {v : k for k, v in bool2ch.items()} |
||
Line 576: | Line 871: | ||
([57.64911, 10.40744] , 22)]: |
([57.64911, 10.40744] , 22)]: |
||
print("encoder(lat=%f, lng=%f, pre=%i) = %r" |
print("encoder(lat=%f, lng=%f, pre=%i) = %r" |
||
% (lat, lng, pre, encoder(lat, lng, pre)))</ |
% (lat, lng, pre, encoder(lat, lng, pre)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 584: | Line 879: | ||
encoder(lat=57.649110, lng=10.407440, pre=22) = 'u4pruydqqvj8pr9yc27rjr'</pre> |
encoder(lat=57.649110, lng=10.407440, pre=22) = 'u4pruydqqvj8pr9yc27rjr'</pre> |
||
Note: The precision can be increased but would need |
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. |
||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
===Module based=== |
===Module based=== |
||
Reference: Used [https://www.movable-type.co.uk/scripts/geohash.html this] for verification. |
Reference: Used [https://www.movable-type.co.uk/scripts/geohash.html this] for verification. |
||
<lang |
<syntaxhighlight lang="raku" line>#20200615 Raku programming solution |
||
use Geo::Hash; |
use Geo::Hash; |
||
Line 605: | Line 900: | ||
# Village Raku is a development committee in north-western Nepal |
# Village Raku is a development committee in north-western Nepal |
||
# https://goo.gl/maps/33s7k2h3UrHCg8Tb6 |
# https://goo.gl/maps/33s7k2h3UrHCg8Tb6 |
||
say geo-encode(29.2021188e0, 81.5324561e0, 4);</ |
say geo-encode(29.2021188e0, 81.5324561e0, 4);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>gc |
<pre>gc |
||
Line 618: | Line 913: | ||
to specify an odd precision so the error interval ends up the same for both latitude and longitude. |
to specify an odd precision so the error interval ends up the same for both latitude and longitude. |
||
<lang |
<syntaxhighlight lang="raku" line>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 ) { |
sub geo-encode ( Rat(Real) $latitude, Rat(Real) $longitude, Int $precision = 9 ) { |
||
Line 658: | Line 953: | ||
say 'geo-decoded: ', geo-decode($enc).map( {-.sum/2 ~ ' ± ' ~ |
say 'geo-decoded: ', geo-decode($enc).map( {-.sum/2 ~ ' ± ' ~ |
||
(abs(.[0]-.[1])/2).Num.fmt('%.3e')} ).join(', ') ~ "\n"; |
(abs(.[0]-.[1])/2).Num.fmt('%.3e')} ).join(', ') ~ "\n"; |
||
}</ |
}</syntaxhighlight> |
||
<pre>51.433718, -0.214126, 2: |
<pre>51.433718, -0.214126, 2: |
||
geo-encoded: gc |
geo-encoded: gc |
||
Line 682: | Line 977: | ||
geo-encoded: tv1ypk4 |
geo-encoded: tv1ypk4 |
||
geo-decoded: 29.202347 ± 6.866e-04, 81.532974 ± 6.866e-04 |
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> |
</pre> |
||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">let base32 = "0123456789bcdefghjkmnpqrstuvwxyz" // no "a", "i", "l", or "o" |
||
extension String { |
extension String { |
||
Line 757: | Line 1,184: | ||
print ("Geohash for: \(coordinate2.toString()), precision = 11 : \(encodeGeohash(for: coordinate, withPrecision: 11))") |
print ("Geohash for: \(coordinate2.toString()), precision = 11 : \(encodeGeohash(for: coordinate, withPrecision: 11))") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 765: | Line 1,192: | ||
Geohash for: 57.64911 N, 10.40744 E, precision = 11 : u4pruydqqvj |
Geohash for: 57.64911 N, 10.40744 E, precision = 11 : u4pruydqqvj |
||
</pre> |
</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}}== |
=={{header|Wren}}== |
||
{{trans|Swift}} |
{{trans|Swift}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
||
var gBase32 = "0123456789bcdefghjkmnpqrstuvwxyz" |
var gBase32 = "0123456789bcdefghjkmnpqrstuvwxyz" |
||
Line 814: | Line 1,317: | ||
var loc = "[%(Fmt.f(9, d[0][0], 6)), %(Fmt.f(9, d[0][1], 6))]" |
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)") |
System.print("geohash for %(loc), precision %(Fmt.d(-2, d[1])) = %(geohash)") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 12:13, 1 February 2024
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
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.
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
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
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
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
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
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
« 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
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)
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
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