2 583
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 13h05min de 8 de julho de 2024
, 8 julho→Sistemas de coordenadas: ilustrações IJ e JI
(→Sistemas de coordenadas: ilustrações IJ e JI) |
|||
| Linha 8: | Linha 8: | ||
== Sistemas de coordenadas == | == Sistemas de coordenadas == | ||
[[Arquivo:DNGS-coords1.png|miniaturadaimagem|440x440px|Sistemas de coordenadas previstos pelo padrão DNGS: LatLong, XY e IJ. A superfície ''S''<sup>2</sup> é o globo terrestre, ''R''<sup>2</sup> o "plano LatLong WGS84" e XY o plano projetado Albers. A passagem para IJ é a discretização. Um mesmo angulo sólido α em locais diferentes do globo terá áreas diferentes em ''R''<sup>2</sup>, mas mesma área em XY.]] | [[Arquivo:DNGS-coords1.png|miniaturadaimagem|440x440px|Sistemas de coordenadas previstos pelo padrão DNGS: LatLong, XY e IJ. A superfície ''S''<sup>2</sup> é o globo terrestre, ''R''<sup>2</sup> o "plano LatLong WGS84" e XY o plano projetado Albers. A passagem para IJ é a discretização. Um mesmo angulo sólido α em locais diferentes do globo terá áreas diferentes em ''R''<sup>2</sup>, mas mesma área em XY.]]<!-- mais detalhes em https://math.stackexchange.com/a/849521/70274 --> | ||
O projeto como um todo faz uso de 3 sistemas de coordenadas: | O projeto como um todo faz uso de 3 sistemas de coordenadas: | ||
| Linha 17: | Linha 17: | ||
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. | 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]]--> | |||
[[Arquivo:Matrix-IJ | [[Arquivo:Matrix-conventions-IJ to JI.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''. | 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)\cdot s</math> pode ser simplificada para <math>X_i=i\cdot s</math> se mudarmos o domínio de ''I'' para o intervalo inteiro [0, m-1]. Analogamente o domínio de ''J'' para [0, n-1]. Com esse ajuste final temos a '''convenção DNGS para índices ''JI'''''. O resultado desta convenção ''JI'' pode ser apreciado pela representação da Curva-Z: | |||
[[Arquivo:MortonCurve IJ-JI.png|580px|center]] | |||
==Core== | ==Core== | ||
| Linha 133: | Linha 135: | ||
A degeneração geométrica, de quadrado para retângulo, é relativa ao segundo argumento de <code>vbit_interleave(x,y)</code>. Como a função é sempre chamada com a mesma ordem dos argumentos, sempre teremos ou só retangulos orizontais (XY) ou só verticais (YX). | A degeneração geométrica, de quadrado para retângulo, é relativa ao segundo argumento de <code>vbit_interleave(x,y)</code>. Como a função é sempre chamada com a mesma ordem dos argumentos, sempre teremos ou só retangulos orizontais (XY) ou só verticais (YX). | ||
===Otimização do cálculo de cobertura=== | === Otimização do cálculo de cobertura=== | ||
Ver [[osmc:Metodologia/Algoritmo_SQL#Tratamento_das_configurações|Tratamento das configurações]] onde já foi discutido e solucionado o tema. Aqui retomando para questões de otimização. | Ver [[osmc:Metodologia/Algoritmo_SQL#Tratamento_das_configurações|Tratamento das configurações]] onde já foi discutido e solucionado o tema. Aqui retomando para questões de otimização. | ||
| Linha 141: | Linha 143: | ||
grid_l0_cell_idx: 0 1 2 3 4 5 6 7 8 9 a b c d e fT fP fN | grid_l0_cell_idx: 0 1 2 3 4 5 6 7 8 9 a b c d e fT fP fN | ||
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''. | ||
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. | ||
| Linha 152: | Linha 154: | ||
*<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 168: | Linha 170: | ||
Lembrar que para [https://stackoverflow.com/a/25997497/287948 obter a array the uma multiarray] não é simples em SQL, exemplo de obtenção do indice ''i'': <code>SELECT array(select unnest( ('<nowiki>{{1,2,3},{4,5,6},{7,8,9}}</nowiki>'::int[][])[i:i] ));</code> | Lembrar que para [https://stackoverflow.com/a/25997497/287948 obter a array the uma multiarray] não é simples em SQL, exemplo de obtenção do indice ''i'': <code>SELECT array(select unnest( ('<nowiki>{{1,2,3},{4,5,6},{7,8,9}}</nowiki>'::int[][])[i:i] ));</code> | ||
===Algoritmo e funções finais de resolução=== | ===Algoritmo e funções finais de resolução === | ||
Algoritmo principal, tendo como entradas: ''pt'' e nível ''L''. Ponto ''pt'' em coordenadas planas, portanto ''x'' e ''y''. | Algoritmo principal, tendo como entradas: ''pt'' e nível ''L''. Ponto ''pt'' em coordenadas planas, portanto ''x'' e ''y''. | ||
#Célula da cobertura nacional: | #Célula da cobertura nacional: | ||
#*<code>ij0=grid_br.xyS_collapseTo_ijS(x,y);</code> com ''s0'' é default, ou função otimizada. | #*<code>ij0=grid_br.xyS_collapseTo_ijS(x,y);</code> com ''s0'' é default, ou função otimizada. | ||
| Linha 175: | Linha 177: | ||
#*<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 208: | Linha 210: | ||
===Célula dona da borda=== | ===Célula dona da borda=== | ||
[[Arquivo:Osmc-convencoes-bordas-exBR.png|miniaturadaimagem|480px|Grade e seus rótulos de célula, em púrpura claro. Os pontos de referência ''XYref'' foram destacados com estrelas vermelhas, e o rótulo da "célula dona do ponto" em preto. Linhas de borda, rotuladas também em preto pelas células com cantos inferior e esquerdo sobre a borda.]] | [[Arquivo:Osmc-convencoes-bordas-exBR.png|miniaturadaimagem|480px|Grade e seus rótulos de célula, em púrpura claro. Os pontos de referência ''XYref'' foram destacados com estrelas vermelhas, e o rótulo da "célula dona do ponto" em preto. Linhas de borda, rotuladas também em preto pelas células com cantos inferior e esquerdo sobre a borda.]] | ||
:'''Pendente''' confirmação e inclusão de ASSERT nas founções. (ou correção da regra para que a função estabeleça a convenção) | :'''Pendente''' confirmação e inclusão de ASSERT nas founções. (ou correção da regra para que a função estabeleça a convenção) | ||
As bordas são conjuntos de pontos, formados pela linha divisória entre 2 células e pelo ponto de fronteira entre 4 células. Apesar de serem infinitesimais, as bordas não podem ser "pontos sem dono". Cada ponto de borda precisa pertencer a uma das células, de um dos lados da borda. São convenções técnicas que definem esse pertencimento: | As bordas são conjuntos de pontos, formados pela linha divisória entre 2 células e pelo ponto de fronteira entre 4 células. Apesar de serem infinitesimais, as bordas não podem ser "pontos sem dono". Cada ponto de borda precisa pertencer a uma das células, de um dos lados da borda. São convenções técnicas que definem esse pertencimento: | ||
#Por convenção DNGS as linhas afetadas pelo ponto de referência pertencem à célula referida. Todos os pontos de fronteira entre 4 células, portanto, possuem um dono.<br />Exemplo: o ponto ''XY''=(0.0,0.0) pertence à célula ''IJ''=(0,0). A função ''ijS_to_xySref''() fui concebida de modo a garantir essa convenção (e vice-versa). | #Por convenção DNGS as linhas afetadas pelo ponto de referência pertencem à célula referida. Todos os pontos de fronteira entre 4 células, portanto, possuem um dono.<br />Exemplo: o ponto ''XY''=(0.0,0.0) pertence à célula ''IJ''=(0,0). A função ''ijS_to_xySref''() fui concebida de modo a garantir essa convenção (e vice-versa). | ||
#Todos os demais pontos, sobre as linhas de borda entre 2 células, pertencem à célula de cantos inferior e esquerdo sobre as respectivas linhas. São as linhas dos eixos locais XY, com origem no canto inferior esquerdo, dada pelo ponto de referência.<br /> Na ilustração abaixo mostramos que dois lados da célula permanecem com o rótulo da referência, e outros dois lados pertencem às respectivas células contíguas. Por exemplo a célula "6" da ilustração possui dois lados próprios, o inferior e o esquerdo, e dois lados impróprios, das células "2" e "7". | # Todos os demais pontos, sobre as linhas de borda entre 2 células, pertencem à célula de cantos inferior e esquerdo sobre as respectivas linhas. São as linhas dos eixos locais XY, com origem no canto inferior esquerdo, dada pelo ponto de referência.<br /> Na ilustração abaixo mostramos que dois lados da célula permanecem com o rótulo da referência, e outros dois lados pertencem às respectivas células contíguas. Por exemplo a célula "6" da ilustração possui dois lados próprios, o inferior e o esquerdo, e dois lados impróprios, das células "2" e "7". | ||
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 271: | Linha 273: | ||
===Casos de uso da grade completa e parcial=== | ===Casos de uso da grade completa e parcial=== | ||
A persistência do sistema de grades tem um custo muito alto, mas em geral, mesmo sem geometria, a lista de identificadores de célula terá um papel importante como chave-primária de conjuntos de atributos, no que consiste o sistema de informação. Existem duas estratégias para se persistir informações: | A persistência do sistema de grades tem um custo muito alto, mas em geral, mesmo sem geometria, a lista de identificadores de célula terá um papel importante como chave-primária de conjuntos de atributos, no que consiste o sistema de informação. Existem duas estratégias para se persistir informações: | ||
*[[wikipedia:Field (geography)|''geo-field'']]: atributos armazenados em todas as células, na grade inteira, eventualmente limitada pela resolução. Geocampos de alta resolução podem ser armazenados de forma separada, como [https://postgis.net/docs/raster.html raster] ou [https://postgis.net/docs/geomval.html geomvals]. | *[[wikipedia:Field (geography)|''geo-field'']]: atributos armazenados em todas as células, na grade inteira, eventualmente limitada pela resolução. Geocampos de alta resolução podem ser armazenados de forma separada, como [https://postgis.net/docs/raster.html raster] ou [https://postgis.net/docs/geomval.html geomvals]. | ||
| Linha 279: | Linha 281: | ||
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 310: | Linha 312: | ||
==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%;"> | ||