Эффективный метод интерполяции для неструктурированных сеток?

Я хотел бы знать хороший метод для интерполяции данных между двумя неструктурированными сетками, где одна сетка является более грубой версией другой.

Эффективность очень важна для меня, так как я решаю переходную проблему PDE, где мне нужно передавать данные между сетками на каждом временном шаге решения.

Я думал об использовании kd-дерева для поиска ближайшего узла данной точки, затем я использовал функции формы этого элемента (FEM-симуляция) для интерполяции данных. Это хорошее решение? Есть лучшие?

Вам также известна надежная и надежная библиотека на C / C ++ для этой задачи?

* Я знаю, что есть похожий вопрос, но он требует наиболее точного метода на структурированной сетке.

Неструктурированные сетки имеют свое место.

Возможно, вы захотите взглянуть на структуру моделирования системы Земли (ESMF). У них есть некоторый код для повторного создания сетки - специально для этой цели - и они также сделали некоторые изящные вещи с параллельным кодом. Вся система предназначена для объединения моделей, поэтому там могут быть и другие полезные вещи.

Некоторые другие заметки:

«нет способа сделать это эффективно для любого значительного количества очков»

Что ж, эффективность - это относительная вещь: если у вас есть сетка в древовидной структуре, вы можете искать ее в O (logn), что может быть чертовски быстрым, хотя и не O (1), как поиск в регулярной сетке является.

Кроме того, похоже, что в то время как интерполяция должна выполняться на каждом временном шаге, если сетки не адаптируются, то отображение из одной сетки в другую остается постоянным. Таким образом, вы можете вычислить это отображение (то есть, какой элемент в каждой сетке соответствует какому элементу в другом) любым удобным способом, сохранить его, и тогда вам никогда не потребуется вычислять его снова (до тех пор, пока сетки не изменятся).

Таким образом, у вас остается код интерполяции, где вы захотите сбалансировать точность и производительность. Простая линейная интерполяция по треугольнику быстра и может быть достаточно хорошей.

«Я думал об использовании дерева kd для поиска ближайшего узла данной точки, тогда я использовал бы функции формы этого элемента»

помните, что ближайший узел не дает вам элемент - поэтому вы захотите сделать немного больше, чтобы найти нужный элемент. Один из вариантов - вместо этого использовать rtree, которое хранит / выполняет поиск с помощью ограничивающего прямоугольника - при каждом поиске вы получите более одного элемента, но затем вы можете проверить, какой из них является правильным.

Если я вас правильно понимаю, вы хотите заполнить значения более мелкой сетки путем интерполяции по более грубой сетке. Один из способов сделать линейную интерполяцию на неструктурированной сетке - триангуляции Делоне (именно так реализованы команды Matlab griddata и TriScatteredInterp). После построения триангуляции точек сетки интерполяция сводится к поиску треугольника, содержащего целевую точку, вычислению его барицентрических координат и использованию значений функции в вершинах для вычисления интерполированного значения. CGAL может создавать n-мерные триангуляции (для среды n), а также имеет встроенный модуль 2D-интерполяции .

Это то, чем я сейчас занимаюсь, за исключением того, что я передаю значения функций в квадратурных точках, а не в узлах. Я реализую методику, описанную в выбранном ответе на мой вопрос здесь: нахождение точек треугольников .

$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))$

Это та работа, для которой вы действительно хотите избежать неструктурированных сеток, поскольку нет способа сделать это эффективно для любого значительного количества баллов. Вы должны рассмотреть возможность использования сеток, которые хотя бы как-то связаны с каждой из них. Например, если они оба получены из иерархического уточнения грубой сетки, то вы можете относительно легко и эффективно выяснить, где точки интерполяции одной сетки расположены на другой сетке.