Как оптимизировать интерполяцию большого набора рассеянных точек? - PullRequest
Новая
       22

Как оптимизировать интерполяцию большого набора рассеянных точек?

2 голосов
/ 10 октября 2011

В настоящее время я работаю с набором координатных точек (долгота, широта, около 60000 из них) и температурой в этом месте.Мне нужно выполнить интерполяцию для них, чтобы вычислить значения в некоторых точках с неизвестной температурой, чтобы отобразить определенные регионы.Что касается уважения влияния точек между ними, я преобразовал каждую (длинную, латинскую) точку в единичную сферу (x, y, z).Я начал применять обобщенную многомерную интерполяцию Шепарда из «Числовых рецептов 3-го издания»: 

Doub interp(VecDoub_I &pt) 
    {
        Doub r, w, sum=0., sumw=0.;
        if (pt.size() != dim) 
            throw("RBF_interp bad pt size");
        for (Int i=0;i<n;i++) 
        {
            if ((r=rad(&pt[0],&pts[i][0])) == 0.) 
                return vals[i];
            sum += (w = pow(r,pneg));
            sumw += w*vals[i];
        }
        return sumw/sum;
    }

    Doub rad(const Doub *p1, const Doub *p2) 
    {
        Doub sum = 0.;
        for (Int i=0;i<dim;i++) 
            sum += SQR(p1[i]-p2[i]);
        return sqrt(sum);
    }

enter image description here Как видите, для интерполяции одной точки алгоритм вычисляет расстояние этой точки докаждый из остальных пунктов и принимая его в качестве веса в конечном значении.Хотя этот алгоритм работает, он слишком медленный по сравнению с тем, что мне нужно, так как я буду вычислять много точек, чтобы отобразить сетку определенного региона.Одним из способов оптимизации этого является то, что я мог бы опустить точки, которые находятся за пределами определенного радиуса, но это создаст проблему для областей с небольшим количеством точек или без них.Другая вещь заключается в том, чтобы уменьшить вычисление расстояния между каждыми 2 точками, вычисляя только один раз справочную таблицу и сохраняя расстояния.Проблема в том, что невозможно хранить такую ​​большую матрицу (60000 x 60000).Полученная сетка температур будет использоваться для расчета контуров для разных значений температуры.Если кто-нибудь знает способ оптимизировать этот алгоритм или, возможно, помочь с лучшим, я буду признателен за это.

Ответы [ 2 ]

1 голос
/ 10 октября 2011

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

Существуют варианты, которые используют Nближайшие соседи и конечная поддержка, чтобы уменьшить количество точек, которые должны учитываться для каждого значения интерполяции.Вариант этого можно найти в первом упомянутом здесь решении Интерполяция с взвешиванием по обратному расстоянию (IDW) с Python .(хотя у меня есть подозрение, что эта реализация может быть прерывистой при определенных условиях - конечно, есть варианты, которые хороши)

0 голосов
/ 10 октября 2011

Ваша справочная таблица не должна хранить каждую точку в квадрате 60 КБ, только те, которые используются повторно. Вы можете отобразить любую координату от x до int(x*resolution), чтобы повысить частоту попаданий путем снижения разрешения.

Аналогичная справочная таблица для функции power также может помочь.

...