Documentação

osmc:Metodologia/Algoritmo SQL/Lib: mudanças entre as edições

osmc Discussão

osmc:Metodologia/Algoritmo SQL/Lib (ver código-fonte)

Edição das 08h42min de 2 de julho de 2024

13 bytes adicionados ,  Terça-feira às 08h42min
m
→‎Algoritmo e funções finais de resolução
(→‎Core: tabela de perfil Lcover)
(4 revisões intermediárias pelo mesmo usuário não estão sendo mostradas)
Linha 6: Linha 6:


A seguir avaliando o uso ''default'' de XYref no lugar de XYcenter, para o desenho da célula. Algumas funções de flexibilização precisam ser agrupadas como "helper functions", enquanto as demais como "core functions". Por exemplo as convenções de array de inteiros baseadas em nível (xyL e ijL) são ''core'', enquanto as baseadas em size-side (xyS e ijS) são ''helper''.  
A seguir avaliando o uso ''default'' de XYref no lugar de XYcenter, para o desenho da célula. Algumas funções de flexibilização precisam ser agrupadas como "helper functions", enquanto as demais como "core functions". Por exemplo as convenções de array de inteiros baseadas em nível (xyL e ijL) são ''core'', enquanto as baseadas em size-side (xyS e ijS) são ''helper''.  
== Sistemas de coordenadas ==
O projeto como um todo faz uso de 3 sistemas de coordenadas
* LatLong: WGS84 no formato [[Geo URI]]
* XY: cartesiano escolar, coordenadas planas da projeção igual-area oficial do país
* IJ: XY discretizado
* JI?  A curva de morton rotacional IJ
...


==  Core ==
==  Core ==
Linha 12: Linha 20:
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''.  
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''.  


:Nota. A fórmula de ''S'' funciona também para níveis-meio, por exemplo ''L''=1.5. Isso se deve à suposição de que o "tamanho do lado genérico ''S'' de um retângulo" seja a raiz quadrada da área do retângulo; e pela [[Generalized_Geohash/pt#Representação_geométrica|construção geométrica dos níveis-meio]], cujas células (necessariamente de áreas iguais) são a união de 2 células do próximo nível inteiro: <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>.  
:Nota. A fórmula de ''S'' funciona também para níveis-meio, por exemplo ''L''=1.5. Isso se deve à suposição de que o "tamanho do lado genérico ''S'' de um retângulo" seja a raiz quadrada da área do retângulo; e pela [[Generalized_Geohash/pt#Representação_geométrica|construção geométrica dos níveis-meio]], cujas células (necessariamente de áreas iguais) são a união de 2 células do próximo nível inteiro: <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>. <br/>A mesma fórmula de ''S'' também nos permite calcular, conforme [[osmc:Metodologia/Algoritmo_SQL/Issues#Issue_05_-_Cálculo_de_dígitos_base32|issue 05]], o número de dígitos base32 para se chegar no metro, a partir do nível ''Lcover'' do município: <math>Ndig1m = 1+\lceil (Lmax-Lcover)/2.5 \rceil</math>.
 
No caso de geocódigo logístico, que requer cobertura municipal, supondo que o nível da grade adotada para cobertura seja ''Lcover'', podemos obteer a aproximação ao metro por um múltiplo de 2.5, que é a quantidade de níveis que se sobe a cada 5 bits do dígito da base32. Partindo de <math>1=2^{Lmax - Lcover - N \cdot 2.5}</math> obtemos por <math>log_2(1)=0</math> a fórmula <math>N= (Lmax-Lcover)/2.5</math>, onde ''N'' é o número de dígitos depois do primeiro para se chegar ao metro.  Num caso típico a cobertura municipal no Brasil (''Lmax''=20) é de nível ''L7.5'', resultando em ''N''=5, ou seja, com 6 dígitos teremos o metro. Para uma cobertura de resolução menor, ''L7'', o valor já não é exato, ''N''=5.2. O número de dígitos para chegar no metro portanto será <math>Ndig1m = 1+\lceil (Lmax-Lcover)/2.5 \rceil</math>.


A decisão de usar a sequência YX e não XY precisa talvez ser revista. Na cultura escolar brasileira XY é horizontal-vertical. Na cultura das imagens de satélite e geoprocessamento XY é vertical-horizontal. Adotamos a "cultura PostGIS", das funções ''standard spatial type'' (aquelas com prefixo "ST_").
A decisão de usar a sequência YX e não XY precisa talvez ser revista. Na cultura escolar brasileira XY é horizontal-vertical. Na cultura das imagens de satélite e geoprocessamento XY é vertical-horizontal. Adotamos a "cultura PostGIS", das funções ''standard spatial type'' (aquelas com prefixo "ST_").
Linha 33: Linha 39:
     FROM ( SELECT COALESCE($1[3],0) ) t1(intlevel)
     FROM ( SELECT COALESCE($1[3],0) ) t1(intlevel)
   ) t2
   ) t2
$f$ language SQL IMMUTABLE;
CREATE FUNCTION grid_br.logistic_Ndig1m(intlevel_cover int) RETURNS real[] AS $f$
    SELECT array[  Lcover, ceil(Ndig1m), ceil(Ndig1m)-Ndig1m,
          2^(Lmax-Lcover-ceil(Ndig1m)*2.5),
          CASE WHEN ceil(Ndig1m)-Ndig1m=0 THEN NULL ELSE 2^(Lmax-Lcover-floor(Ndig1m)*2.5) END  ]
    FROM (
      SELECT *, (Lmax-Lcover)/2.5 as Ndig1m
      FROM (SELECT 20 as Lmax, intlevel_cover/10.0 as Lcover) t1 
    ) t2
$f$ language SQL IMMUTABLE;
$f$ language SQL IMMUTABLE;
</syntaxhighlight>
</syntaxhighlight>


<!--
select x[1] as level_cover, x[2] as Ndigits_for_1m, round(x[4],2) as side_size, round(x[5],2) as size_before from (select grid_br.logistic_Ndig1m(intLevel) as x from generate_series(40,90,5) t1(intLevel)) t2;
-->
A escolha de nivel ''Lcover'' de cada município no caso do Brasil vai ter o seguinte perfil dado pela função <code>logistic_Ndig1m()</code>. Como o metro é a maior resolução significativa, é interesante não permitir resoluções finais inferiores a meio metro: por exemplo quando a cobertura ótima ''Lcover'' for 4 ou 4.5, usar no máximo 6 dígitos ao invés de 7, já que 2 metros e 1.4 metros são resoluções razoáveis para endereços. Idem ''Lcover''6.5 e 7 etc.
{| class="wikitable"
|+ Número de dígitos base32 para se chegar no metro, conforme ''Lcover'' do município
|-
|''Lcover'' || Ndigits for 1m || ''side_size'' || ''size_before''
|-
|        4 ||              7 ||      0.35 ||        2.00
|-
|      4.5 ||              7 ||      0.25 ||        1.41
|-
|        5 ||              6 ||      1.00 ||           
|-
|      5.5 ||              6 ||      0.71 ||        4.00
|-
|        6 ||              6 ||      0.50 ||        2.83
|-
|      6.5 ||              6 ||      0.35 ||        2.00
|-
|        7 ||              6 ||      0.25 ||        1.41
|-
|      7.5 ||              5 ||      1.00 ||           
|-
|        8 ||              5 ||      0.71 ||        4.00
|-
|      8.5 ||              5 ||      0.50 ||        2.83
|-
|        9 ||              5 ||      0.35 ||        2.00
|}
'''Construção da geometria''':
'''Construção da geometria''':


Linha 155: Linha 119:


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 ===
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.
A definição nacional, no caso do Brasil é
  grid_l0_cell:    40 41 42 43 30 31 32 33 34 21 22 23 11 12 13 02 44 24
  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'' na projeção do Brasil, ou seja, com coordenadas planas ''x'' e ''y''. O primeiro passo é obter as coordenadas ''ij0'' do ponto na cobertura.
O tamanho de célula ''s0'' da cobertura nacional é o ''default'' em <code>ij0=grid_br.xyS_collapseTo_ijS(x,y)</code>. Alternativamente uma cadeia de ''IF''s (árvore de decisão BBOX) pode nos fornecer rapidamente o valor. O que é mais rápido, depende de ''benchmark'' em cada linguagem (C ou SQL).
Como ij0 é um caso muito especial de ''ij'' podemos obter o seu valor num formato mais conveniente, por exemplo usando 3 bits (0=000, 1=001, 2=010, 3=011, 4=100, 5=101) 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. <!--
select varbit_to_int(b'100000') as "40", varbit_to_int(b'100001') as "41",
      varbit_to_int(b'100010') as "42", varbit_to_int(b'001011') as "13",
      varbit_to_int(b'000010') as "02", varbit_to_int(b'100100') as "44";
40 | 41 | 42 | 13 | 02 | 44
----+----+----+----+----+----
32 | 33 | 34 | 11 |  2 | 36
--> Resulta numa array esparsa de 40 posições.  Teremos:
* coordenadas iniciais ''x0'' e ''y0'' dadas por ''arrays'' <code>x0_from_ij0</code> e <code>x0_from_ij0</code>.
* índice cbits0 dado por ''array'' <code>cbits0_from_ij0</code>.
Por fim as 'arrays'' podem ser "hardcoded" nas funções usuárias, otimizando a obtenção dos valores desejado.


=== Algoritmo e funções finais de resolução ===
=== Algoritmo e funções finais de resolução ===
Algoritmo principal:
Algoritmo principal, tendo como entradas: ''pt'' e nível ''L''. Ponto ''pt'' em coordenadas planas, portanto ''x'' e ''y''.
 
# Célula da cobertura nacional:
# ''pt'' na projeção do Brasil, ou seja, com coordenadas planas ''x'' e ''y''.
#* <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); xy0=grid_br.ijS_to_xySref(ij0);</code>
#* <code>x0=x0_from_ij0[ij0]; y0=y0_from_ij0[ij0];</code> ou função de ij0 retorando xy0.
# <code>cbits0 = grid_br.IJ0_to_L0( ij0, false )</code>
#* <code>cbits0 = grid_br.IJ0_to_vbitL0( ij0, false )</code>
# <code>cbits = cbits0 || ints_to_interleavedbits(x-x0, y-y0, 20-level_desejado)</code>
# 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>cbits = cbits0 || ints_to_interleavedbits(ijL)</code>
#* <code>grid_br.xyS_draw_anycell( grid_br.ijL_to_xyL(ijL) )</code>


É um pouco mais complexo, 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.</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%;">
drop FUNCTION if exists grid_br.xyS_to_cbits(int,int,int,boolean)
drop FUNCTION if exists grid_br.xyS_to_cbits(int,int,int,boolean)
;
;
-- cuidado é YX! ver subtração
-- revisar se é YX!
CREATE FUNCTION grid_br.xyS_to_cbits(
CREATE FUNCTION grid_br.xyS_to_cbits(
   y int,
   y int,
Linha 179: Linha 170:
-- falta conferir se lenght(cbits0)>4 AND s<3
-- falta conferir se lenght(cbits0)>4 AND s<3
  SELECT CASE WHEN use_country_prefix THEN b'0001001100' ELSE b'' END  
  SELECT CASE WHEN use_country_prefix THEN b'0001001100' ELSE b'' END  
         || cbits0 || ints_to_interleavedbits(x-xy0[1], y-xy0[2], 20-s)
         || cbits0 || ints_to_interleavedbits( grid_br.xyS_collapseTo_ijL(x-xy0[1], y-xy0[2], S) )
  FROM (
  FROM (
   SELECT grid_br.ijS_to_xySref(ij0) as xy0, grid_br.IJ0_to_L0(ij0,false) as cbits0
   SELECT grid_br.ijS_to_xySref(ij0) as xy0, grid_br.IJ0_to_L0(ij0,false) as cbits0
Peter
2 402

edições

Disponível em “https://wiki.addressforall.org/doc/Especial:MobileDiff/4080...4199”