Geohash meine Positionen
Über Geohash
Geohash ist eines von vielen Codierungssystemen für geografische Positionen. Geohash-Positionen haben einige Vorteile. Es bietet einen Funktionscode anstelle der beiden üblichen Zahlen für Längen- und Breitengrad.
Die Herausforderung
Bei zwei Zahlen, dem Breiten- und Längengrad, wird die Geohash-Zeichenfolge der Länge 8 berechnet und zurückgegeben oder gedruckt. Ein längerer Geohash würde genauere Positionen ergeben, hier verwenden wir die Länge 8. Breiten- und Längengrade werden als Gleitkommazahlen (Grad) angegeben. Die Breiten liegen zwischen -90 und +90 (Süd nach Nord) und die Längen zwischen -180 und +180 (West nach Ost).
Algorithmus mit Beispiel
Ein Geohash-Code ist ein Base32-codierter Bitstring. In diesem Beispiel geht die Konvertierung in die andere Richtung als die Herausforderung. Wir konvertieren Geohash ezs42in Breiten- und Längengrade. Geohashes verwendet einen Satz von 32 Ziffern, die durch 5 Bits dargestellt werden. Die 32 Stellen sind 0 – 9für die ersten 10 und die Kleinbuchstaben zwischen der b – zAusnahme i, lund ofür den nächsten 22. Das heißt: 0123456789bcdefghjkmnpqrstuvwxyz.
Das erste Zeichen in ezs42ist e, das sich an der 0-indizierten Position 13 befindet, die die 5 Bits 01101 hat. Die Zeichen haben diese Bits:
e→ 13 → 01101z→ 31 → 11111s→ 24 → 110004→ 4 → 001002→ 2 → 00010
Beim Verbinden der Bits erhalten wir 0110111111110000010000010 .
Ausgehend von links stehen die geraden Bits (2., 4., 6., ...) für den Breitengrad ( 101111001001 ) und die ungeraden Bits (1., 3., 5., ...) für den Längengrad ( 0111110000000 ).
Mit jedem Bit gehen wir nach links oder rechts, um die Zahl durch Halbierung des Bereichs einzugrenzen. Das erste Bit der Längengradbits ( 0) wird verwendet, um zu entscheiden, ob der Längengrad zwischen -180 - 0 oder 0 - 180 liegt. Bit 0bedeutet, dass wir nach links gehen, dh -180 - 0. Das nächste Bit des Längengrads entscheidet, ob wir wählen -180 - -90 oder -90 - 0. Da es 1hier ist, gehen wir nach rechts zum nächsten Bereich: -90 - 0. Für jedes Bit gehen wir nach links (0) oder rechts (1) und halbieren den Min-Max-Bereich. Wenn alle Bits verbraucht sind, geben wir die mittlere Position (Durchschnitt) der letzten min und max zurück.
Wir wiederholen für den Breitengrad, außer jetzt beginnen wir mit der Auswahl zwischen -90 - 0 und 0 - 90 mit dem ersten Bit.
Der Breitengrad für 101111001001 wird +42.605.
Der Längengrad für 0111110000000 wird -5.603.
Dieses Beispiel stammt aus https://en.wikipedia.org/wiki/Geohash#Algorithm_and_example das hat einen visuelleren Durchgang.
Bei der Codierung von 0 ° (Äquator oder Nullmeridian) können Sie zwischen 01111 ... und 10000 ... wählen http://geohash.co/ Seite haben 01111 gewählt ...
Testfälle
(+48.8583, +2.2945) → u09tunqu # Eiffel Tower
(+40.68925, -74.04450) → dr5r7p62 # Statue of Liberty
(+29.9753, +31.1377) → stq4s8cf # The Great Sphinx at Giza
(-22.95191, -43.21044) → 75cm2txp # Statue of Christ, Brazil
(+71.17094, +25.78302) → usdkfsq8 # North Cape
(+90, +180) → zzzzzzzz # North Pole
(-90, -180) → 00000000 # South Pole
(+42.605, -5.603) → ezs42s00 # Léon, Spain from example above
Weitere Tests können erstellt oder überprüft werden http://geohash.co/ und Google Maps.
(GPS-Positionen werden häufig auch als Grad, Bogenminuten und Bogensekunden geschrieben. Die Position des Eiffelturms beträgt 48 ° 51 '29, 88 "N, 2 ° 17 '40, 20,20" E. Für Nord (N) und Ost (E) positiv Zahlen werden verwendet, damit wir die Position [48 + 51/60 + 29.88 / 3600, 2 + 17/60 + 40.20 / 3600] = [+48.8583, +2.2945] erhalten. Geohash-Codes können für eine schnelle Suche in der Nähe in Datenbanken gespeichert und indiziert werden In der Nähe befindliche Positionen haben dieselben Codepräfixe, es müssen jedoch Randfälle behandelt werden. Eine einzelne Indexsuche im Geohash-Code auf einem oder einem kleinen Satz von Codepräfixen ist normalerweise viel schneller als die Verwendung von zwei Indizes, dh einem für den Breitengrad und einem für Längengrad.)
Antworten
Perl 5 ( -ap -MList::Util+sum), 136 Bytes
@a=([-90,90],[-180,180]);map{$y=0;$a[--$|][$,=$F[$|]<($m=.5*sum@{$a[$|]})]=$m,$y+=$y+!$,for 0..4;$\.=(0..9,grep!/[ilo]/,b..z)[$y]}0..7}{
Probieren Sie es online aus!
Überprüfen Sie alle Testfälle
Python 3 , 250 Bytes
lambda b,a:(lambda l:"".join("0123456789bcdefghjkmnpqrstuvwxyz"[int("".join(map(str,l[i*5:][:5])),2)]for i in range(8)))(sum(zip(f(a,180,-180),f(b,90,-90)),()))
f=lambda a,u,l,p=20:p and([1]+f(a,u,(u+l)/2,p-1)if u+l<a*2else[0]+f(a,(u+l)/2,l,p-1))or[]
Probieren Sie es online aus!
Ich denke, benannte Funktionen zu verwenden wäre wahrscheinlich besser ... sowieso. Ich habe noch keine Zeit, dies weiter zu spielen, also poste es einfach zuerst hier.
05AB1E , 64 63 61 42 41 Bytes
90x‚R/>19o*î<Dd*b20jð0:SÅ=5ôJCžhA«„ŠÙaмsè
-19 Bytes durch Portieren von @Neils Charcoal-Antwort , also stellen Sie sicher, dass Sie ihn ebenfalls positiv bewerten!
-1 Byte, indem die Eingabe in umgekehrter Reihenfolge vorgenommen wird.
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Original 64 63 61 60 Bytes Antwort:
εd©ˆ¾ƵΔN>÷‚19FÐÆÄ;UÅmyÄ‹®Qˆε¯θ®QNÊiXNi-ë+]¯Å=5ôJCžhA«„ŠÙaмsè
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Beide nehmen die Eingabe als [longitude, latitude]und Ausgabe als Liste von Zeichen.
Erläuterung:
90 # Push 90
x # Double it to 180 (without popping)
‚ # Pair them together: [90,180]
R # Reverse it: [180,90]
/ # Divide the (implicit) input-pair by these
> # Increase both by 1
19o # Push 2^19: 524288
* # Multiply both decimals by this 524288
î # Ceil both to an integer
< # Then decrease them by 1
# (ceil + decrement cannot be floor, if they already are integers)
Dd # Create a copy, and check if it's >=0 (1 if >=0; 0 if <0)
* # Multiply this to the pair (-1 becomes 0, else it stays the same)
b # Convert both integers to a binary string
20j # Pad them with leading spaces up to a length of 20
ð0: # Replace all spaces with 0s
S # Convert it to a flattened list of digits
Å= # Shuffle this list ([a,b,c,d,e,f] → [a,d,b,e,c,f])
5ô # Split this into parts of size 5
J # Join each inner list together to a string
C # Convert each binary string to a base-10 integer
žh # Push builtin "0123456789"
A« # Append the lowercase alphabet
„ŠÙa # Push dictionary string "oila"
м # Remove those characters from the string
s # Swap to get the list of integers at the top again
è # And (0-based) index them into the string
# (after which the list of characters is output implicitly
ε # Map both values in the pair to:
d # Pop and check if it's non-negative (1 if >=0; 0 if <0)
© # Store this in variable `®` (without popping)
ˆ # And pop and add it to the global_array
¾ # Push 0
ƵΔ # Push compressed 180
N # Push the 0-based map-index
> # Increase it by 1 to make it 1-based
÷ # Divide the 180 by this (longitude=180; latitude=90)
‚ # Pair it together with the 0
19F # Loop 19 times:
Ð # Triplicate the current pair
ÆÄ # Pop one, and get the absolute difference
; # Halve this
U # Pop and store this halved difference in variable `X`
Åm # Pop another copy, and take its average
‹ # Check that it's smaller than
yÄ # the absolute value of the current map value
# (1 if truthy; 0 if falsey)
®Q # Check if this is equal to `®`
# (this will invert the boolean for negative values)
ˆ # Pop and add this to the global_array
ε # Map over the third pair:
¯θ # Push the last value of the global_array
®Q # Check it this is equal to `®`
# (to invert for negative values again)
NÊi # If this is NOT equal to the 0-based inner map-index:
X # Push variable `X`
Ni # If the 0-based inner map-index is 1:
- # Subtract `X` from the current value we're mapping over
ë # Else:
+ # Add it instead
] # Close both if-statements, both maps, and the loop
¯ # Push the global_array
Å=5ôJCžhA«„ŠÙaмsè # Same as above
Sehen Sie diese 05AB1E Spitze von mir (Abschnitte Wie das Wörterbuch benutzen? Und Wie große natürliche Zahlen zu komprimieren? ) Zu verstehen , warum „ŠÙaist "oila"und ƵΔist 180.
Holzkohle , 65 Bytes
Ｆ²⊞υ⌈×Ｘ²¦¹⁹⊕∕Ｎ×⁹⁰⊕ιＵＭυ◧⎇‹ι²ω⍘⊖ι !²⁰⭆⪪⭆²⁰⭆⮌υ§λι⁵§⁺⭆χλΦβ¬№ailoλ⍘ι !
Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Erläuterung:
Ｆ²⊞υ⌈×Ｘ²¦¹⁹⊕∕Ｎ×⁹⁰⊕ι
Geben Sie beide Zahlen ein. Teilen Sie die erste durch 90 und die zweite durch 180, erhöhen Sie dann beide, multiplizieren Sie sie mit 524288 und runden Sie dann auf.
ＵＭυ◧⎇‹ι²ω⍘⊖ι !²⁰
Wenn das Ergebnis größer als 2 ist, dekrementieren und konvertieren Sie es mit einem benutzerdefinierten Ziffernsatz auf Basis 2 und füllen Sie es auf 20 "Ziffern" auf. (Dies funktioniert nicht für 0, da es negativ werden würde, und es funktioniert nicht für 1 aufgrund eines Fehlers in der Version von Charcoal auf TIO.)
⭆⪪⭆²⁰⭆⮌υ§λι⁵§⁺⭆χλΦβ¬№ailoλ⍘ι !
Mische die Bits, teile sie in Fünfergruppen auf, dekodiere jede Gruppe von Basis 2 mit demselben Ziffernsatz und suche dann die Ziffer in einer Tabelle mit Ziffern und Buchstaben ohne ailo.
R , 149 147 144 128 Bytes
Bearbeiten: -16 Bytes dank Giuseppe, indem Code-effizientere Matrixoperationen verwendet werden ( rbind, %*%)
function(l,m,d=function(x)((x+180)*5825.422)%/%2^(20:1)%%2)c(0:9,letters[-c(1,3:5*3)])[1+2^(4:0)%*%matrix(rbind(d(m),d(l*2)),5)]
Probieren Sie es online aus!
Gibt den Vektor der Zeichen aus.
Wie? (vor Giuseppes Golf)
geohash=
function(l,m, # l=latitude, m=longitude
d=function(x) # d=helper function to calculate bits from lat or long
((x+180)*5825.422) # scale by 5825.422 == 2^20/180
%/%2^(20:1)%%2 # convert to binary bits
)
c(0:9, # encode using digits 0..9, joined to
letters[-c(1,9,12,15)]) # letters except a,i,l,o
[1+ # 1-based indexing
colSums( # sums of each column of matrix
# columns represent each 5-bit character
matrix( ... ,5,8) # format numbers into matrix with 5 rows & 8 columns
t( # using transpose of
matrix( # matrix of
c(d(m),d(l*2)),,2)# longitude bits, latitude bits x2, in rows
)
*2^(4:0))] # times powers of 2 to convert sums to numbers
Python 3 , 174 Bytes
f=lambda a,b,c='',n=1,x=0,y=0,z=(-45,45):n<7**7and f(a,b,c+'%i%i'%(b>y,a>x),n*2,x+z[a>x]/n,y+z[b>y]/n*2)or c and'0123456789bcdefghjkmnpqrstuvwxyz'[int(c[:5],2)]+f(*z,c[5:],n)
Probieren Sie es online aus!
Verfolgt die Durchschnittswerte xsowie den yLängen- und Breitengrad. Die Funktion erhöht oder verringert diese Werte in Schritten von 45/nund 90/n, wobei ngleich ist 2**(current cycle). Die Vergleiche werden in der Bitfolge gespeichert c. Dies dauert 20 Zyklen, bis es nüberschritten wird 2**19, was durch angenähert wird 7**7. Wenn dieser Wert erreicht ist, wird das cin das Endergebnis konvertiert .