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