Skuteczna metoda interpolacji dla nieustrukturyzowanych siatek?

Chciałbym poznać dobrą metodę interpolacji danych między dwiema nieustrukturyzowanymi siatkami, gdzie jedna siatka jest grubszą wersją drugiej.

Wydajność jest dla mnie bardzo ważna, ponieważ rozwiązuję przejściowy problem PDE, w którym muszę przesyłać dane między sieciami na każdym etapie rozwiązania.

Myślałem o użyciu drzewa kd do wyszukiwania najbliższego węzła danego punktu, a następnie użyłem funkcji kształtu tego elementu (symulacja MES) do interpolacji danych. Czy to dobre rozwiązanie? Czy są lepsze?

Czy znasz także solidną i niezawodną bibliotekę w C / C ++ do tego zadania?

* Wiem, że istnieje podobne pytanie, ale wymaga ono najdokładniejszej metody na siatce strukturalnej.

Nieustrukturyzowane siatki mają swoje miejsce.

Możesz przyjrzeć się modelowi Earth System Modeling Framework (ESMF). Mają trochę kodu do zmiany siatki - specjalnie do tego celu - i zrobili kilka fajnych rzeczy z równoległym kodem. Cały system jest zaprojektowany do łączenia modeli, więc mogą tam być również inne przydatne rzeczy.

Inne uwagi:

„nie da się tego zrobić skutecznie dla żadnej znaczącej liczby punktów”

cóż, wydajność jest względna - gdy już masz siatkę w strukturze drzewa, możesz ją przeszukiwać w O (logn), który może być dość cholernie szybki, choć nie w O (1), jak przeszukiwanie zwykłej siatki jest.

Wygląda na to, że interpolacja musi być wykonywana na każdym kroku, jeśli siatki nie dostosowują się, mapowanie z jednej siatki na drugą pozostaje stałe. Możesz więc obliczyć to odwzorowanie (tj. Który element w każdej siatce odpowiada, który element w drugim) w dowolny dogodny sposób, zapisz go, a potem nigdy nie będziesz musiał obliczać go ponownie (dopóki siatki się nie zmienią).

To pozostawia kod interpolacyjny - w którym chcesz zrównoważyć dokładność z wydajnością - prosta interpolacja liniowa w trójkącie jest szybka i może być wystarczająca.

„Myślałem o użyciu drzewa kd do wyszukiwania najbliższego węzła danego punktu, a następnie użyłbym funkcji kształtu tego elementu”

pamiętaj, że najbliższy węzeł nie daje ci elementu - więc będziesz musiał zrobić coś więcej, aby znaleźć pożądany element. Jedną z opcji byłoby użycie zamiast tego rtree, który przechowuje / wyszukuje, ograniczając ramkę - przy każdym wyszukiwaniu otrzymasz więcej niż jeden element, ale możesz następnie sprawdzić, który z nich jest poprawny bezpośrednio.

Jeśli dobrze cię rozumiem, chcesz wypełnić wartości drobniejszej siatki, interpolując ją na grubszej siatce. Jednym ze sposobów wykonania interpolacji liniowej na nieustrukturyzowanej siatce są triangulacje Delaunaya (w ten sposób zaimplementowane są dane gridla Matlaba i polecenia TriScatteredInterp). Po zbudowaniu triangulacji punktów siatki interpolacja sprowadza się do zlokalizowania trójkąta zawierającego punkt docelowy, obliczenia jego współrzędnych barycentrycznych i użycia wartości funkcji w wierzchołkach do obliczenia wartości interpolowanej. CGAL może konstruować trójwymiarowe triangulacje (dla ośrodka n), a także ma wbudowany moduł interpolacji 2D .

Właśnie to robię w tej chwili, z tym wyjątkiem, że przesyłam wartości funkcji w punktach kwadraturowych, a nie węzłach. Realizuję technikę objaśnioną w wybranej odpowiedzi na moje pytanie tutaj: Znajdowanie, w których punktach są trójkąty .

Zasadniczo powiedzmy, że masz 2 siatki i i chcesz przenieść informacje z siatki do siatkiB A $A$$B$$A$$B$

1. Na podstawie punktów węzłowych lub kwadraturowych na siatce listę punktów które zostaną ocenione na siatce ,p i$B$$p_i$$A$
2. uporządkować punkty oceny na podstawie krzywej Hilberta,$p_i$
3. skonstruuj ograniczone rozszerzenie Delaunaya siatki (wszystkie trójkąty w , plus kilka zewnętrznych trójkątów, aby kształt był wypukły)$A$$A$
4. zaczynając od trójkąta w rozszerzonej wersji , chodź losowo z trójkąta do trójkąta „w ogólnym kierunku” punktu aż do niego dojdziesz. Następnie idź dalej do , itd., Aż , które trójkąty w zawierają wszystkie punkty oceny.p 1 p 2 p 3 $A$$p_1$$p2$$p3$$A$

Jeśli masz punktów oceny i trójkątów w rozszerzonej wersji , a jeśli zignorujesz porządkowanie krzywej Hilberta i pójdziesz deterministycznie, najgorszym przypadkiem może być czas . Uwzględniając uporządkowanie krzywej Hilberta i chodzenie z przypadkowością, widzę w praktyce znacznie bardziej wydajne wyniki, bardziej jak .M A O ( N $N$$M$$A$O(max(N,M)$O(N \sqrt{M})$$O(max(N,M))$

Jest to rodzaj pracy, dla którego naprawdę chcesz uniknąć nieustrukturyzowanych siatek, ponieważ nie ma sposobu, aby wykonać to skutecznie dla dowolnej znacznej liczby punktów. Należy rozważyć użycie siatek, które są przynajmniej w jakiś sposób powiązane z każdą z nich. Na przykład, jeśli oba są uzyskane z hierarchicznego udoskonalenia grubej siatki, wówczas można stosunkowo łatwo i skutecznie dowiedzieć się, gdzie znajdują się punkty interpolacji jednej siatki na drugiej siatce.