2 384
edições
m
→Representação geométrica
m (ref-list) |
|||
| (2 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
| Linha 100: | 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> | ::<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 110: | 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 118: | Linha 127: | ||
|''base2js'' | |''base2js'' | ||
|1 | |1 | ||
|<code>01</code> | | <code>01</code> | ||
|ECMA-262 | |ECMA-262 | ||
|- | |- | ||
| Linha 130: | 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 147: | 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 164: | Linha 173: | ||
|- | |- | ||
|32 | |32 | ||
|hex* | | hex* | ||
|''base32hex'' | |''base32hex'' | ||
|5 | |5 | ||
| Linha 177: | 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 199: | 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 225: | 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 243: | 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-comparing1.png|miniaturadaimagem|380px|Comportamento do intervalo 7 a 9. Na Curva de Morton há descontinuidade.]] | ||
| Linha 256: | Linha 267: | ||
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. | 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 == | ==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 267: | 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 274: | Linha 285: | ||
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 == | ==Ver também== | ||
* [[Generalized Geohash/Poliedro]] | *[[Generalized Geohash/Poliedro]] | ||
* Uso no [[DNGS]] | *Uso no [[DNGS]] | ||
* Uso no [[DGGS]] | *Uso no [[DGGS]] | ||
== Referências == | ==Referências== | ||
(Pendente revisar e usar [[Ref-list]]) | (Pendente revisar e usar [[Ref-list]]) | ||
Fundamentação e tecnologias similares: | 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. | *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 | *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. | *"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: | Contra-exemplos: | ||
* H3 Uber | *H3 Uber | ||
* ... | *... | ||
Operações usuais em DGGS: ver diversas referências, | Operações usuais em DGGS: ver diversas referências, | ||
* https://doi.org/10.1016/j.jag.2022.102985 | *https://doi.org/10.1016/j.jag.2022.102985 | ||
* ... | *... | ||
[[Categoria:Conceitos]] | [[Categoria:Conceitos]] | ||