Méthode d'interpolation efficace pour les grilles non structurées?

Je voudrais connaître une bonne méthode pour interpoler des données entre deux grilles non structurées, où une grille est une version plus grossière de l'autre.

L'efficacité est très importante pour moi car je résous un problème PDE transitoire où je dois transférer des données entre les grilles à chaque étape de la solution.

J'ai pensé à utiliser kd-tree pour rechercher le nœud le plus proche d'un point donné, puis j'utiliserais les fonctions de forme de cet élément (simulation FEM) pour interpoler les données. Est-ce une bonne solution? Y en a-t-il de meilleurs?

Connaissez-vous également une bibliothèque robuste et fiable en C / C ++ pour cette tâche?

* Je sais qu'il y a une question similaire, mais elle demande la méthode la plus précise sur une grille structurée.

Les grilles non structurées ont leur place.

Vous voudrez peut-être regarder le cadre de modélisation du système terrestre (ESMF). Ils ont du code pour le re-maillage - spécifiquement à cet effet - et ils ont également fait des trucs astucieux avec du code parallèle. L'ensemble du système est conçu pour coupler des modèles, il peut donc y avoir également d'autres éléments utiles.

Quelques autres notes:

"aucun moyen de le faire efficacement pour un nombre significatif de points"

eh bien, efficace est une chose relative - une fois que vous avez la grille dans une structure arborescente, vous pouvez la rechercher dans O (logn), qui peut être assez rapide, mais pas O (1), comme la recherche d'une grille régulière est.

En outre, il semble que l'interpolation doive être effectuée à chaque pas de temps, si les grilles ne s'adaptent pas, le mappage d'une grille à l'autre reste constant. Ainsi, vous pouvez calculer ce mappage (c'est-à-dire quel élément dans chaque grille correspond à quel élément dans l'autre) de la manière qui vous convient, le stocker, puis vous n'avez jamais besoin de le calculer agin (jusqu'à ce que les grilles changent).

Cela vous laisse avec le code d'interpolation - où vous voudrez équilibrer la précision avec les performances - une simple interpolation linéaire à travers un triangle est rapide et peut être suffisante.

"J'ai pensé à utiliser kd-tree pour rechercher le nœud le plus proche d'un point donné, puis j'utiliserais les fonctions de forme de cet élément"

rappelez-vous que le nœud le plus proche ne vous obtient pas l'élément - vous voudrez donc faire un peu plus pour trouver l'élément que vous voulez. Une option serait d'utiliser à la place un rtree, qui stocke / recherche par boîte englobante - vous obtiendrez plus d'un élément à chaque recherche, mais vous pouvez ensuite vérifier lequel est correct directement.

Si je vous comprends bien, vous voulez remplir les valeurs de la grille plus fine en interpolant sur la grille plus grossière. Une façon de faire une interpolation linéaire sur une grille non structurée est avec les triangulations de Delaunay (c'est ainsi que les commandes Griddata et TriScatteredInterp de Matlab sont implémentées). Après avoir construit une triangulation de vos points de grille, l'interpolation se résume à localiser le triangle contenant le point cible, à calculer ses coordonnées barycentriques et à utiliser les valeurs de fonction aux sommets pour calculer la valeur interpolée. CGAL peut construire des triangulations à n dimensions (pour n moyen), et dispose également d'un module d' interpolation 2D intégré.

C'est ce que je fais en ce moment, sauf que je transfère des valeurs de fonction aux points de quadrature, pas aux nœuds. J'implémente ici la technique expliquée dans la réponse choisie à ma question: trouver les points triangles .

$A$$B$$A$$B$

1. $B$$p_i$$A$
2. $p_i$
3. $A$$A$
4. $A$$p_1$$p2$$p3$$A$

$N$$M$$A$$O(N \sqrt{M})$$O(max(N,M))$

C'est le genre de travail pour lequel vous voulez vraiment éviter les maillages non structurés car il n'y a aucun moyen de le faire efficacement pour un nombre significatif de points. Vous devriez envisager d'utiliser des maillages qui sont au moins en quelque sorte liés à chacun. Par exemple, s'ils sont tous les deux obtenus à partir du raffinement hiérarchique d'un maillage grossier, vous pouvez déterminer relativement facilement et efficacement où se trouvent les points d'interpolation d'un maillage sur l'autre maillage.