Geohash-36¹ is een techniek waarmee geografische locaties kunnen gecodeerd worden als een reeks letters en cijfers. Zo kan de locatie van The Shard² wolkenkrabber in Londen (Engeland) op coördinaat (-0.086667, 51.504444) aangeduid worden met geohash-36 code bdrdC26BqH en de locatie van het Vrijheidsbeeld³ in New York (Verenigde Staten van Amerika) op coördinaat (-74.044445, 40.689168) met geohash-36 code 9LVB4BH89g.

Geohashes hebben de eigenschap dat je hun nauwkeurigheid kan variëren en dat je op het einde tekens kan verwijderen om de code korter te maken (waardoor er geleidelijk ook nauwkeurigheid verloren gaat). Zo kan de locatie van The Shard ook aangeduid worden met geohash-36 code bdrdC26B zonder veel aan nauwkeurigheid in te boeten. Door het gradueel inboeten aan nauwkeurigheid zullen locaties die bij elkaar in de buurt liggen vaak (maar niet altijd) met dezelfde tekens beginnen. Hoe meer gemeenschappelijk tekens vooraan, hoe dichter twee locaties bij elkaar in de buurt liggen.

Geohash-36 verdeelt de wereldkaart in 36 gelijke gebieden volgens een $$6 \times 6$$ rooster. Aan elk gebied wordt een uniek teken uit een alfabet van 36 letters en cijfers toegekend door de gebieden van west naar oost (links naar rechts) en van noord naar zuid (boven naar onder) af te lopen. Hoofdletters en kleine letters worden als verschillende tekens aanzien. Standaard maakt geohash-36 gebruik van het alfabet

23456789bBCdDFgGhHjJKlLMnNPqQrRtTVWX

Deze tekens zijn gekozen zodat er geen klinkers gebruikt worden, geen cijfers die op klinkers lijken, geen tekens die tot verwarring kunnen leiden, en geen kleine letters die sterk op hun hoofdlettervariant lijken in de gangbare lettertypes. Door geen klinkers te gebruiken kunnen geohash-36 codes geen bestaande woorden vormen, wat anders ook weer tot verwarring zou kunnen leiden.

The Shard wolkenkrabber in Londen (Engeland) — in bovenstaande kaart aangeduid met een rode markering — ligt bijvoorbeeld in het gebied dat aangeduid wordt met de letter b. Dat is het eerste teken van de geohash-36 code. Om de locatie nauwkeuriger aan te duiden, wordt gebied b op dezelfde manier terug onderverdeeld in 36 deelgebieden (onderstaande kaart). Daarbij zien we dat Londen nu in het deelgebied ligt dat aangeduid wordt met de letter d, die het tweede teken vormt van de geohash-36 code. Door het huidige gebied telkens weer in te delen in 36 deelgebieden, kunnen we steeds verder inzoomen en de locatie nauwkeuriger voorstellen.

Optioneel kan een geohash-36 code een checksum⁴ meekrijgen die voorgesteld wordt als een kleine letter achteraan de code en die van de eigenlijke code gescheiden wordt door een koppelteken (-). Aan de hand van de checksum kan gecontroleerd worden of er geen foutieve of omgewisselde tekens zijn. De checksum wordt berekend als modulo 26 van de som van de positie van elk teken in de geohash-36 code vermenigvuldigd met de positie van het teken in het alfabet. Hierbij worden posities in geohash-36 codes van rechts naar links genummerd vanaf 1, en worden posities in het alfabet van links naar rechts genummerd vanaf 0. Zo worden de posities van de tekens in het standaard alfabet voor geohash-36 op de volgende manier genummerd:

De checksum van geohash-36 code bdrdC26BqH-m met checksum m wordt dan berekend als \[ \left( 10 \times 8 + 9 \times 11 + 8 \times 29 + 7 \times 11 + 6 \times 10 + 5 \times 0 + 4 \times 4 + 3 \times 9 + 2 \times 27 + 1 \times 17 \right)\!\!\!\!\mod{26 }= 12 \] met letter m op positie 12 in het klassieke alfabet a–z, waarvan de posities van links naar rechts genummerd worden vanaf 0.

Opgave

Zet een gegeven geohash-36 code om naar coördinaat $$(\lambda, \varphi)$$ met $$\lambda, \varphi \in \mathbb{R}$$. Hierbij geldt dat lengtegraad $$\lambda \in [-180, 180]$$ en breedtegraad $$\varphi \in [-90, 90]$$. Het algoritme dat je hiervoor moet gebruiken werd geschetst in de inleiding, maar we geven nog meer gedetailleerd aan hoe je telkens met het volgende teken uit de geohash-36 code kunt inzoomen naar een nauwkeuriger deelgebied.

Stel dat we de coördinaat reeds gelocaliseerd hebben binnen een rechthoekig gebied met lengtegraden in het interval $$[l_{\lambda}, u_{\lambda}]$$ en breedtegraden in het interval $$[l_{\varphi}, u_{\varphi}]$$. We delen dit gebied verder op in 36 gelijke deelgebieden volgens een $$6 \times 6$$ rooster en nummeren de rijen van het rooster van onder naar boven en de kolommen van links naar rechts, telkens vanaf 0.

Als het volgende teken correspondeert met het deelgebied in rij $$r$$ en kolom $$k$$, dan liggen de lengtegraden van dat deelgebied in het interval $$[l'_{\lambda}, u'_{\lambda}]$$ en de breedtegraden in het interval $$[l'_{\varphi}, u'_{\varphi}]$$, waarbij de onder- en bovengrenzen van de intervallen op de volgende manier berekend worden:

\[ \begin{align} l'_{\lambda} &= l_{\lambda} + k \times \frac{u_{\lambda} - l_{\lambda}}{6} \\ u'_{\lambda} &= l_{\lambda} + (k + 1) \times \frac{u_{\lambda} - l_{\lambda}}{6} \\ l'_{\varphi} &= l_{\varphi} + r \times \frac{u_{\varphi} - l_{\varphi}}{6} \\ u'_{\varphi} &= l_{\varphi} + (r + 1) \times \frac{u_{\varphi} - l_{\varphi}}{6} \end{align} \]

Onderstaande tabel toont hoe de opeenvolgende deelgebieden kunnen berekend worden voor geohash-36 code bdrdC26BqH. Kolom $$\lambda$$ toont de schatting van de lengtegraad als het middelpunt van het interval $$[l'_{\lambda}, u'_{\lambda}]$$ en kolom $$\varphi$$ toont de schatting van de breedtegraad als het middelpunt van het interval $$[l'_{\varphi}, u'_{\varphi}]$$. Elk volgend teken van de geohash-36 code maakt deze schatting nauwkeuriger.

Definieer een klasse Geohash36 die kan gebruikt worden om geohash-36 codes voor te stellen. Bij het instantiëren van Geohash36-objecten moet een geohash-36 code (str) doorgegeven worden, die eventueel ook een checksum kan bevatten. Bijkomend kan er aan de optionele parameter alfabet ook een string (str) doorgegeven worden die het alfabet bevat dat door de geohash-36 code gebruikt wordt. Indien er niet expliciet een waarde wordt doorgegeven aan de parameter alfabet, dan maakt de geohash-36 code gebruik van het standaard alfabet dat we in de inleiding gegeven hebben.

Er moet expliciet gecontroleerd worden dat het gegeven alfabet een string (str) is die bestaat uit 36 verschillende letters en cijfers. Als dat niet het geval is dan moet een AssertionError opgeworpen worden met de boodschap ongeldig alfabet.

Er moet ook expliciet gecontroleerd worden dat de gegeven geohash-36 code een string (str) is waarvan alle karakters behoren tot het gegeven alfabet. Als de code een checksum bevat, dan moet deze checksum ook geldig zijn. Als dat niet het geval is dan moet een AssertionError opgeworpen worden met de boodschap ongeldige code.

Als er een Geohash36-object doorgegeven wordt aan de ingebouwde functies repr en str, dan moeten beide functies een stringvoorstelling van de geohash-36 code met checksum teruggeven. Voor de functie repr is de stringvoorstelling een Python expressie die een nieuw Geohash36-object aanmaakt met dezelfde toestand als die van het object dat als argument werd doorgegeven. Enkel wanneer het alfabet van de geohash-36 code verschilt van het standaard alfabet moet daarbij expliciet een waarde doorgegeven worden aan de parameter alfabet, die ook expliciet moet benoemd worden. Voorts moet de klasse Geohash36 minstens de volgende methoden ondersteunen:

• Een methode checksum waaraan geen argumenten moeten doorgegeven worden. De methode moet de checksum (str) van de geohash-36 code teruggeven.

• Een methode positie waaraan een teken $$t$$ (str) moet doorgegeven worden. De functie moet de positie teruggeven van het deelgebied in het $$6 \times 6$$ rooster dat wordt aangeduid met het teken $$t$$. Die positie moet voorgesteld worden als een tuple $$(r, k)$$ (tuple), waarbij $$r$$ (int) en $$k$$ (int) resp. het rij- en kolomnummer van het deelgebied in het rooster aangeven. Als het teken $$t$$ geen deelgebied in het rooster aanduidt, dan moet een AssertionError opgeworpen worden met de boodschap ongeldig teken.

• Een methode lengtegraad waaraan geen argumenten moeten doorgegeven worden. De methode moet het interval (tuple) teruggeven met de lengtegraden $$l'_{\lambda}$$ (float) en $$u'_{\lambda}$$ (float) van het deelgebied dat wordt aangeduid door de geohash-36 code.

• Een methode breedtegraad waaraan geen argumenten moeten doorgegeven worden. De methode moet het interval (tuple) teruggeven met de breedtegraden $$l'_{\varphi}$$ (float) en $$u'_{\varphi}$$ (float) van het deelgebied dat wordt aangeduid door de geohash-36 code.

• Een methode coordinaat waaraan geen argumenten moeten doorgegeven worden. De methode moet een tuple (tuple) teruggeven met de schatting van de lengtegraad $$\lambda$$ (float) en de breedtegraad $$\varphi$$ (float) voor de geohash-36 code, waarbij de lengte- en breedtegraad geschat worden als het middelpunt van het deelgebied dat wordt aangeduid door de geohash-36 code.

Voorbeeld

>>> geohash = Geohash36('bdrdC26BqH')    # The Shard (Londen, Engeland)
>>> geohash.checksum()
'm'
>>> geohash
Geohash36('bdrdC26BqH-m')
>>> print(geohash)
bdrdC26BqH-m
>>> geohash.positie('b')
(4, 2)
>>> geohash.positie('d')
(4, 5)
>>> geohash.positie('r')
(1, 5)
>>> geohash.positie('c')
Traceback (most recent call last):
AssertionError: ongeldig teken
>>> geohash.lengtegraad()
(-0.08666861949397955, -0.0866626657521719)
>>> geohash.breedtegraad()
(51.504442086762694, 51.5044450636336)
>>> geohash.coordinaat()
(-0.08666564262307572, 51.504443575198145)

>>> geohash = Geohash36('9LVB4BH89g-m')  # Vrijheidsbeeld (New York, VSA)
>>> geohash.checksum()
'm'
>>> geohash
Geohash36('9LVB4BH89g-m')
>>> print(geohash)
9LVB4BH89g-m
>>> geohash.coordinaat()
(-74.0444452779683, 40.68916794076742)

>>> geohash = Geohash36('EAQK46y', alfabet='i8jC4TsPkQplz6AZE5WB3R2oKymUrOc0t7MG')
>>> geohash.checksum()
'k'
>>> geohash
Geohash36('EAQK46y-k', alfabet='i8jC4TsPkQplz6AZE5WB3R2oKymUrOc0t7MG')
>>> print(geohash)
EAQK46y-k
>>> geohash.coordinaat()
(85.19483024691357, 18.600501543209877)

>>> Geohash36('bdrdc26BqH')     # kleine letter c niet in alfabet
Traceback (most recent call last):
AssertionError: ongeldige code
>>> Geohash36('bdrdC26BqH-a')   # ongeldige checksum
Traceback (most recent call last):
AssertionError: ongeldige code
>>> geohash = Geohash36('EAQK46y', alfabet='ABCDE')
Traceback (most recent call last):
AssertionError: ongeldig alfabet