Estensione di un array

Question

Ho un vettore di campioni che formano una curva. Immaginiamo che ci siano 1000 punti in esso. Se voglio allungarlo per riempire 1500 punti, qual è l'algoritmo più semplice che dà risultati decenti? Sto cercando qualcosa che è solo poche righe di C/C++.

Desidero sempre aumentare la dimensione del vettore e il nuovo vettore può essere ovunque da 1,1x a 50 volte la dimensione del vettore corrente.

Grazie!

Answer 1

Ecco il C++ per l'interpolazione lineare e quadratica.
interp1(5.3, a, n) è un [5] + .3 * (a [6] - a [5]), .3 del percorso da un [5] a un [6];
interp1array(a, 1000, b, 1500) estendere a a b.
interp2(5.3, a, n) disegna una parabola attraverso i 3 punti più vicini a [4] a [5] a [6]: più agevole di interp1 ma ancora veloce.
(Spline utilizzare 4 punti più vicini, più liscia ancora,. Se leggete pitone, vedere 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

qual è l'algoritmo più semplice che offre risultati decenti?

spline Catmull-Rom. (Se si desidera una curva regolare)

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

Per ogni nuovo elemento calcolare la posizione frazionale nella vecchia matrice, uso utilizzare una parte frazionaria (F - piano (f)) come fattore di interpolazione, e "integer "(es. floor (f)) per trovare gli elementi più vicini.

Ciò presuppone che si stia operando su dati che possono essere interpolati matematicamente (float). Se i dati non possono essere interpolati (stringhe), l'unica soluzione è utilizzare l'elemento disponibile più prossimo del vecchio array.

Avrete bisogno di qualche ritocco se i punti nell'array non sono equamente distribuiti.

Answer 3

opzione più semplice che posso pensare è solo un fn che espande la matrice in base alle medie medi, quindi:

x, y, z

diventa

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

Se sono necessari più punti dati, è sufficiente eseguirlo più volte sul vettore.