Subpavimentação
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 s2.sidewalklabs.com/regioncoverer 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.