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:
  • diferentes bases além da base32: base4h, base8h ou base16h.
  • diferentes alfabetos além do clássico: padrões como NVU ou JS, e localizados para o idioma (ex. russo).
• 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 em algumas aplicações eletrônicas, mas a proposta de geocódigo de Morton não era muito prática e legível, 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 (hoje semi-abandonado) http://geohash.org, que permite aos usuários converter coordenadas geográficas em URLs curtos que identificam exclusivamente as posições na Terra. A mais importante inovação em seguida foi a versão Geohash-integer de 2014, que faz uso da sua versão binária e ampliada para 64 bits.

S2 Geometry, usando curva de Hilbert e projeção plana.

Algumas variações foram desenvolvidas, incluindo o link curto do OpenStreetMap em 2009 (usando base64url em vez de base32ghs), o Geohash-integer de 2014, e outros. Em uma linha de desenvolvimento bem diferente, tendo o geocódigo como subproduto, em 2017 a Google tornou público no Github o seu software S2 Geometry. O S2 implementa um geocódigo baseado na curva de Hilbert ao invés da curva de Morton, e faz uso de uma projeção plana para reduzir as distorções de latitude da grade LatLong.

Na AddressForAll, em 2018, foi desenvolvida a proposta do GGeohash, registrada para o domínio público em [KraEtAll2018]. A proposta GGeohash unifica de forma coerente as variantes do Geohash e as variantes do S2. 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 geométrica

No contexto do padrão DNGS o importante é que as células de todos os níveis hierárquicos sejam quadriláteros: quadrados, losangos, retângulos ou paralelogramos. Portanto, apesar de não ser o ideal, é possível construir níveis intermediários entre grades quadradas, utilizando-se retângulos. Numa típica grade quadrada, considerando-se a sua simetria, a grade intermediária é uma degeneração.

É possível construir a grade retangular (degenerada) a partir da grade quadrada (simétrica) mesclando-se células vizinhas e indexando a grade retangular resultante pela função $j=\left\lfloor {\frac {i}{2}}\right\rfloor$. As células C_j da grade resultante são obtidas da união de células da grade de nível superior, F_i, ou seja, $C_{j}=F_{j\times 2}\cup F_{j\times 2+1}$. Ilustrando com os dois tipos de curva de preenchimento:

A Curva de Morton acima, e a ilustração de como obter a grade de 32 células retangulares a partir da grade de 64 células quadradas.

A Curva de Hilbert acima, e a ilustração de como obter a grade de 32 células retangulares a partir da grade de 64 células quadradas. Repare que a grade deixa de ser regular e passa a ser uma grade aperiódica de dominós.

Ilustramos com decimais para permitir o entendimento dos cálculos. A propriedade mais importante do GGeohash para humanos é que ele preserva a hierarquia espacial nos prefixos do código. Para demonstrar isso precisamos visualizar com geocódigos hierárquicos, por exemplo com a base4h:

Geometria e geocódigo consistentes

Tendo a base16h como principal notação dentro das convenções adotadas, ela garante a consistência entre geometria e geocódigo, principalmente na expressão da hierarquia. A compatibilidade com os números hexadecimais tradicionais também foi ajustada de modo a bater com os casos de geometria simétrica (quadrados).

Características da grade em base16h:

• Níveis inteiros (L0, L1, L2 etc.) são quadrados.
• Níveis meio (L½, L1½, L2½ etc.) são retângulos (grades degeneradas).
• Níveis inteiros pares são hexadecimais, simbolicamente iguais aos hexadecimais tradicionais (exceto por diferenciar zeros a esquerda).

Na base32 a principal característica é a alternância entre quadrados e retângulos. Pelas convenções adotadas no padrão DNGS a grade base32 de 1 metro sempre será quadrada.

Solução multifinalitária

As principais aplicações para um sistema de geocódigos, associado a múltiplas grades, são:

1. Logísticas: código postal e geocódigos similares para apoio simplificar a localização de pontos de interesse, endereços, e quadrantes (grade tradicional de navegação).
2. Computacionais: representação e conversão de geo-objetos em geo-campos e vice versa, indexação (quadtree e similares em bancos de dados espaciais)
3. Métricas e Cartográficas: oferecer identificadores zonais padronizados e com representação visual compacta. Além disso as células da grade padronizada permitem a interação humana com sistemas de informação.

O requisito mais importante, que garante o uso do mesmo sistema de grades nas diversas aplicações, é a hierarquia. Sistemas não-hierarquicos, ou com limtações nas operações hierárquicas, perdem a utilidade nas aplicações mais sensíveis.

Em seguida, outro requisito importante é a visualização dos identificadores de células: os geocódigos não podem ser longos, e devem tirar proveito da hierarquia para serem reduzidos pelo contexto.

Como resultado da imposição destes requisitos, muitos sistemas de grades precisam ser descartados:

• sistemas baseados em células hexagonais não podem ser usados em coberturas nem em geocódigos consistentes
• sistemas baseados em células triangulares sao menos eficientes do que os quadrados ...
• sistemas sem projeção igual-area nao satisfazem nem à álgebra de geocampos/geoobjetos, nem aos requisitos métricos para a comparação das informações contidas nas células de diferentes locais.

A conclusão é que apenas sistemas hierárquicos de grades quadriláteras regulares é seriam elejíveis para o uso multifinalitário.