Generalized Geohash/pt: mudanças entre as edições
(→Representação geométrica: revisando) |
m (→Intervalos de geocódigos: vizinhança) |
||
(31 revisões intermediárias por 2 usuários não estão sendo mostradas) | |||
Linha 1: | Linha 1: | ||
'''Generalização do algoritmo [[wikipedia:Geohash|Geohash]]''' para [[wikipedia:geocode|geocódigos]], '''GGeohash''' (do inglês ''Generalized Geohash''). Vantagens: | '''Generalização do algoritmo [[wikipedia:Geohash|Geohash]]''' para [[wikipedia:geocode|geocódigos]], '''GGeohash''' (do inglês ''Generalized Geohash''). Definição original em {{xref|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 | * permite adequação da representação textual às necessidades do usuário: | ||
*permite escolha entre 2 curvas de preenchimento (Morton e Hilbert). | ** diferentes bases além da [[base32]] clássica: [[base4h]], [[base8h]] ou [[base16h]]. | ||
** diferentes alfabetos além do clássico: padrões como [[#Representação textual|NVU ou JS]], e adaptações para o idioma do usuário (ex. russo). | |||
* permite escolha entre 2 curvas de preenchimento ([[wikipedia:Z-order curve|Morton]] e [[wikipedia:Hilbert curve|Hilbert]]). | |||
== Caracterização == | |||
As diversas opções podem ser visualizadas em [https://git-site.OSM.codes/Sfc4q/ '''Sfc4q'''] ('''''S'''pace-'''f'''illing '''c'''urves of refinement ratio '''4''' '''q'''uadrilateral''). Abaixo são ilustrados o Geohash clássico (Morton) e a sua generalização em curva de Hilbert. | |||
[[File:Comparing-Geoash-Hilbert.png|center|800px]] | [[File:Comparing-Geoash-Hilbert.png|center|800px]] | ||
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. | 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: | Entre as várias opções, uma delas corresponde ao "Geohash clássico". As opções surgem da combinação dos seguintes parâmetros: | ||
Linha 27: | Linha 31: | ||
|'''Curva de preenchimento''' | |'''Curva de preenchimento''' | ||
|Morton ou Hilbert | |Morton ou Hilbert | ||
|Define como será a indexação e | |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: | |||
* <code>6</code> ⊃ <code>6g</code> ⊃ <code>6gy</code> ⊃ <code>6gyc</code> ⊃ <code>6gyce</code> ⊃ <code>6gycex</code> | |||
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: | |||
* <code>2</code> ⊃ <code>2G </code> ⊃ <code>21</code> ⊃ <code>21Q</code> ⊃ <code>213</code> ⊃ <code>213Q</code> ⊃ <code>2132</code> | |||
* <code>2</code> ⊃ <code>21</code> ⊃ <code>213</code> ⊃ <code>2132</code> | |||
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: | |||
* <code>58</code> ⊃ <code>588M</code> ⊃ <code>588MC8</code> ⊃ <code>588MC8QV</code> | |||
O OLC faz uso de uma subgrade, destacada pelo separador <code>+</code>, que, esta sim, é hierárquica a cada dígito, mas não cumpre mais a curva de Morton: | |||
* <code>588MC8QV</code> ⊃ <code>588MC8QV+C</code> ⊃ <code>588MC8QV+CJ</code> | |||
Outro geocódigo, o [http://easymapwork.blogspot.com/2010/08/map-code.html '''map-code base4'''] usa Morton Base4 com alfabeto <code>ABCD</code> porém o prefixo do código é um par decimal representando quadrante de latitude e longitude inteiros. Exemplo: | |||
* <code>2627</code> ⊃ <code>2627 A</code> ⊃ <code>2627 AC</code> ⊃ <code>2627 ACC</code> | |||
* <code>2627</code> , <code>2628</code>, <code>2527</code>, ... | |||
Se entendermos os prefixos decimais como células de cobertura (~9999 células), fica caracterizado um GGeohash. | |||
== Problemas que soluciona == | |||
:: <small>Contém resumo de [[DNGS/Geocódigo#Desafios do bom geocódigo]].</small> | |||
... 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 == | == 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, | 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 [[wikipedia:base32|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. | |||
[[Arquivo:Geohash-binary.png|centro|520px]] | |||
[[Arquivo:Osmc-proj-S2geom-illustr1.png|thumb|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 [https://s2geometry.io/ 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 {{xref|KraEtAll2018}}. Em seguida, em 2019, uma fundamentação mais ampla foi adicionada através dos Natural Codes, com {{xref|KraEtAll2019}}. | Na AddressForAll, em 2018, foi desenvolvida a proposta do GGeohash, registrada para o domínio público em {{xref|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 {{xref|KraEtAll2019}}. | |||
== Typical and main usages == | == Typical and main usages== | ||
... | ... | ||
==Descrição técnica== | ==Descrição técnica== | ||
[[File:Zcurve45bits.png|thumb|360px|A principal vantagem da curva de Morton é a simplicidade e [https://web.archive.org/web/20240218152927/https://mmcloughlin.com/posts/geohash-assembly rapidez com que se pode realizar o encode/decode] das coordenadas XY.]] | |||
As [[wikipedia:Space-filling curve|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 [https://web.archive.org/web/20240218152511/https://mathoverflow.net/questions/357117/domino-tiling-obtained-from-space-filling-curves-is-possible-to-predict-basic-p discussão de 2020], existem apenas 3 possibilidades, sendo que uma delas pode ser descartada, por não ser "dominó-compatível": | ||
[[Arquivo:Space-filling curves for domino and minimal refinement ratio.png|centro|semmoldura|420x420px]] | |||
Estas duas são bem conhecidas, pelo nome dos seus descobridores, que primeiramente as descreveram matematicamente: | |||
* [[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). | |||
===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]]. Células "top/bottom/left/right" podem ser calculadas com alta performance sem recorrer à geometria. <br/>Ver interface de ''Neighbours'' em [https://www.movable-type.co.uk/scripts/geohash.html movable-type.co.uk/Geohash]. | |||
* 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]). | |||
* Algoritmo para resgatar interseção com cobertura: | |||
O principal vínculo entre algoritmos de vizinhança e geometria, é o cálculo da proximidade, ou ''buffer'': expansão da vizinhança através de "ondas" de proximidade. [https://www.pubnub.com/blog/calculating-geolocation-proximity-w-javascript-geohashing/ Exemplo]. | |||
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=== | |||
::<small>Resumo de [[Código natural/Notação posicional]].</small> | |||
Alfabetos e convenções da notação. Lista completa de IDs com respectivos alfabetos-padrão para [[Wikipedia:Positional notation|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 [[Wikipedia:Binary logarithm|log<sub>2</sub>]] da base. No alfabeto foram destacados os ''nhDigits'' (''non-hierarchical digits'') conforme notação [[Código natural|Natural Code]]. | Alfabetos e convenções da notação. Lista completa de IDs com respectivos alfabetos-padrão para [[Wikipedia:Positional notation|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 [[Wikipedia:Binary logarithm|log<sub>2</sub>]] da base. No alfabeto foram destacados os ''nhDigits'' (''non-hierarchical digits'') conforme notação [[Código natural|Natural Code]]. | ||
{| class="wikitable" | {| class="wikitable" | ||
Linha 55: | Linha 135: | ||
|'''label''' | |'''label''' | ||
|'''ID''' | |'''ID''' | ||
|'''bits''' | |'''bits''' | ||
|'''alphabet''' (depois do espaço os ''nhDigits'') | |'''alphabet''' (depois do espaço os ''nhDigits'') | ||
|'''Reference standard''' | |'''Reference standard''' | ||
|- | |- | ||
|2 | |2 | ||
Linha 63: | Linha 143: | ||
|''base2js'' | |''base2js'' | ||
|1 | |1 | ||
|<code>01</code> | | <code>01</code> | ||
|ECMA-262 | |ECMA-262 | ||
|- | |- | ||
Linha 75: | Linha 155: | ||
|4 | |4 | ||
|h | |h | ||
|''base4h'' | | ''base4h'' | ||
|2 | |2 | ||
|<code>0123 GQ</code> | | <code>0123 GQ</code> | ||
|ECMA + nhDigits alphabet | |ECMA + nhDigits alphabet | ||
|- | |- | ||
Linha 95: | Linha 175: | ||
|- | |- | ||
|16 | |16 | ||
|js* | |js* | ||
|''base16js'' | |''base16js'' | ||
|4 | | 4 | ||
|<code>0123456789abcdef</code> | |<code>0123456789abcdef</code> | ||
|ECMA-262 and <nowiki>RFC 4648</nowiki>/sec8 | |ECMA-262 and <nowiki>RFC 4648</nowiki>/sec8 | ||
|- | |- | ||
|16 | |16 | ||
Linha 109: | Linha 189: | ||
|- | |- | ||
|32 | |32 | ||
|hex* | | hex* | ||
|''base32hex'' | |''base32hex'' | ||
|5 | |5 | ||
Linha 127: | Linha 207: | ||
|5 | |5 | ||
|<code>0123456789BCDFGHJKLMNPQRSTUVWXYZ</code> | |<code>0123456789BCDFGHJKLMNPQRSTUVWXYZ</code> | ||
|No-Vowels except U (near non-syllabic) | |No-Vowels except U (near non-syllabic) | ||
|- | |- | ||
|32 | |32 | ||
|rfc | | rfc | ||
|''base32rfc'' | |''base32rfc'' | ||
|5 | |5 | ||
Linha 136: | Linha 216: | ||
|<nowiki>RFC 4648</nowiki>/sec6 | |<nowiki>RFC 4648</nowiki>/sec6 | ||
|- | |- | ||
|64 | |64 | ||
|url* | |url* | ||
|''base64url'' | |''base64url'' | ||
Linha 145: | Linha 225: | ||
|64 | |64 | ||
|rfc | |rfc | ||
|''base64rfc'' | | ''base64rfc'' | ||
|6 | |6 | ||
|<code>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/</code> | |<code>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/</code> | ||
Linha 158: | Linha 238: | ||
<!-- [[File:MortonCurve64grid-mergingCells.png|thumb|480px|A curva da grade de 32 células foi obtida mesclando-se 2 a 2 células do "próximo nível" (grade de 64 células ilustrada) para obter uma representação geométrica do "Geohash de dígito ímpar".]]--> | <!-- [[File:MortonCurve64grid-mergingCells.png|thumb|480px|A curva da grade de 32 células foi obtida mesclando-se 2 a 2 células do "próximo nível" (grade de 64 células ilustrada) para obter uma representação geométrica do "Geohash de dígito ímpar".]]--> | ||
No contexto do [[ | No contexto do [[Discrete National Grid Systems|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. <!-- {figura do quadrado para dois retângulos} --> | ||
É 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 <math>j = \left\lfloor\frac{i}{2}\right\rfloor</math>. As células ''C''<sub>j</sub> da grade resultante são obtidas da união de células da grade de nível superior, ''F''<sub><i>i</i></sub>, ou seja, <math>C_j = F_{j \times 2} \cup F_{j \times 2 + 1}</math>. Ilustrando com os dois tipos de [[wikipedia:Space-filling curve|curva de preenchimento]]: | |||
[[Arquivo:MortonCurve64grid-merging32grid.png|centro|580px]] | |||
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. | |||
[[Arquivo:HilbertCurve64grid-merging32grid.png|centro|580px]] | |||
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 [[wikipedia:Domino tiling|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 [[Discrete National Grid Systems/pt|padrão DNGS]] temos <math>S_{L}=2^{Lmax-L}</math>. No caso do Brasil ''Lmax''=20, no caso de Camarões ''Lmax=18''.<br/>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:<br/> <math>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}</math> onde <math>Lhalf = \forall L | L = \lceil L \rceil - 0.5</math>. | |||
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]]: | |||
[[arquivo:Zcurve-8cells base4h.png|278px]] [[arquivo:Zcutve-base4.png|285px]] | |||
[[Arquivo:Sfc4q-Morton-grid64 gridHalf.png|620px|centro]] | |||
===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). | |||
[[Arquivo:GGeohash-ilustra4.png|centro|620px]] | |||
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==== | |||
[[Arquivo:Sfc4q-intervals-comparing1.png|miniaturadaimagem|400px|Comportamento do intervalo 7 a 9. Na Curva de Morton há descontinuidade.]] | |||
[[Arquivo: | [[Arquivo:Sfc4q-intervals-Z-problem2.png|miniaturadaimagem|400px|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. Todos os intervalos Hilbert são de [[wikipedia:Von Neumann neighborhood|vizinhança por aresta]], enquanto intervalos Morton, como o 4-9, podem conter vizinhança por adjacência.]] | ||
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: [[wikipedia:Quadtree|''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 | 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]]) | |||
A | 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, | ||
*https://doi.org/10.1016/j.jag.2022.102985 | |||
*... | |||
[[Categoria:Conceitos]] |
Edição atual tal como às 22h43min de 6 de agosto 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. Células "top/bottom/left/right" podem ser calculadas com alta performance sem recorrer à geometria.
Ver interface de Neighbours em movable-type.co.uk/Geohash.
- Algoritmo para encontrar "BBOX" dentro da grade, conhecido como Zdivide (ref de 2028).
- Algoritmo para resgatar interseção com cobertura:
O principal vínculo entre algoritmos de vizinhança e geometria, é o cálculo da proximidade, ou buffer: expansão da vizinhança através de "ondas" de proximidade. Exemplo. 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,