Многомерная интерполяция

Question

Учитывая набор данных сэмплов в многомерном пространстве (в моем случае это 4D-пространство), где сэмплы присутствуют во всех углах 4D-куба и значительное количество сэмплов в этом кубе, но не в аккуратной сетке. Каждый образец имеет выходное значение рядом с его 4D-координатой. Куб имеет координаты [0,0,0,0] .. [1,1,1,1].

Учитывая новую координату (4D), как я могу получить лучшее интерполированное значение, учитывая эти выборки? Например, как выбрать сэмплы для начала, как интерполировать.

В качестве первого предположения я бы предположил, что это можно сделать с помощью двухэтапного процесса:

1. найдите наименьший выпуклый пентахорон (четырехмерный эквивалент трехмерного тетраэдра / двумерного треугольника) вокруг координаты, которую мы должны интерполировать.

2. интерполировать внутри этого тетраэдра.

Особенно шаг 1 кажется довольно сложным и медленным.

Answer 1

Вот первый подход, который я бы попробовал.

Шаг 1

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

Если проверки ближайших соседей слишком медленные, попробуйте структурировать ваши данные в дерево пространственного поиска, которое работает в 4D.

Шаг 2

Теперь нам нужно связать значение с точкой интерполяции X. Начнем с получения представления X в этой новой барицентрической системе координат. Эта барицентрическая координата состоит из 4 чисел, которые в совокупности описывают относительное расстояние между точкой интерполяции и каждой из вершин 4-симплекса.

Нормализовать барицентрическую координату, чтобы ее составляющие составляли 1.

Каждая из этих 4 симплексных вершин является точками данных и имеет выходное значение. Объедините эти 4 выходных значения в вектор.

Наконец, выполните интерполяцию путем вычисления точечного произведения нормализованной координаты с вектором выходных значений.

Источник: Эта идея на самом деле является только 4D расширением этого драгоценного камня в середине страницы Барицентрической системы координат в Википедии.