Método de interpolação eficiente para redes não estruturadas?

12

Gostaria de conhecer um bom método para interpolar dados entre duas grades não estruturadas, onde uma grade é uma versão mais grossa da outra.

A eficiência é muito importante para mim, pois estou resolvendo um problema temporário de PDE em que preciso transferir dados entre as grades a cada etapa da solução.

Pensei em usar o kd-tree para pesquisar o nó mais próximo de um determinado ponto; depois, usaria as funções de forma desse elemento (simulação FEM) para interpolar os dados. Esta é uma boa solução? Existem melhores?

Você também conhece alguma biblioteca robusta e confiável em C / C ++ para esta tarefa?

* Eu sei que existe uma pergunta semelhante, mas solicita o método mais preciso em uma grade estruturada.

Bernardo MR
fonte
ver esse bando Q & A, eu coletei de métodos de código aberto para isso: scicomp.stackexchange.com/questions/19137/...
denfromufa

Respostas:

6

Grades não estruturadas têm seu lugar.

Você pode consultar a ESMF (Earth System Modeling Framework). Eles têm algum código para reorganizar - especificamente para esse fim - e também fizeram algumas coisas bacanas com código paralelo. Todo o sistema foi projetado para acoplar modelos, portanto também pode haver outras coisas úteis.

Algumas outras notas:

"nenhuma maneira de fazer isso de forma eficiente para um número significativo de pontos"

bem, eficiente é uma coisa relativa - uma vez que você tenha a grade em uma estrutura de árvore, poderá pesquisá-la em O (logn), que pode ser bem rápido, embora não em O (1), como pesquisar em uma grade regular é.

Além disso, parece que enquanto a interpolação precisa ser feita a cada passo, se as grades não estiverem se adaptando, o mapeamento de uma grade para outra permanece constante. Portanto, você pode calcular esse mapeamento (ou seja, qual elemento em cada grade corresponde a qual elemento na outra) da maneira que for mais conveniente, armazená-lo e nunca mais precisar computá-lo novamente (até que as grades mudem).

Isso deixa você com o código de interpolação - onde você deseja equilibrar precisão e desempenho - a interpolação linear simples através de um triângulo é rápida e pode ser boa o suficiente.

"Pensei em usar o kd-tree para pesquisar o nó mais próximo de um determinado ponto, então usaria as funções de forma desse elemento"

lembre-se de que o nó mais próximo não recebe o elemento - então você precisará fazer um pouco mais para encontrar o elemento que deseja. Uma opção seria usar uma rtree, que armazena / pesquisa por caixa delimitadora - você obterá mais de um elemento a cada pesquisa, mas poderá verificar qual deles está correto diretamente.

Chris Barker
fonte
Isso parece legal. Como não preciso adaptar as malhas, o mapeamento de uma grade para outra será feito apenas uma vez. Obrigado pela dica sobre a estrutura de dados r-tree.
Bernardo MR
1
O(N)O(logN)
7

Se eu entendi direito, você deseja preencher os valores da grade mais fina interpolando na grade mais grossa. Uma maneira de fazer interpolação linear em uma grade não estruturada é com as triangulações de Delaunay (é assim que os comandos griddata e TriScatteredInterp do Matlab são implementados). Depois de construir uma triangulação dos pontos da grade, a interpolação se resume a localizar o triângulo que contém o ponto de destino, calculando suas coordenadas baricêntricas e usando os valores da função nos vértices para calcular o valor interpolado. CGAL pode construir triangulações n-dimensionais (para o meio n) e também possui um módulo de interpolação 2d interno .

Ronaldo Carpio
fonte
Sim. Mas também quero "injetar" os valores da grade fina na grade grossa também, por isso disse transferência.
Bernardo MR
3

É o que estou fazendo no momento, exceto que estou transferindo valores de função em pontos de quadratura, não em nós. Estou implementando a técnica explicada na resposta escolhida para minha pergunta aqui: Descobrindo quais pontos dos triângulos estão .

ABAB

  1. BpiA
  2. pi
  3. AA
  4. Ap1p2p3A

NMAO(NM)O(max(N,M))

Nick Alger
fonte
2

Esse é o tipo de trabalho para o qual você realmente deseja evitar malhas não estruturadas, pois não há como fazer isso de forma eficiente para um número significativo de pontos. Você deve considerar o uso de malhas que sejam pelo menos de alguma forma relacionadas a cada uma. Por exemplo, se ambos forem obtidos a partir do refinamento hierárquico de uma malha grossa, você poderá descobrir de maneira relativamente fácil e eficiente onde os pontos de interpolação de uma malha estão localizados na outra malha.

Wolfgang Bangerth
fonte
Eu acho que essa pode ser a melhor opção (hierarquia de grades). Se for esse o caso, você conhece alguma boa estrutura de dados ou método específico para usar?
Bernardo MR
Sim, as malhas hierárquicas são todas armazenadas como árvores quad / oct (se iniciarem em uma única célula grossa) ou florestas dessas árvores (se a malha grossa tiver mais de uma vez a célula).
Wolfgang Bangerth