2 525
edições
osmc:Metodologia/Algoritmo SQL/Lib: mudanças entre as edições
osmc:Metodologia/Algoritmo SQL/Lib (ver código-fonte)
Edição das 12h08min de 8 de julho de 2024
, 8 julho→Sistemas de coordenadas
| Linha 15: | Linha 15: | ||
*'''IJ''': XY discretizado. É o tradicional ''IJ'' rotacionado para que na Curva de Morton o eixo Y tenha prioridade. | *'''IJ''': XY discretizado. É o tradicional ''IJ'' rotacionado para que na Curva de Morton o eixo Y tenha prioridade. | ||
... | ... | ||
Na tradição matemática a indexação de matrizes, com elementos <math>a_{ij}</math>, índice ''i'' variando nas linhas e ''j'' variando nas colunas, a origem <math>a_{11}</math> é no canto superior esquerdo, enquanto a origem ''XY'' do eixo cartesiano é no canto inferior. | |||
[[Arquivo:Matrix-IJ-conventions.png|320px|center]] | |||
Para equiparar a orientação de ''I×J'' a ''X×Y'' é necessário [[wikipedia:Rotation_matrix#Common_2D_rotations|aplicar a rotação de 90 graus no sentido anti-horário]] sobre ''I×J'', o que equivale a trocar a ordem das coordenadas, ou seja, convencionar ''J×I''. | |||
[[Arquivo:Matrix-JI-coventions.png|220px|center]] | |||
Por fim, na convenção cartesiana ''XY'' a origem é (0,0) e a equação <math>X_i=(i-1)*s</math> pode ser simplificada para <math>X_i=i*s</math> se mudarmos os domínios de ''I'' para o intervalo inteiro <math>\[0\dots m-1\]</math> e de ''J'' para [0, m-1] | |||
==Core== | ==Core== | ||
| Linha 133: | Linha 143: | ||
A entrada é o ponto ''pt''=(''x'',''y''). O primeiro passo é obter as coordenadas ''ij0'' de ''pt'' na cobertura. Temos dois possíveis algoritmos: | A entrada é o ponto ''pt''=(''x'',''y''). O primeiro passo é obter as coordenadas ''ij0'' de ''pt'' na cobertura. Temos dois possíveis algoritmos: | ||
* A função discretizadora <code>ijL0=grid_br.xyS_collapseTo_ijL(x,y)</code>, onde o tamanho de célula ''s0'' é o ''default''. | *A função discretizadora <code>ijL0=grid_br.xyS_collapseTo_ijL(x,y)</code>, onde o tamanho de célula ''s0'' é o ''default''. | ||
*Uma árvore de decisão com 4 nívieis de ''IF''s (análogo a índice BBOX) pode nos fornecer rapidamente o valor ''ijL0''. | *Uma árvore de decisão com 4 nívieis de ''IF''s (análogo a índice BBOX) pode nos fornecer rapidamente o valor ''ijL0''. | ||
| Linha 139: | Linha 149: | ||
O que é mais rápido, depende de ''benchmark'' na linguagem adotada (C ou SQL). Por hora ficamos com o primeiro algoritmo. | O que é mais rápido, depende de ''benchmark'' na linguagem adotada (C ou SQL). Por hora ficamos com o primeiro algoritmo. | ||
Como ''ijL0'' é um caso muito especial de ''ij'' podemos obter o seu valor num formato mais conveniente. Exemplos: | Como ''ijL0'' é um caso muito especial de ''ij'' podemos obter o seu valor num formato mais conveniente. Exemplos: | ||
*<code>ij0 := i::text||j::text</code> poderia usar um objeto JSONb como array associativa, mas não é tão rápido quanto array SQL. Seria algo hardcoded numa função, <code>('{"40":[123,456,"0"],"41":[0,1,"1"],"13":[22,33,"e"]}'::jsonb)->ij0</code>. | *<code>ij0 := i::text||j::text</code> poderia usar um objeto JSONb como array associativa, mas não é tão rápido quanto array SQL. Seria algo hardcoded numa função, <code>('{"40":[123,456,"0"],"41":[0,1,"1"],"13":[22,33,"e"]}'::jsonb)->ij0</code>. | ||
*<code>i*10+j</code> resulta em array de 44 posições. Seriam ''arrays'' leves; e delas, a partir de ''ij0'', teremos: | *<code>i*10+j</code> resulta em array de 44 posições. Seriam ''arrays'' leves; e delas, a partir de ''ij0'', teremos: | ||
**coordenadas iniciais ''x0'' e ''y0'', por arrays <code>x0_from_ij0</code> e <code>x0_from_ij0</code>; | **coordenadas iniciais ''x0'' e ''y0'', por arrays <code>x0_from_ij0</code> e <code>x0_from_ij0</code>; | ||
**índice ''cbits0'', pela array <code>cbits0_from_ij0</code>. | ** índice ''cbits0'', pela array <code>cbits0_from_ij0</code>. | ||
<!-- | <!-- | ||
* usando 3 bits (0=000, 1=001, 2=010, 3=011, 4=100) e concatenando os valores de ''i'' e ''j'': 40=b'100000'=32 41=b'100001'=33 42=b'100010'=34 ... 13=b'001011'=11 02=b'000010'=2 44=b'100100'=36 24=b'010100'=20. | * usando 3 bits (0=000, 1=001, 2=010, 3=011, 4=100) e concatenando os valores de ''i'' e ''j'': 40=b'100000'=32 41=b'100001'=33 42=b'100010'=34 ... 13=b'001011'=11 02=b'000010'=2 44=b'100100'=36 24=b'010100'=20. | ||
| Linha 165: | Linha 175: | ||
#*<code>cbits0 = grid_br.IJ0_to_vbitL0( ij0, false )</code> | #*<code>cbits0 = grid_br.IJ0_to_vbitL0( ij0, false )</code> | ||
#Código ''cbits'' e geometria da célula do nível ''L'': | #Código ''cbits'' e geometria da célula do nível ''L'': | ||
#*<code>ijL=grid_br.xyL_collapseTo_ijL(x-xy0[1], y-xy0[2], L);</code> | #*<code>ijL=grid_br.xyL_collapseTo_ijL(x-xy0[1], y-xy0[2], L);</code> | ||
#*<code>cbits = cbits0 || ints_to_interleavedbits(ijL)</code> | #*<code>cbits = cbits0 || ints_to_interleavedbits(ijL)</code> | ||
#*<code>grid_br.xyS_draw_anycell( grid_br.ijL_to_xyL(ijL) )</code> | #*<code>grid_br.xyS_draw_anycell( grid_br.ijL_to_xyL(ijL) )</code> | ||
Com um passo a mais para contemplar os casos de pontos sobre cobertura fantasma. Existe uma condição de validade e um ajuste do ponto ao nível: | Com um passo a mais para contemplar os casos de pontos sobre cobertura fantasma. Existe uma condição de validade e um ajuste do ponto ao nível: | ||
:<code>SE lenght(cbits0)>4 e level_desejado<1.5 THEN NULL; ELSE recalcula xy0 dentro da célula especial.</code> | :<code>SE lenght(cbits0)>4 e level_desejado<1.5 THEN NULL; ELSE recalcula xy0 dentro da célula especial.</code> | ||
<syntaxhighlight lang="sql" style="font-size: 80%;"> | <syntaxhighlight lang="sql" style="font-size: 80%;"> | ||
| Linha 207: | Linha 217: | ||
No caso especial de fronteira nacional, como as células "0" ou "3" do Brasil, onde não existem "células contíguas", o dono é o país estrangeiro, portanto, a rigor, a linha inteira (incluindo o canto do quadrado) não existe na grade. | No caso especial de fronteira nacional, como as células "0" ou "3" do Brasil, onde não existem "células contíguas", o dono é o país estrangeiro, portanto, a rigor, a linha inteira (incluindo o canto do quadrado) não existe na grade. | ||
===Geração do sistema de grades=== | === Geração do sistema de grades=== | ||
Algoritmo genérico, para gerar grades nacionais ou municipais. Existem dois algoritmos mais gerais de geração: "scan IJ" e scan NatCodes". | Algoritmo genérico, para gerar grades nacionais ou municipais. Existem dois algoritmos mais gerais de geração: "scan IJ" e scan NatCodes". | ||
A função <code>grid_br.parents_to_children_cuting</code> implementa de maneira simples o algoritmo "scan NatCodes", que pode ser expresso como recorrência: | A função <code>grid_br.parents_to_children_cuting</code> implementa de maneira simples o algoritmo "scan NatCodes", que pode ser expresso como recorrência: | ||
#Gera células-filhas da cobertura. | # Gera células-filhas da cobertura. | ||
#Remove filhas que ficaram fora da interseção da geometria do país (ou município). | # Remove filhas que ficaram fora da interseção da geometria do país (ou município). | ||
#Assume filhas como cobetura e volta ao 1. | #Assume filhas como cobetura e volta ao 1. | ||
| Linha 269: | Linha 279: | ||
O sistema completo de grades é mais importante no caso de ''geo-fields''. Os primeiros níveis podem ser geo-fields orientadores, para descobrir onde se encontram geo-objects de interesse. Municípios, devido ao interesse por gestão polcal podem formarmar seus geofields locais, um só banco de dados para a getão municipal (não o país inteiro), viabilizando o armazenamento, que requer capacidade exponencial de disco em função do nível. | O sistema completo de grades é mais importante no caso de ''geo-fields''. Os primeiros níveis podem ser geo-fields orientadores, para descobrir onde se encontram geo-objects de interesse. Municípios, devido ao interesse por gestão polcal podem formarmar seus geofields locais, um só banco de dados para a getão municipal (não o país inteiro), viabilizando o armazenamento, que requer capacidade exponencial de disco em função do nível. | ||
==Helper lib== | ==Helper lib == | ||
Funções complementares às "core functions", a maioria implementações "wrap" para simplesmente compatibilizar tipos e estruturas. Ainda assim a ortogonalidade é requerida apenas nos tipos principais (ex. baseados no ''intLevel''), não precisam garantir a conversão direta de tipos secundários (ex. ''cell side size''). | Funções complementares às "core functions", a maioria implementações "wrap" para simplesmente compatibilizar tipos e estruturas. Ainda assim a ortogonalidade é requerida apenas nos tipos principais (ex. baseados no ''intLevel''), não precisam garantir a conversão direta de tipos secundários (ex. ''cell side size''). | ||
| Linha 300: | Linha 310: | ||
==Testes da lib== | ==Testes da lib== | ||
Primeiro demonstrações (de que as funções funcionam), testes para validar hipóteses e requisitos básicos; depois [https://pt.stackoverflow.com/a/13530/4186 testes de regressão]. | Primeiro demonstrações (de que as funções funcionam), testes para validar hipóteses e requisitos básicos; depois [https://pt.stackoverflow.com/a/13530/4186 testes de regressão]. | ||
===Validação primária=== | ===Validação primária === | ||
Testes para validação, usando funções ou tabelas já homologadas: | Testes para validação, usando funções ou tabelas já homologadas: | ||
<syntaxhighlight lang="sql" style="font-size: 80%;"> | <syntaxhighlight lang="sql" style="font-size: 80%;"> | ||