代码之家 › 专栏 › 技术社区 › twk Mark Adler

展开阵列

curve-fitting interpolation algorithm

twk Mark Adler · 技术社区 · 14 年前

我有一个样本向量,形成一条曲线。让我们想象一下有1000个点在里面。如果我想把它拉伸到1500点,最简单的算法是什么?我正在寻找一些只是C/C++的几行。

我总是想增加向量的大小,新向量的大小可以是当前向量大小的1.1x到50倍。

谢谢!

3 回复 | 直到 14 年前

denis 14 年前

interp1( 5.3, a, n ) 是a[5]+.3*(a[6]-a[5]),从a[5]到a[6]的.3;
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" );
}

SigTerm 14 年前

什么是最简单的算法,可以提供体面的结果?

http://www.mvps.org/directx/articles/catmull/
http://en.wikipedia.org/wiki/Cubic_Hermite_spline

对于每个新项,计算旧数组中的分数位置,使用分数部分(f-楼层(f))作为插值因子,使用“整数”(即楼层(f))部分查找最近的元素。

如果数组中的点分布不均匀,则需要进行一些调整。

mikurski 14 年前

我能想到的最简单的选择就是基于平均值扩展数组的fn,所以:

x、是的,是的

变成

x、平均值(x,y),y,平均值(y,z),z

如果需要更多的数据点,只需在向量上运行多次。