DGGS/Cell: mudanças entre as edições
(7 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
Linha 2: | Linha 2: | ||
==Exigência de grade regular== | ==Exigência de grade regular== | ||
O padrão | O padrão [[DGGS]] obriga que a forma das células não varie. Na Matemática a grade (''tesselation'') é um conjunto com ladrilhos (''tiles''), e se vai usar um tipo só de ladrilho, denomina-se a grade de regular. Já há séculos é conhecido pelos matemáticos o fato de não existirem muitas [[wikipedia:Euclidean tilings by convex regular polygons#Regular tilings|opções para se construir uma grade regular]], são apenas '''três formatos de ladrilho''': | ||
{| class="wikitable" | {| class="wikitable" | ||
Linha 8: | Linha 8: | ||
!Forma | !Forma | ||
!Vizinhanças | !Vizinhanças | ||
!Subdivisão | !Subdivisão para [[subpavimentação]] | ||
!Conclusão | |||
|- | |- | ||
|'''Triangular'''<br />3 lados | |'''Triangular'''<br />3 lados | ||
| align="center" | | | align="center" |9 vizinhas (3 por aresta)<br />[[Arquivo:Cell-triangular-neighbors.png|180px]] | ||
|4 partes exatas[[Arquivo:Trangular-subdivision-4.png|centro|semmoldura]] | |4 partes exatas[[Arquivo:Trangular-subdivision-4.png|centro|semmoldura]] | ||
|<big>👎</big> Pior caso de vizinhança (muitas e com apenas 25% por aresta), mas <br/><br/><big>👍</big> pelo menos permite a subdivisão. | |||
|- | |- | ||
|'''Quadrilátero'''<br />4 lados | |'''Quadrilátero'''<br />4 lados | ||
| align="center" | | | align="center" |8 vizinhas (4 por aresta)<br />[[Arquivo:Cell-quadrilateral-neighbors.png|180px]] | ||
|4 partes exatas (ou 2 retangulares)[[Arquivo:Quadrilateral-refinementFactor4.png|centro|semmoldura]] | |4 partes exatas (ou 2 retangulares)[[Arquivo:Quadrilateral-refinementFactor4.png|centro|semmoldura]] | ||
|<big>👍</big> Caso razoável de vizinhança<br/>(poucas e com 50% por aresta), <br/><br/><big>👍</big> subdivisão válida e flexível. | |||
|- | |- | ||
|'''Hexagonal'''<br />6 lados | |'''Hexagonal'''<br />6 lados | ||
| align="center" |6 vizinhas<br />[[Arquivo:Cell-hexagonal-neighbors.png|180px]] | | align="center" |6 vizinhas por aresta<br />[[Arquivo:Cell-hexagonal-neighbors.png|180px]] | ||
|([https://math.stackexchange.com/a/4829230/70274 impossível]) | |([https://math.stackexchange.com/a/4829230/70274 impossível]) | ||
|<big>👍</big> Melhor caso de vizinhança<br/>(100% aresta), mas <br/><br/><big>👎</big> impedimento no requisito da subdivisão. | |||
|} | |} | ||
Considerações: | |||
* Forma: é genérica. Triângulos não precisam ser equiláteros; quadriláteros podem ser losangos, paralelogramas ou retângulos. | |||
* Adjacência: por aresta é preferível à adjacência por vértice. A adjacência refere-se não só à fronteira comum, mas também ao conjunto mais próximo de ladrilhos num raio partindo do centroide. | |||
* Subdivisões: indicando apenas o caso de menor número, que proporcina mais niveis hierárquicos | |||
A adjacência entre células é um importante critério na escolha de grades. Em aplicações que demandam apenas células de um só tamanho (mono-nível), tais como visualização e cálculos, principalmente em aplicações logísticas, o hexágono se sai melhor. Ele tem o menor número total de vizinhaças e todas elas por aresta ([https://www.tandfonline.com/doi/full/10.1080/13658816.2022.2108036 vizinhança isotrópica]). Ver Uber H3. Os [https://www.redblobgames.com/grids/hexagons/ algoritmos hexagonais] são ainda novos e um pouco mais complexos, apesar da boa performance. | |||
Grades quadriláteras e triangulares exibem adjacência não-uniforme porque têm vizinhos de aresta e vértice (Sahr et al. 2003). As grades quadriláteras ainda assim são razoáveis, por apresentarem quantidade menor de adjacências (8 contra 12 do triângulo), com proporção maior de adjacências-por-aresta (50% contra 25% do triângulo). Todos os algoritmos conhecidos (inclusive mais complexos como [[wikipedia:Fast Fourier transform|FFT]] foram primeiramente lançados em grades quadriláteras, de modo que elas possuem amplas bibliotecas e boa performance. | |||
[[Arquivo:DGGS-coverRectangular1.png|miniaturadaimagem|Representação de um polígino (linha preta e área hachurada) por sua ''subpavimentação'', ou seja, através de elementos de um mosaico de retângulos previamente fixado. Em vermelho a ''subpavimentação interior'', sobrepondo a ''subpavimentação com borda'' em amarelo. ]] | |||
Por fim, quando se fala de multifinalidade de uma grade, principalmente em aplicações cadatrais para o governo e dados públicos, é importante a capacidade de "subdivisão para [[subpavimentação]]", onde falha a grade hexagonal. | |||
=== Coberturas não-hexagonais === | |||
Ladrilhos de qualquer formato e um só tamanho podem cobrir uma zona qualquer, mas uma [[subpavimentação]] requer diversos tamanhos, ou seja, ladrilhos de mais de uma grade dentro da mesma cobertura. Apenas ladrilhos triangulares e quadriláteros conseguem subpavimentar. | |||
A '''impossibilidade de uso do hexágono para fins de ''subpavimentação'' foi demonstrada''' [https://math.stackexchange.com/a/4829230/70274 matematicamente e de forma simples por R. Israeal]: | |||
:''"Em um hexágono regular, todos os ângulos medem 120 graus. Se você tiver dois hexágonos regulares de tamanhos diferentes compartilhando parte de um lado, você cria um ângulo de 180−120=60 graus. Não há como ''subpavimentar'' esse setor de 60 graus com um número finito de hexágonos regulares."'' | |||
:[[Arquivo:Hexagono-vao60.png|centro|semmoldura|620px]] | |||
O melhor que se consegue com a subpavimentação hexagonal é a estratégia do Uber H3, de preencher aproximadamente a célula-mãe com 7 células-filhas. O problema dos hexágonos H3 é ilustrado abaixo como subpavimentação errada, e comparado com uma subpavimentação correta: | |||
[[Arquivo:DGGS-coverH3-fail.png|center|580px]] | |||
[[Arquivo:DGGS-coverH3-fail-Detail.png|thumb|Falha que torna inválida a cobertura multi-nível hexagonal. Em destaque as falhas que surgem entre os dois níveis de hexágonos maiores, com lacunas (amarelo) e sobrepoições (vermelho).]] | |||
* INVÁLIDA: o mapa à esquerda (Califórnia) estava coberto por hexágonos de quatro tamanhos diferentes e os hexágonos se sobrepunham. | |||
* VÁLIDA: mapa à direita (Flórida) estava coberto por formas quadriláteras (losangos) de quatro tamanhos diferentes, sem furos e sem sobreposições. Abaixo está um detalhe na Califórnia, destacando os buracos (amarelo) e as sobreposições (vermelho) entre as células maiores. | |||
== Ver também == | |||
* [[DNGS/Geocódigo]] | |||
* [[Subpavimentação]] | |||
* ... | |||
[[Categoria:Discrete Global Grid Systems]] | [[Categoria:Discrete Global Grid Systems]] |
Edição atual tal como às 13h28min de 5 de agosto de 2024
O principal componente do DGGS é a célula, com seu ID. Como o esquema DGGS prevê subdivisões recursivas da célula, podemos dizer que a célula dá origem à grade.
Exigência de grade regular
O padrão DGGS obriga que a forma das células não varie. Na Matemática a grade (tesselation) é um conjunto com ladrilhos (tiles), e se vai usar um tipo só de ladrilho, denomina-se a grade de regular. Já há séculos é conhecido pelos matemáticos o fato de não existirem muitas opções para se construir uma grade regular, são apenas três formatos de ladrilho:
Forma | Vizinhanças | Subdivisão para subpavimentação | Conclusão |
---|---|---|---|
Triangular 3 lados |
9 vizinhas (3 por aresta) |
4 partes exatas | 👎 Pior caso de vizinhança (muitas e com apenas 25% por aresta), mas 👍 pelo menos permite a subdivisão. |
Quadrilátero 4 lados |
8 vizinhas (4 por aresta) |
4 partes exatas (ou 2 retangulares) | 👍 Caso razoável de vizinhança (poucas e com 50% por aresta), 👍 subdivisão válida e flexível. |
Hexagonal 6 lados |
6 vizinhas por aresta |
(impossível) | 👍 Melhor caso de vizinhança (100% aresta), mas 👎 impedimento no requisito da subdivisão. |
Considerações:
- Forma: é genérica. Triângulos não precisam ser equiláteros; quadriláteros podem ser losangos, paralelogramas ou retângulos.
- Adjacência: por aresta é preferível à adjacência por vértice. A adjacência refere-se não só à fronteira comum, mas também ao conjunto mais próximo de ladrilhos num raio partindo do centroide.
- Subdivisões: indicando apenas o caso de menor número, que proporcina mais niveis hierárquicos
A adjacência entre células é um importante critério na escolha de grades. Em aplicações que demandam apenas células de um só tamanho (mono-nível), tais como visualização e cálculos, principalmente em aplicações logísticas, o hexágono se sai melhor. Ele tem o menor número total de vizinhaças e todas elas por aresta (vizinhança isotrópica). Ver Uber H3. Os algoritmos hexagonais são ainda novos e um pouco mais complexos, apesar da boa performance.
Grades quadriláteras e triangulares exibem adjacência não-uniforme porque têm vizinhos de aresta e vértice (Sahr et al. 2003). As grades quadriláteras ainda assim são razoáveis, por apresentarem quantidade menor de adjacências (8 contra 12 do triângulo), com proporção maior de adjacências-por-aresta (50% contra 25% do triângulo). Todos os algoritmos conhecidos (inclusive mais complexos como FFT foram primeiramente lançados em grades quadriláteras, de modo que elas possuem amplas bibliotecas e boa performance.
Por fim, quando se fala de multifinalidade de uma grade, principalmente em aplicações cadatrais para o governo e dados públicos, é importante a capacidade de "subdivisão para subpavimentação", onde falha a grade hexagonal.
Coberturas não-hexagonais
Ladrilhos de qualquer formato e um só tamanho podem cobrir uma zona qualquer, mas uma subpavimentação requer diversos tamanhos, ou seja, ladrilhos de mais de uma grade dentro da mesma cobertura. Apenas ladrilhos triangulares e quadriláteros conseguem subpavimentar.
A impossibilidade de uso do hexágono para fins de subpavimentação foi demonstrada matematicamente e de forma simples por R. Israeal:
- "Em um hexágono regular, todos os ângulos medem 120 graus. Se você tiver dois hexágonos regulares de tamanhos diferentes compartilhando parte de um lado, você cria um ângulo de 180−120=60 graus. Não há como subpavimentar esse setor de 60 graus com um número finito de hexágonos regulares."
O melhor que se consegue com a subpavimentação hexagonal é a estratégia do Uber H3, de preencher aproximadamente a célula-mãe com 7 células-filhas. O problema dos hexágonos H3 é ilustrado abaixo como subpavimentação errada, e comparado com uma subpavimentação correta:
- INVÁLIDA: o mapa à esquerda (Califórnia) estava coberto por hexágonos de quatro tamanhos diferentes e os hexágonos se sobrepunham.
- VÁLIDA: mapa à direita (Flórida) estava coberto por formas quadriláteras (losangos) de quatro tamanhos diferentes, sem furos e sem sobreposições. Abaixo está um detalhe na Califórnia, destacando os buracos (amarelo) e as sobreposições (vermelho) entre as células maiores.