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és. 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çaram a divisão máxima,$M_{max}$, ou possuem pelo menos três pontos, a geração de malha é concluída. Caso contrário continue. 6. Divida o painel em quatro painéis correspondentes, retorne para (4) e verifique o próximo painel.
Idéias de funções necessárias para auxiliar na construção do algoritmo através de estrutura de dados em árvore a. Gerar árvore: criação e manipulação da árvore b. Conferir condições de refinamento c. Encontrar vizinhos de cada painel – ida e volta d. Estrutura do nó e. Adição e remoção de nós – no caso de refinamento, por exemplo f. Interpolação
