Generalized Geohash/pt

Generalização do algoritmo Geohash para geocódigos, GGeohash (do inglês Generalized Geohash). Vantagens:

• permite representações interna (no computador) e humana (como geocódigo) totalmente compatíveis e consistentes.
• permite adequação da representação humana à sua cultura ou preferências do usuário.
• permite escolha entre 2 curvas de preenchimento (Morton e Hilbert).

Opções podem ser visualizadas em https://osm-codes.github.io/Sfc4q/

Uma das inovações do GGeohash foi a introdução do conceito de níveis-meio (L½), que se originam da união geométrica de células consecutivas do nível inteiro, permitindo formalizar melhor o Geohash clássico e viabilizando a curva de Hilbert. Nos níveis-meio as curvas Morton e Hilbert são degeneradas.

Entre as várias opções, uma delas corresponde ao "Geohash clássico". As opções surgem da combinação dos seguintes parâmetros:

Opção	Alternativas	Descrição
Número de bits por dígito	1,2,3,4 ou 5	Apesar da geometria da célula ser subdividida sempre em 4 (2 bits), a representação pode determinar a compatibilidade da base com a geometria.
Base e alfabeto para humanos	base4h, 8h e 16h ou base32	Base e alfabeto determinam a notação posicional. Geocódigo para humanos, mantendo a compatibilidade com número de bits. As bases hierárquicas (h) são compatíveis com 1 a 4 bits, a base32 apenas com 5 bits.
Curva de preenchimento	Morton ou Hilbert	Define como será a indexação e ordem da segunda.
...

História

A parte central do algoritmo Geohash e a primeira iniciativa para uma solução semelhante foi documentada em um relatório da G.M. Morton em 1966. O trabalho de Morton foi usado para implementações eficientes da curva de ordem Z, como na versão Geohash-integer de 2014, que faz uso da sua versão binária e ampliada para 64 bits. Ainda assim, a proposta de geocódigo de Morton não era legível por humanos, e foi esquecida por mais de três décadas.

G. Niemeyer, no final dos anos 2000, desconhecendo a obra de Morton, a reinventou, acrescentando o uso da representação base32. Em fevereiro de 2008, junto com o anúncio do sistema, Niemeyer lançou o site http://geohash.org, que permite aos usuários converter coordenadas geográficas em URLs curtos que identificam exclusivamente as posições na Terra.
Muitas variações foram desenvolvidas, incluindo o link curto do OpenStreetMap em 2009 (usando base64url em vez de base32ghs), o Geohash de 64 bits em 2014, e outros.

Na AddressForAll, em 2018, foi desenvolvida a proposta do GGeohash, registrada para o domínio público em [KraEtAll2018]. Em seguida, em 2019, uma fundamentação mais ampla foi adicionada através dos Natural Codes, com [KraEtAll2019].

Typical and main usages

...

Descrição técnica

...

Representação textual

Alfabetos e convenções da notação. Lista completa de IDs com respectivos alfabetos-padrão para conversão de base, para as “bases potência de 2”. O identificador é a concatenação da palavra “base” com o valor da base e o rótulo (label) do alfabeto. O número de bits por dígito é o log₂ da base. No alfabeto foram destacados os nhDigits (non-hierarchical digits) conforme notação Natural Code.

base	label	ID	bits	alphabet (depois do espaço os nhDigits)	Reference standard
2	js*	base2js	1	01	ECMA-262
4	js*	base4js	2	0123	ECMA-262
4	h	base4h	2	0123 GQ	ECMA + nhDigits alphabet
8	js*	base8js	3	01234567	ECMA-262
8	h	base8h	3	01234567 GQ HMRV	ECMA + nhDigits alphabet
16	js*	base16js	4	0123456789abcdef	ECMA-262 and RFC 4648/sec8
16	h	base16h	4	0123456789abcdef GQ HMRV JKNPSTZY	ECMA + nhDigits alphabet
32	hex*	base32hex	5	0123456789abcdefghijklmnopqrstuv	ECMA-262 and RFC 4648/sec7
32	ghs	base32ghs	5	0123456789bcdefghjkmnpqrstuvwxyz	Geohash
32	nvu	base32nvu	5	0123456789BCDFGHJKLMNPQRSTUVWXYZ	No-Vowels except U (near non-syllabic)
32	rfc	base32rfc	5	ABCDEFGHIJKLMNOPQRSTUVWXYZ234567	RFC 4648/sec6
64	url*	base64url	6	ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_	RFC 4648/sec5
64	rfc	base64rfc	6	ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/	RFC 4648/sec4
(*) default base. For example base32 is interpreted by default as base32hex.     All base32 here are using with leading zeros, they are valid instances of “restricted hiearchy”, base32rh.

Representação geometrica

A geometria GGeohash permite uma representação espacial mista:

• Geohashes clássicos com 2, 4, 6, ... e dígitos (dígitos pares) são representados pela curva de ordem Z em uma "grade regular" onde o par decodificado (latitude, longitude) tem incerteza uniforme, válida como Geo URI.
• Geohashes clássicos com 1, 3, 5, ... d dígitos (dígitos ímpares) são representados por "curva de ordem И". Latitude e longitude do par decodificado tem incerteza diferente (a longitude é truncada).

It is possible to build the "И-order curve" from the Z-order curve by merging neighboring cells and indexing the resulting rectangular grid by the function $j=\left\lfloor {\frac {i}{2}}\right\rfloor$.

The illustration shows how to obtain the grid of 32 rectangular cells from the grid of 64 square cells.

The most important property of Geohash for humans is that it preserves spatial hierarchy in the code prefixes.
For example, in the "1 Geohash digit grid" illustration of 32 rectangles, above, the spatial region of the code e (rectangle of greyish blue circle at position 4,3) is preserved with prefix e in the "2 digit grid" of 1024 rectangles (scale showing em and greyish green to blue circles at grid).