Ein Array ausdehnen

Question

Ich habe einen Vektor von Samples, die eine Kurve bilden. Stellen wir uns vor, dass es 1000 Punkte gibt. Wenn ich es strecken möchte, um 1500 Punkte zu füllen, was ist der einfachste Algorithmus, der ordentliche Ergebnisse liefert? Ich suche nach etwas, das nur ein paar Zeilen C/C++ ist.

Ich werde immer die Größe des Vektors erhöhen wollen, und der neue Vektor kann irgendwo von 1,1x bis 50x der Größe des aktuellen Vektors sein.

Danke!

Answer 1

Hier ist C++ für lineare und quadratische Interpolation.
interp1(5.3, a, n) ist ein [5] + .3 * (a [6] - a [5]), .3 des Weges von a [5] nach a [6];
interp1array(a, 1000, b, 1500) würde a zu b dehnen.
interp2(5.3, a, n) zeichnet eine Parabel durch die 3 nächsten Punkte a [4] a [5] a [6]: glatter als interp1, aber immer noch schnell.
(Splines verwenden 4 nächste Punkte, glatter doch,., Wenn Sie Python lesen, sehen 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

Was ist der einfachste Algorithmus, der ordentliche Ergebnisse liefert?

Catmull-Rom-Splines. (Wenn Sie eine glatte Kurve wollen)

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

Für jedes neue Element fraktionalen Position in alten Array berechnen, verwenden verwenden Bruchteil (f - Boden (f)) als Interpolationsfaktor und „integer "(dh Stock (f)) Teil, um die nächsten Elemente zu finden.

Das geht davon aus, dass Sie mit Daten arbeiten, die mathematisch interpoliert werden können (Gleitkommazahlen). Wenn Daten nicht interpoliert werden können (Strings), ist die einzige Lösung, das nächste verfügbare Element des alten Arrays zu verwenden.

Sie müssen etwas optimieren, wenn die Punkte im Array nicht gleichmäßig verteilt sind.

Answer 3

Simplest Option ich denken kann, ist nur eine fn, die das Array basiert auf Mittelwerte erweitert, so:

x, y, z

wird

x, avg (x, y), y, avg (y, z), z

Wenn Sie mehr Datenpunkte benötigen, führen Sie es einfach mehrmals auf dem Vektor.