algorithm - 展开一个数组

Question

我有一个形成曲线的样本向量。让我们假设其中有 1000 个点。如果我想将其拉伸以填充 1500 个点，那么给出体面结果的最简单算法是什么？我正在寻找只有几行 C/C++ 的东西。

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

谢谢！

Answer 1

这是用于线性和二次插值的 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" );
}

Answer 2

什么是给出体面结果的最简单算法？

Catmull-Rom 样条。（如果你想要平滑的曲线）

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

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

那是假设您正在对可以进行数学插值（浮点数）的数据进行操作。如果无法对数据进行插值（字符串），那么唯一的解决方案是使用旧数组中最近的可用元素。

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

Answer 3

我能想到的最简单的选项只是一个基于平均平均值扩展数组的 fn，所以：

x,y,z

变成

x，平均（x，y），y，平均（y，z），z

如果您需要更多数据点，只需在向量上运行多次即可。