У меня есть вектор образцов, которые образуют кривую. Представим, что в нем 1000 точек. Если я хочу растянуть его до заполнения 1500 точек, какой самый простой алгоритм дает достойные результаты? Я ищу что-то, что представляет собой всего несколько строк C/C++.
Я всегда буду хотеть увеличить размер вектора, и новый вектор может быть от 1,1x до 50x размера текущего вектора.
Спасибо!
Вот C++ для линейной и квадратичной интерполяции.interp1( 5.3, a, n ) равно a[5] + .3 * (a[6] - a[5]), .3 пути от a[5] до a[6];< br> interp1array( a, 1000, b, 1500 ) растянет a до b.interp2( 5.3, a, n ) рисует параболу через 3 ближайшие точки a[4] a[5] a[6]: более плавно, чем interp1, но все равно быстро.
(сплайны используют 4 ближайшие точки , еще более гладко; если вы читали Python, см. базовая-сплайн-интерполяция-в-несколько-строк-из-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/< br> http://en.wikipedia.org/wiki/Cubic_Hermite_spline
Для каждого нового элемента вычислите дробную позицию в старом массиве, используйте дробную часть (f - пол (f)) в качестве коэффициента интерполяции и «целую» (т.е. пол (f)) часть, чтобы найти ближайшие элементы.
Это предполагает, что вы работаете с данными, которые могут быть математически интерполированы (с плавающей запятой). Если данные не могут быть интерполированы (строки), то единственным решением является использование ближайшего доступного элемента старого массива.
Вам потребуется некоторая настройка, если точки в массиве распределены неравномерно.
Самый простой вариант, который я могу придумать, - это просто fn, который расширяет массив на основе средних значений, поэтому:
x,y,z
становится
х, среднее (х, у), у, среднее (у, г), г
Если вам нужно больше точек данных, просто запустите его несколько раз на векторе.
