Протягивание массива
У меня есть вектор образцов, которые формируют кривую. Давайте предположим, что существует 1 000 точек в нем. Если я хочу расширить его для заполнения 1 500 точек, каков самый простой алгоритм, который дает достойные результаты? Я ищу что-то, что является всего несколькими строками C/C++.
Я буду всегда хотеть увеличить размер вектора, и новый вектор может быть где угодно от 1.1x к 50x размер текущего вектора.
Спасибо!
3 ответа
Вот C++ для линейной и квадратичной интерполяции.
interp1( 5.3, a, n ) - это a[5] + .3 * (a[6] - a[5]), .3 пути от a[5] до a[6];
interp1array( a, 1000, b, 1500 ) растянет a до b.
interp2( 5.3, a, n ) рисует параболу через 3 ближайшие точки a[4] a[5] a[6]: более плавно, чем interp1, но все равно быстро.
(Сплайны используют 4 ближайшие точки, еще более гладкие; если вы читаете python, см.
basic-spline-interpolation-in-a-few-lines-of-numpy.
// linear, quadratic interpolation in arrays
// from interpol.py denis 2010-07-23 July
#include <stdio.h>
#include <stdlib.h>
// linear interpolate x in an array
// inline
float interp1( float x, float a[], int n )
{
if( x <= 0 ) return a[0];
if( x >= n - 1 ) return a[n-1];
int j = int(x);
return a[j] + (x - j) * (a[j+1] - a[j]);
}
// linear interpolate array a[] -> array b[]
void inter1parray( float a[], int n, float b[], int m )
{
float step = float( n - 1 ) / (m - 1);
for( int j = 0; j < m; j ++ ){
b[j] = interp1( j*step, a, n );
}
}
//..............................................................................
// parabola through 3 points, -1 < x < 1
float parabola( float x, float f_1, float f0, float f1 )
{
if( x <= -1 ) return f_1;
if( x >= 1 ) return f1;
float l = f0 - x * (f_1 - f0);
float r = f0 + x * (f1 - f0);
return (l + r + x * (r - l)) / 2;
}
// quadratic interpolate x in an array
float interp2( float x, float a[], int n )
{
if( x <= .5 || x >= n - 1.5 )
return interp1( x, a, n );
int j = int( x + .5 );
float t = 2 * (x - j); // -1 .. 1
return parabola( t, (a[j-1] + a[j]) / 2, a[j], (a[j] + a[j+1]) / 2 );
}
// quadratic interpolate array a[] -> array b[]
void interp2array( float a[], int n, float b[], int m )
{
float step = float( n - 1 ) / (m - 1);
for( int j = 0; j < m; j ++ ){
b[j] = interp2( j*step, a, n );
}
}
int main( int argc, char* argv[] )
{
// a.out [n m] --
int n = 10, m = 100;
int *ns[] = { &n, &m, 0 },
**np = ns;
char* arg;
for( argv ++; (arg = *argv) && *np; argv ++, np ++ )
**np = atoi( arg );
printf( "n: %d m: %d\n", n, m );
float a[n], b[m];
for( int j = 0; j < n; j ++ ){
a[j] = j * j;
}
interp2array( a, n, b, m ); // a[] -> b[]
for( int j = 0; j < m; j ++ ){
printf( "%.1f ", b[j] );
}
printf( "\n" );
}
Какой самый простой алгоритм дает достойные результаты?
Сплайны Катмулла-Рома. (если вам нужна плавная кривая)
http://www.mvps.org/directx/articles/catmull/
http://en.wikipedia.org/wiki/Cubic_Hermite_spline
Для каждого нового элемента вычислить дробную позицию в старом массиве, использовать дробную часть (f - floor (f)) в качестве коэффициента интерполяции и «целую» (например, floor (f)) часть для поиска ближайших элементов.
Предполагается, что вы работаете с данными, которые можно математически интерполировать (с плавающей точкой). Если данные не могут быть интерполированы (строки), то единственное решение - использовать ближайший доступный элемент старого массива.
Вам потребуется дополнительная настройка, если точки в массиве распределены неравномерно.
Простейший вариант, который я могу придумать, - это просто fn, расширяющая массив на основе средних средних значений, поэтому:
x, y, z
становится
x, avg ( x, y), y, avg (y, z), z
Если вам нужно больше точек данных, просто запустите его несколько раз для вектора.