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

De WikiLICC
Ir para: navegação, pesquisa
m
 
(13 revisões intermediárias por 2 usuários não estão sendo mostradas)
Linha 1: Linha 1:
'''QUADTREE'''
+
* Coloque aqui o que você acha que são as funções necessárias para o algoritmo Quadtree e um pequeno resumo do que você entendeu até agora.
 +
 
 +
==Links==
 +
* [[Malha]] não uniforme
 +
 
 +
==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:
 
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:
  
 +
[[Imagem:Quad.jpg]]
  
  
Alguns termos importantes:
+
===Alguns termos importantes:===
 
*Pontos sementes: pontos sobre os quais a grade quadtree é gerada.
 
*Pontos sementes: pontos sobre os quais a grade quadtree é gerada.
 
*Pai: painel ou retângulo dividido para gerar filhos.
 
*Pai: painel ou retângulo dividido para gerar filhos.
Linha 10: Linha 17:
 
*Folha: painel não dividido.
 
*Folha: painel não dividido.
  
O  algoritmo quadtree pode ser resumido como segue:
+
===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.
+
# Defina o conjunto de pontos sementes da fronteira, <math>P_n</math>, sobre o qual a grade será gerada.
3.  Divida o painel raiz em quatro painés.
+
# Defina o quadrado unitário ou retângulo (painel raiz) que cerca o domínio de interesse.
4. Considere cada painel: se o painel contém mais de dois pontos, continue com (5), caso contrário confira o próximo painel.
+
# Divida o painel raiz em quatro painéis.
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.
+
# Considere cada painel: se o painel contém mais de dois pontos, continue com (5), caso contrário confira o próximo painel.
6. Divida o painel em quatro painéis correspondentes, retorne para (4) e verifique o próximo painel.
+
# 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.
 +
# 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
+
===Funções Importantes===
a. Gerar árvore: criação e manipulação da árvore
+
Algumas funções que talvez sejam necessárias para auxiliar na construção do algoritmo através de estrutura de dados:
b. Conferir condições de refinamento
+
* Gerar árvore: criação e manipulação da árvore
c. Encontrar vizinhos de cada painel – ida e volta
+
* Conferir condições de refinamento
d. Estrutura do nó
+
* Encontrar vizinhos de cada painel – ida e volta
e. Adição e remoção de nós – no caso de refinamento, por exemplo
+
* Estrutura do nó
f. Interpolação
+
* Adição e remoção de nós – no caso de refinamento, por exemplo
 +
* Interpolação

Edição atual tal como às 11h27min de 26 de junho de 2009

  • Coloque aqui o que você acha que são as funções necessárias para o algoritmo Quadtree e um pequeno resumo do que você entendeu até agora.

Links

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.

Funções Importantes

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