Subpavimentação: mudanças entre as edições
(Criou página com 'miniaturadaimagem|Ilustrando em vermelho a subpavimentação menor (interior), que estaria sobrepondo a subpavimentação maior (com borda) em amarelo. De https://github.com/osm-codes/WS/issues/28 O tema é tratado entre os matemáticos como subpavimentação... Dada uma geometria ''X'', temos duas aproximações, ''X⁻'' e ''X⁺'', tais que ''X''⁻ ⊂ ''X'' ⊂ ''X⁺''. Precisamos de duas funções neste projeto: # A...') |
|||
| (12 revisões intermediárias por 2 usuários não estão sendo mostradas) | |||
| Linha 1: | Linha 1: | ||
[[Arquivo:DGGS-coverRectangular1.png|miniaturadaimagem|Ilustrando em vermelho a subpavimentação menor (interior), que estaria sobrepondo a subpavimentação maior (com borda) em amarelo. ]] | [[Arquivo:DGGS-coverRectangular1.png|miniaturadaimagem|Ilustrando em vermelho a subpavimentação menor (interior), que estaria sobrepondo a subpavimentação maior (com borda) em amarelo. ]] | ||
[[Arquivo:OSMC-cover-MontFuji-cut.png|miniaturadaimagem|Aneis representados por ''cobertura equilibrada'', entre a menor e a maior.]] | |||
No [[OSMC|projeto OSMC]] tratamos de "funções universais de cobertura": o tema específico é tratado entre os matemáticos como [[wikipedia:Subpaving|'''subpavimentação''']] (do inglês ''subpaving''). Dada uma geometria ''X'', temos duas aproximações, ''X⁻'' e ''X⁺'', tais que ''X''⁻ ⊂ ''X'' ⊂ ''X⁺''. | |||
Esses conjuntos podem ser obtidos de funções correspondentes de redução da resolução (de alta para baixa), ou de conversão "vector to raster": | |||
# A '''cobertura interior''', ou seja, ''X⁻'', e portanto uma aproximação de subpavimentação conforme os limites de grade ou de número de células imposto. Na ilustração é a parte vermelha | # A '''cobertura interior''' (menor), ou seja, ''X⁻'', e portanto uma aproximação de subpavimentação conforme os limites de grade ou de número de células imposto. Na ilustração é a parte vermelha. | ||
# A '''cobertura com borda''' (maior), ou seja, ''X⁺''. Na ilustração a união da parte vermelha com a amarela, onde a parte amarela é a aproximação de borda. | |||
== Implementação == | # ... Não há um jargão matemático, mas teríamos a "cobertura equilibrada", "intermediária" ou "média", como uma versão equilibrada entre as coberturas maior e menor. Na ilustração ao lado os anéis foram '''ajustados para cada célula conter mais de 50%''' da sua região original (vetorial). | ||
Ver "region cover" (de fato esse é o nome mais popular para a funcionalidade) em | |||
Outra abordagem, a [[wikipedia:Mathematical Morphology|Morfologia Matemática]], trata sempre da aproximação de ''X'' como ponto de partida: ''X⁺'' é a sua '''dilatação''' e ''X⁻'' a sua '''erosão''', mas existem centenas de maneiras diferentes para se erodir ou dilatar, ver livro em portugues. No [[PostGIS]] temos [https://postgis.net/docs/ST_Buffer.html ST_Buffer] positivo e negativo como recurso para depois discretizar na grade, quando um controle métrico for necessário. | |||
Quanto à implementação desse tipo de representação de [[geo-objetos]], a mais tradicional é o [[quadtree]]. | |||
==Implementação== | |||
Ver "region cover" (de fato esse é o nome mais popular para a funcionalidade) em [https://igorgatis.github.io/ws2 igorgatis.github.io/ws2] ou [https://s2geometry.io/devguide/examples/coverings.html S2 Covering Examples]. | |||
A '''interseção''' pode ser uma boa referência: | A '''interseção''' pode ser uma boa referência: | ||
* '''interseção da borda com grade fixa de maior resolução''': pode depois ser otimizada com substituição das células interiores por grades de menor resolução. Pode retornar a borda, o interior ''X⁻'' ou ''X⁺''. | *'''interseção da borda com grade fixa de maior resolução''': pode depois ser otimizada com substituição das células interiores por grades de menor resolução. Pode retornar a borda, o interior ''X⁻'' ou ''X⁺''. | ||
* '''interseção da borda com espeçura fixa''': tomando-se um buffer métrico da linha de borda podemos medir a área de interseção de modo a selecionar mais corretamente a resolução mais grosseira, minimizando a quantidade de células que comporá a aproximação de borda. | *'''interseção da borda com espeçura fixa''': tomando-se um buffer métrico da linha de borda podemos medir a área de interseção de modo a selecionar mais corretamente a resolução mais grosseira, minimizando a quantidade de células que comporá a aproximação de borda. | ||
* '''interseção com tamanhos variávies''': usar o número de células como parâmetro. A função buscaria a menor área de não-interseção, resultando em ''X⁺''. | *'''interseção com tamanhos variávies''': usar o número de células como parâmetro. A função buscaria a menor área de não-interseção, resultando em ''X⁺''. | ||
===Bibliotecas === | |||
... No guia dos algoritmos de grade... Ver [https://github.com/AddressForAll/pg_pubLib-v1/tree/main/docs/src-illustrative pg_pubLib-v1/docs/src-illustrative] , mostra como funciona o algoritmo de cobertura com códigos hierárquicos binários (bitstrings). A partir dele foi implementado no PostGIS a [https://github.com/AddressForAll/pg_pubLib-v1/blob/main/docs/pgis-geohash.md solução real para Geohashes]. Ver Cover Functions em https://git.osm.codes/GGeohash (ver issues/1) | |||
* define modal density strategy: one centroid as cover reference (one contiguous cover), or many local centers to many disjoint coverages. | |||
* function that take the geocode list as input and return a small set of geocodes representing its coverage. | |||
[[Arquivo:Osmc-coverBR-byGeohashes.png|center]] | |||
== Uso prático nos projetos == | |||
A principal aplicação nos projetos AddressForAll é a "cobertura de jurisdição" no [[OSMC]]. | |||
Ver também [[DNGS/Poliedro das nações]] e [[osmc:Convenções/Grade_científica_multifinalitária#Grade_e_Notação_Logística]]. | |||
Construir pagina [[osmc:Convenções/Coberturas]]. | |||
== Generalização e rotulação hierárquica== | |||
[[Arquivo:Mosaic-voronoi-andIndex.png|miniaturadaimagem|Mosaicos são compostos de ladrilhos, seguindo um padrão qualquer, regular ou irregular. <br/>O requisito de P1 é que cubra toda a superfície, sem deixar buracos. Em P1 define-se '''identificador de ladrilhos''': cada ladrilho pode ser identificado por seu nome (ex.cor), mas o mais curto é o rótulo numérico.]] | |||
Operacionalmente a subpavimentação, para que possa ser generalizada, pode partir de um sistema de mosaicos hierárquicos. Na ilustração ao lado o mosaico inicial. Em certas aplicações a rotulação (em destaque) também é importante. | |||
A partição sucessiva, por exemplo de todas as células do mosaico em duas, gera a noção de hierarquica. As células-filha vão sendo rotuladas por um path cuja raiz são os rótulos do mosaico inicial. A rotulação hierárquica cabe também nesta generalização. | |||
[[Arquivo:Mosaic-voronoi-andIndex-subpav-hierarchy.png|centro|semmoldura|480px]] | |||
A subpavimentação é um conceito geral, operacionalmente baseado apenas na noção de conjunto, e conceitualmente o sistema hierárquico de retângulos é extensível para sistema hierárquico de mosaicos irregulares. | |||
Resumindo: | |||
* O mosaico é a cobertura do plano por ladrilhos, ou seja, uma cobertura que não deixa buracos, por polígonos que não se sobrepõe. | |||
* As células do mosaico podem receber IDs (rótulos) | |||
* As células do mosaico podem ser submetidas a uma "subdivisão regular sucessiva" de todas as suas células. Por exemplo subdividir em 2. | |||
* Os IDs das células-filha são paths, e precisam ter como prefixo o ID da célula-mãe. | |||
===Extensão para triangulos e hexagonos=== | |||
Um processo análogo com triângulos é sempre possível, tendo em vista que um triângulo pode ser subdividido em 4 recursivamente, apesar de não poder ser subdibvido em 2 como o quadrilátero. | |||
Já o hexagono, muito usado em [[DGGS]], aparentemente não pode ser submetido a esse tipo de proceso. Ver | |||
*prova de que não existe subpavimentação hexasgobal https://stackoverflow.com/a/759232/287948 | |||
* prova de que na cobertura da esfera é impossível (precisa de pentágonos), https://stackoverflow.com/a/759232/287948 | |||
*ver guia de grades hexagonais, {{xref|Patel13}}, como contra-exemplo: nao apresenta algoritmo de cobertura. | |||
https://gis.stackexchange.com/q/473092/7505 | |||
== Implementações otimizadas == | |||
A partir da grade de maior resolução pode-se depois, por análise de strings apenas, chegar na cobertura hierárquica. | |||
O algoritmos da interseção todavia é pesado. Existe uma opção mais leva que é trocar o "traçado vetorial do PostGIS por traçado na grade". Ver algoritmos, que idealmente seriam convertidos em C: | |||
* [[wikipedia:Bresenham's line algorithm|Bresenham's line algorithm]] | |||
* Bresenham's bold line: http://eugen.dedu.free.fr/projects/bresenham/ | |||
==Ver também== | |||
... | |||
[[Categoria:Conceitos]] | |||
Edição atual tal como às 22h59min de 25 de março de 2024
No projeto OSMC tratamos de "funções universais de cobertura": o tema específico é tratado entre os matemáticos como subpavimentação (do inglês subpaving). Dada uma geometria X, temos duas aproximações, X⁻ e X⁺, tais que X⁻ ⊂ X ⊂ X⁺.
Esses conjuntos podem ser obtidos de funções correspondentes de redução da resolução (de alta para baixa), ou de conversão "vector to raster":
- A cobertura interior (menor), ou seja, X⁻, e portanto uma aproximação de subpavimentação conforme os limites de grade ou de número de células imposto. Na ilustração é a parte vermelha.
- A cobertura com borda (maior), ou seja, X⁺. Na ilustração a união da parte vermelha com a amarela, onde a parte amarela é a aproximação de borda.
- ... Não há um jargão matemático, mas teríamos a "cobertura equilibrada", "intermediária" ou "média", como uma versão equilibrada entre as coberturas maior e menor. Na ilustração ao lado os anéis foram ajustados para cada célula conter mais de 50% da sua região original (vetorial).
Outra abordagem, a Morfologia Matemática, trata sempre da aproximação de X como ponto de partida: X⁺ é a sua dilatação e X⁻ a sua erosão, mas existem centenas de maneiras diferentes para se erodir ou dilatar, ver livro em portugues. No PostGIS temos ST_Buffer positivo e negativo como recurso para depois discretizar na grade, quando um controle métrico for necessário.
Quanto à implementação desse tipo de representação de geo-objetos, a mais tradicional é o quadtree.
Implementação
Ver "region cover" (de fato esse é o nome mais popular para a funcionalidade) em igorgatis.github.io/ws2 ou S2 Covering Examples.
A interseção pode ser uma boa referência:
- interseção da borda com grade fixa de maior resolução: pode depois ser otimizada com substituição das células interiores por grades de menor resolução. Pode retornar a borda, o interior X⁻ ou X⁺.
- interseção da borda com espeçura fixa: tomando-se um buffer métrico da linha de borda podemos medir a área de interseção de modo a selecionar mais corretamente a resolução mais grosseira, minimizando a quantidade de células que comporá a aproximação de borda.
- interseção com tamanhos variávies: usar o número de células como parâmetro. A função buscaria a menor área de não-interseção, resultando em X⁺.
Bibliotecas
... No guia dos algoritmos de grade... Ver pg_pubLib-v1/docs/src-illustrative , mostra como funciona o algoritmo de cobertura com códigos hierárquicos binários (bitstrings). A partir dele foi implementado no PostGIS a solução real para Geohashes. Ver Cover Functions em https://git.osm.codes/GGeohash (ver issues/1)
- define modal density strategy: one centroid as cover reference (one contiguous cover), or many local centers to many disjoint coverages.
- function that take the geocode list as input and return a small set of geocodes representing its coverage.
Uso prático nos projetos
A principal aplicação nos projetos AddressForAll é a "cobertura de jurisdição" no OSMC.
Ver também DNGS/Poliedro das nações e osmc:Convenções/Grade_científica_multifinalitária#Grade_e_Notação_Logística.
Construir pagina osmc:Convenções/Coberturas.
Generalização e rotulação hierárquica
Operacionalmente a subpavimentação, para que possa ser generalizada, pode partir de um sistema de mosaicos hierárquicos. Na ilustração ao lado o mosaico inicial. Em certas aplicações a rotulação (em destaque) também é importante.
A partição sucessiva, por exemplo de todas as células do mosaico em duas, gera a noção de hierarquica. As células-filha vão sendo rotuladas por um path cuja raiz são os rótulos do mosaico inicial. A rotulação hierárquica cabe também nesta generalização.
A subpavimentação é um conceito geral, operacionalmente baseado apenas na noção de conjunto, e conceitualmente o sistema hierárquico de retângulos é extensível para sistema hierárquico de mosaicos irregulares.
Resumindo:
- O mosaico é a cobertura do plano por ladrilhos, ou seja, uma cobertura que não deixa buracos, por polígonos que não se sobrepõe.
- As células do mosaico podem receber IDs (rótulos)
- As células do mosaico podem ser submetidas a uma "subdivisão regular sucessiva" de todas as suas células. Por exemplo subdividir em 2.
- Os IDs das células-filha são paths, e precisam ter como prefixo o ID da célula-mãe.
Extensão para triangulos e hexagonos
Um processo análogo com triângulos é sempre possível, tendo em vista que um triângulo pode ser subdividido em 4 recursivamente, apesar de não poder ser subdibvido em 2 como o quadrilátero.
Já o hexagono, muito usado em DGGS, aparentemente não pode ser submetido a esse tipo de proceso. Ver
- prova de que não existe subpavimentação hexasgobal https://stackoverflow.com/a/759232/287948
- prova de que na cobertura da esfera é impossível (precisa de pentágonos), https://stackoverflow.com/a/759232/287948
- ver guia de grades hexagonais, [Patel13], como contra-exemplo: nao apresenta algoritmo de cobertura.
https://gis.stackexchange.com/q/473092/7505
Implementações otimizadas
A partir da grade de maior resolução pode-se depois, por análise de strings apenas, chegar na cobertura hierárquica.
O algoritmos da interseção todavia é pesado. Existe uma opção mais leva que é trocar o "traçado vetorial do PostGIS por traçado na grade". Ver algoritmos, que idealmente seriam convertidos em C:
- Bresenham's line algorithm
- Bresenham's bold line: http://eugen.dedu.free.fr/projects/bresenham/
Ver também
...