Subpavimentação

De Documentação
Ilustrando em vermelho a subpavimentação menor (interior), que estaria sobrepondo a subpavimentação maior (com borda) em amarelo.
Aneis representados por cobertura equilibrada, entre a menor e a maior.

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":

  1. 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.
  1. 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.
  1. ... 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.
Osmc-coverBR-byGeohashes.png

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

Mosaicos são compostos de ladrilhos, seguindo um padrão qualquer, regular ou irregular.
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.

Mosaic-voronoi-andIndex-subpav-hierarchy.png

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

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:


Ver também

...

Disponível em “https://wiki.addressforall.org/w/index.php?title=Subpavimentação&oldid=3782”