Usuário:Elispf

De WikiLICC
Revisão de 21h45min de 21 de maio de 2009 por Dago (Discussão | contribs) (O algoritmo quadtree pode ser resumido como segue:)
Ir para: navegação, pesquisa

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:

Quad.jpg


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