Generalized Geohash/pt

Generalização do algoritmo Geohash para geocódigos, GGeohash (do inglês Generalized Geohash). Definição original em [KraEtAll2018]. Vantagens sobre o Geohash:

oferece representações interna (para o computador) e textual (como geocódigo para humanos) totalmente compatíveis e consistentes;
permite adequação da representação textual às necessidades do usuário:
- diferentes bases além da base32 clássica: base4h, base8h ou base16h.
- diferentes alfabetos além do clássico: padrões como NVU ou JS, e adaptações para o idioma do usuário (ex. russo).
permite escolha entre 2 curvas de preenchimento (Morton e Hilbert).

Caracterização

As diversas opções podem ser visualizadas em Sfc4q (Space-filling curves of refinement ratio 4 quadrilateral). Abaixo são ilustrados o Geohash clássico (Morton) e a sua generalização em curva de Hilbert.

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 formação de geocódigos eficientes com a curva de Hilbert. Nos níveis-meio as curvas Morton e Hilbert são degeneradas: a rigor formam outro fractal.

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 ordenação. A escolha determina o custo de CPU (Hilbert tem maior custo), regularidade ou não no alinhamentos das células em curvas degeneradas (Hilbert é irregular), e possibilidade de uso de intervalos (só Hilbert permite).
Projeção igual-área	Com ou sem projeção, aproximada ou exata, global ou local.	Devido ao escopo multifinalitário, principalmente com relação às aplicações no Censo populacional e (secundariamente) de estimativa de área de lote, a projeção se faz necessária. O padrão DGGS mostra outra dezena de aplicações.

Hierarquia dígito-a-dígito no geocódigo

Geocódigos do padrão GGeohash são hierárquicos. Por exemplo com Geohash clássico:

6 ⊃ 6g ⊃ 6gy ⊃ 6gyc ⊃ 6gyce ⊃ 6gycex

No caso de base-h há uma quebra da hierarquia no último dígito enquanto o nível não é múltiplo da base. Por exemplo a base16h só é hierárquica a cada 4 bits, e a base4h a cada 2 bits. Exemplificando com a base4h:

2 ⊃ 2G ⊃ 21 ⊃ 21Q ⊃ 213 ⊃ 213Q ⊃ 2132
2 ⊃ 21 ⊃ 213 ⊃ 2132

A hierarquia e a quasi-hierarquia estão simultaneamente presentes na Base-H, diferente da quasi-hierarquia de outros padrões, como OLC, onde a alternativa (subconjunto) de hierarquia dígito a dígito não existe.

Quasi-hierarquia em outros padrões

O OLC usa de certa forma a curva de Morton, mas mesmo seu prefixo não é considerado GGeohash por expressar a curva apenas nos dígitos pares:

58 ⊃ 588M ⊃ 588MC8 ⊃ 588MC8QV

O OLC faz uso de uma subgrade, destacada pelo separador +, que, esta sim, é hierárquica a cada dígito, mas não cumpre mais a curva de Morton:

588MC8QV ⊃ 588MC8QV+C ⊃ 588MC8QV+CJ

Outro geocódigo, o map-code base4 usa Morton Base4 com alfabeto ABCD porém o prefixo do código é um par decimal representando quadrante de latitude e longitude inteiros. Exemplo:

2627 ⊃ 2627 A ⊃ 2627 AC ⊃ 2627 ACC
2627 , 2628, 2527, ...

Se entendermos os prefixos decimais como células de cobertura (~9999 células), fica caracterizado um GGeohash.

Problemas que soluciona

Contém resumo de DNGS/Geocódigo#Desafios do bom geocódigo.

... colocando os problemas P na forma de perguntas:

P: Quais os problemas DNGS? e porque o GGeohash é orientado à sua solução?
- R: Um dos problemas citados é o problema do triângulo e o problema do hexagono, ambos comprometendo a multifinalidade, deixando como única opção a célula quadrilátera. O GGeohash é uma generalização das grades hierárquicas com célula quadrilátera, sendo portanto a solução mais geral do problema.

P: Qual índice usar na indexação espacial de pontos?
- R: Qualquer curva de preenchimento permite reunir latitude e longitude em um só número, dito "índice da curva de preenchimento". Ela vai possuir dependência geométrica com o formato da célula e sua taxa de refinamento, r. Por exemplo H3 Uber é hexagonal com taxa r=7, S2 Geometry é quadrilátero com r=4, Geohash é quadrilátero com r=32.
- R: Aquele que satisfazer as (múltiplas) aplicações eleitas pela nação.

P: Qual base usar na representação posicional do índice, ou seja, como geocódigo?
- R: Prova matemática de que bons geocódigos emergem das potências de 2 na representação interna (outros números primos seriam menos compactos)
- R: Restrição de base como potência da taxa de refinamento, para garantir representação hierárquica (de cada nível do refinamento).
- R: Prova matemática de que Triângulos não são boa solução para aplicações logísticas (e outras)
- R: Prova matemática de que Hexagonos não oferecem possibilidade de cobertura multi-resolução

...

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

A principal vantagem da curva de Morton é a simplicidade e rapidez com que se pode realizar o encode/decode das coordenadas XY.

As curvas de preenchimento garantem a transformação consistente de 2 coordenadas em uma. Para mantermos o máximo de níveis hierárquicos devemos focar nas curvas com menor fator de refinamento possível, que no caso de quadrado é o fator 4. Podemos chegar no fator 2 mas ele "degenera" a forma quadrada das células, transformando-as em retângulos: a solução de "usar as duas" é garantir que o refinamento 4 possa ser degenerado em refinamento 2, resultando em retângulos (dominós).

Nesta condição, conforme discussão de 2020, existem apenas 3 possibilidades, sendo que uma delas pode ser descartada, por não ser "dominó-compatível":

Estas duas são bem conhecidas, pelo nome dos seus descobridores, que primeiramente as descreveram matematicamente:

Curva de Morton: mais rápida de se calcular e com versão degenerada regular periódica.
Curva de Hilbert: mais eficiente (sem descontinuidades) porém com versão degenerada aperiódica.

Representação textual

Resumo de Código natural/Notação posicional.

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.

Nota. É importante lembrar também que existe uma relação entre o seu nível hierárquico L da célula e o seu tamanho de lado S (side size). Por imposição do padrão DNGS temos

S_{L}=2^{Lmax-L}

. No caso do Brasil Lmax=20, no caso de Camarões Lmax=18.
A fórmula de S funciona também para níveis-meio, por exemplo L=1.5. Como o "tamanho do lado genérico S de um retângulo" é a raiz quadrada da área do retângulo; e pela construção geométrica dos níveis-meio, cujas células, de áreas iguais, são a união de 2 células do próximo nível inteiro, temos:

S_{Lhalf}={\sqrt {2\cdot {Area_{\lceil Lhalf\rceil }}}}={\sqrt {2}}\cdot {\sqrt {{S_{\lceil Lhalf\rceil }}^{2}}}=2^{Lmax-\lceil Lhalf\rceil +0.5}

onde

Lhalf=\forall L|L=\lceil L\rceil -0.5

.

Ilustramos com índices i e j decimais para permitir o entendimento dos cálculos. Na prática o identificador da célula é apresentado ao ser humano com baseH. 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.

Intervalos de geocódigos

Comportamento do intervalo 7 a 9. Na Curva de Morton há descontinuidade.

Intervalos 4-9 (verde), 28-34 (lilás) e 55-58 (azul), mostrando o crescente de interrupções na Curva de Morton conforme se avança no tamanho da grade. Os intervalos são sempre contíguos em Hilbert.

Em diversas aplicações, tais como definição de setores territoriais abstratos na gestão pública, podem também fazer uso de intervalos. Em Computação, o balanceamento de cargas entre partições de disco requer a escolha de geocódigos de diferentes grades da hierarquia, mas uma segunda estratégia é a escolha de intervalos de geocódigos de uma mesma grade.

Não havendo questões de performance da indexação ou regularidade da geometria na grade degenerada, a demanda ou não por intervalos contínuos determina qual curva utilizar, Morton ou Hilbert.

Resumindo: intervalos podem ser úteis para definir zonas abstratas (não-políticas) coerentes com a indexação e ao mesmo tempo uma grandeza para estabelecer partições balanceadas.

Solução multifinalitária

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

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).
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)
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.

Ver também

Referências

(Pendente revisar e usar Ref-list)

Fundamentação e tecnologias similares:

Implementa células por curva de Morton e oferece benchmarks de consulta https://doi.org/10.1016/j.heliyon.2017.e00332 "A multi-resolution HEALPix data structure for spherically mapped point data", 2017.
S2 Geometry
"The hierarchical tessellation model and its use in spatial analysis", PAUL H Y TSUl AND ALLAN J BRIMICOMBE (1997). "Transadions in GIS", 1997, vol.2, no.3, pag. 267. O primeiro a usar algo similar ao Geohash (com partições retangulares), antes de 2010... Mas usava partição 6 em 6 ao invés de 4 em 4.

Contra-exemplos:

H3 Uber
...

Operações usuais em DGGS: ver diversas referências,