Mudanças entre as edições de "Usuário:Elispf"

Edição das 11h30min de 21 de maio de 2009

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