2 585
edições
m (→História: ilustrando) |
|||
(16 revisões intermediárias pelo mesmo usuário 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: | ||
** diferentes bases além da [[ | ** 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 | ** 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]]). | * 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 29: | 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 == | ||
Linha 54: | Linha 100: | ||
==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. | |||
===Representação textual=== | ===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 64: | Linha 119: | ||
|'''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 72: | Linha 127: | ||
|''base2js'' | |''base2js'' | ||
|1 | |1 | ||
|<code>01</code> | | <code>01</code> | ||
|ECMA-262 | |ECMA-262 | ||
|- | |- | ||
Linha 84: | Linha 139: | ||
|4 | |4 | ||
|h | |h | ||
|''base4h'' | | ''base4h'' | ||
|2 | |2 | ||
|<code>0123 GQ</code> | | <code>0123 GQ</code> | ||
|ECMA + nhDigits alphabet | |ECMA + nhDigits alphabet | ||
|- | |- | ||
Linha 101: | Linha 156: | ||
|3 | |3 | ||
|<code>01234567 GQ HMRV</code> | |<code>01234567 GQ HMRV</code> | ||
| ECMA + nhDigits alphabet | |ECMA + nhDigits alphabet | ||
|- | |- | ||
|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 118: | Linha 173: | ||
|- | |- | ||
|32 | |32 | ||
|hex* | | hex* | ||
|''base32hex'' | |''base32hex'' | ||
|5 | |5 | ||
Linha 131: | Linha 186: | ||
|Geohash | |Geohash | ||
|- | |- | ||
| 32 | |32 | ||
|nvu | |nvu | ||
|''base32nvu'' | |''base32nvu'' | ||
|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 | ||
|<code>ABCDEFGHIJKLMNOPQRSTUVWXYZ234567</code> | |<code>ABCDEFGHIJKLMNOPQRSTUVWXYZ234567</code> | ||
|<nowiki>RFC 4648</nowiki>/sec6 | |<nowiki>RFC 4648</nowiki>/sec6 | ||
|- | |- | ||
|64 | |64 | ||
|url* | |url* | ||
|''base64url'' | |''base64url'' | ||
Linha 153: | Linha 208: | ||
|- | |- | ||
|64 | |64 | ||
|rfc | |rfc | ||
| ''base64rfc'' | | ''base64rfc'' | ||
|6 | |6 | ||
| <code>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/</code> | |<code>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/</code> | ||
| <nowiki>RFC 4648</nowiki>/sec4 | |<nowiki>RFC 4648</nowiki>/sec4 | ||
|- | |- | ||
| colspan="6" |<small>(*) default base. For example base32 is interpreted by default as base32hex.</small> | | colspan="6" |<small>(*) default base. For example base32 is interpreted by default as base32hex.</small> | ||
Linha 179: | Linha 234: | ||
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]]. | 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]]. | ||
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]]: | :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:Zcurve-8cells base4h.png|278px]] [[arquivo:Zcutve-base4.png|285px]] | ||
Linha 197: | Linha 254: | ||
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. | 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|380px|Comportamento do intervalo 7 a 9. Na Curva de Morton há descontinuidade.]] | |||
[[Arquivo:Sfc4q-intervals-Z-problem2.png|miniaturadaimagem|380px|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.]] | |||
==Solução multifinalitária == | 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: | 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). | #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) | # 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. | #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. | ||
Linha 209: | Linha 278: | ||
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. | 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: | 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 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 baseados em células triangulares sao menos eficientes do que os quadrados ... | ||
Linha 215: | Linha 284: | ||
A conclusão é que apenas sistemas hierárquicos de grades quadriláteras regulares é seriam elejíveis para o uso multifinalitário. | 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, | |||
*https://doi.org/10.1016/j.jag.2022.102985 | |||
*... | |||
[[Categoria:Conceitos]] | [[Categoria:Conceitos]] |
edições