Usuário:Elispf
QUADTREE
Grades QUADTREE são grades retangulares bidimensionais que são geradas pela subdivisão recursiva do domínio, onde cada subdivisão gera quatro novos retângulos. Ou ainda, estrutura de dados QUADTREE é uma árvore onde cada nó possui no máximo quatro filhos, como ilustra a figura abaixo:
Alguns termos importantes:
- Pontos sementes: pontos sobre os quais a grade quadtree é gerada.
- Pai: painel ou retângulo dividido para gerar filhos.
- Filhos ou crianças: painéis resultantes da divisão do painel pai.
- Folha: painel não dividido.
O algoritmo quadtree pode ser resumido como segue:
1. Defina o conjunto de pontos sementes da fronteira, <math>P_n</math>, sobre o qual a grade será gerada.
2. Defina o quadrado unitário ou retângulo (painel raiz) que cerca o domínio de interesse.
3. Divida o painel raiz em quatro painéis.
4. Considere cada painel: se o painel contém mais de dois pontos, continue com (5), caso contrário confira o próximo painel.
5. Confira se o nível de divisão máxima, <math>M_{max}</math>, foi atingido. Nesse caso, a divisão do painel em questão está completa, desta forma volte para (4) e confira o próximo painel. Quando todos os painéis considerados alcançarem a divisão máxima,<math>M_{max}</math>, , ou possuírem pelo menos três pontos, a geração de malha está completa. Caso contrário continue.
6. Divida o painel em quatro painéis correspondentes, retorne para (4) e verifique o próximo painel.
Algumas funções que talvez sejam necessárias para auxiliar na construção do algoritmo através de estrutura de dados:
- Gerar árvore: criação e manipulação da árvore
- Conferir condições de refinamento
- Encontrar vizinhos de cada painel – ida e volta
- Estrutura do nó
- Adição e remoção de nós – no caso de refinamento, por exemplo
- Interpolação
