Generalized Geohash/pt: mudanças entre as edições
(→Representação textual: add Topologia e indexação) |
|||
Linha 111: | Linha 111: | ||
* [[wikipedia:Morton Curve|Curva de Morton]]: mais rápida de se calcular e com versão degenerada regular periódica. | * [[wikipedia:Morton Curve|Curva de Morton]]: mais rápida de se calcular e com versão degenerada regular periódica. | ||
* [[wikipedia:Hilbert Curve|Curva de Hilbert]]: mais eficiente ([[#Intervalos de geocódigos|sem descontinuidades]]) porém com versão degenerada aperiódica, e computacionalmente mais complexa (menor performance esperada). | * [[wikipedia:Hilbert Curve|Curva de Hilbert]]: mais eficiente ([[#Intervalos de geocódigos|sem descontinuidades]]) porém com versão degenerada aperiódica, e computacionalmente mais complexa (menor performance esperada). | ||
===Topologia e indexação === | |||
A resolução de '''problemas de vizinhança''' se faz de duas maneiras: | |||
* Algoritmo de vizinhança-4 (e por recorrência vizinhança-8) [[wikipedia:Z-order curve#Coordinate_values|baseado em operações bitwise e sequências de Moser-deBruijn]]. | |||
* Algoritmo para encontrar "BBOX" dentro da grade, [https://stackoverflow.com/a/34956693/287948 conhecido como Zdivide] ([https://web.archive.org/web/20180311015006/https://docs.raima.com/rdme/9_1/Content/GS/POIexample.htm#zdivide ref de 2028]). | |||
A resolução de problemas de indexação e busca hierárquica se faz através de diversas maneiras: | |||
* ''bit string'': na sua ordem natural proporciona recuperação de ramos da árvore. | |||
* "[[Código Natural/Representação interna#Hidden-bit_strategy|Bigint hiddenBit]]": funciona só com nível fixo. | |||
* "[[Código Natural/Representação interna#hInt|Bigint cached-length]]": mesma funcionalidade que ''bit string'', mesma performance que "hiddenBit", mas com cuto de 1% a 5% dos bits da representação numérica. | |||
===Representação textual=== | ===Representação textual=== |
Edição das 11h01min de 21 de julho de 2024
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:
- 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.
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
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, e computacionalmente mais complexa (menor performance esperada).
Topologia e indexação
A resolução de problemas de vizinhança se faz de duas maneiras:
- Algoritmo de vizinhança-4 (e por recorrência vizinhança-8) baseado em operações bitwise e sequências de Moser-deBruijn.
- Algoritmo para encontrar "BBOX" dentro da grade, conhecido como Zdivide (ref de 2028).
A resolução de problemas de indexação e busca hierárquica se faz através de diversas maneiras:
- bit string: na sua ordem natural proporciona recuperação de ramos da árvore.
- "Bigint hiddenBit": funciona só com nível fixo.
- "Bigint cached-length": mesma funcionalidade que bit string, mesma performance que "hiddenBit", mas com cuto de 1% a 5% dos bits da representação numérica.
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 log2 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 . As células Cj da grade resultante são obtidas da união de células da grade de nível superior, Fi, ou seja, . 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 . 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:
onde .
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
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 simplificar a localização de pontos de interesse, endereços ou quadrantes.
- Computacionais:
- Indexação: quadtree e similares em bancos de dados espaciais.
- Sistema de informação: as células indexadas são utilizadas como unidades de referência espacial para a localização de informações cadastrais. A informação pode ser recuperada e sua distribuição espacial avaliada.
- Geo-álgebra: representação e conversão de geo-objetos em geo-campos e vice versa.
- Ajuste hierárquico e estatístico: por oferecer grades de todos os níveis, a escolha do nível hierárquico mais adequado (à precisão ou alvo estatístico) é possível.
- Visualização de dados geográficos: oferecer identificadores zonais padronizados e com representação visual compacta.
- Cartografia: as células da grade padronizada permitem a interação humana com mapas e sistemas de informação. Os geocódigos padronizados permitem a visualização em mapas.
- Dashboards: geocódigos nos mais diversos gráficos e diagramas, relacionando-os com os códigos apresentados em mapas.
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
- Generalized Geohash/Poliedro
- Uso no DNGS
- Uso no DGGS
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,