Punto Della Sequenza Di Interpolazione

Question

Data una sequenza arbitraria di punti nello spazio, come si fa a produrre un buon continuo di interpolazione tra di loro?

2D e 3D soluzioni sono i benvenuti.Soluzioni che producono un elenco di punti arbitrari di granularità e le soluzioni che producono i punti di controllo per le curve di bezier sono anche apprezzati.

Inoltre, sarebbe bello vedere un iterativo soluzione che potrebbe approssimativa prime sezioni della curva in cui ha ricevuto i punti, in modo che si può disegnare con esso.

Answer 1

La Catmull-Rom spline è garantita per passare attraverso tutti i punti di controllo. Trovo che sia più pratico che cercare di regolare i punti di controllo intermedi per altri tipi di spline.

Questo PDF di Christopher Twigg ha un bella breve introduzione alla matematica della spline. La migliore frase di sintesi è:

  

Le spline Catmull-Rom hanno C1   continuità, controllo locale e   interpolazione, ma non mentire all'interno   lo scafo convesso del loro controllo   punti.

Detto in altro modo, se i punti indicano una forte curva a destra, la spline si inclinerà a sinistra prima di girare a destra (in questo documento c'è un'immagine di esempio). La tenuta di questi diventa controllabile, in questo caso usando il suo parametro tau nella matrice di esempio.

Ecco un altro esempio con un codice DirectX scaricabile.

Answer 2

Un modo è Lagrange polynominal, che è un metodo per produrre una polynominal che passerà attraverso tutti i punti.

Durante il mio primo anno all'università, ho scritto un piccolo strumento per fare questo in 2D, e si può trova su questa pagina, è chiamato Lagrange risolutore.Wikipedia, la pagina è un esempio di implementazione.

Funziona così:si dispone di una di ordine n polynominal, p(x), dove n è il numero di punti che si hanno.Ha la forma a_n x^n + a_(n-1) x^(n-1) + ...+ a_0, dove _ è pedice, ^ è il potere.È quindi trasformare questo in un insieme di equazioni simultanee:

p(x_1) = y_1
p(x_2) = y_2
...
p(x_n) = y_n

La conversione di cui sopra in una matrice aumentata, e risolvere per i coefficienti a_0 ... a_n.Poi si dispone di un polinomio che passa per tutti i punti, e ora è possibile interpolare tra i punti.

Si noti, tuttavia, questo potrebbe non essere adatto per il vostro scopo in quanto offre alcun modo per regolare la curvatura ecc - si sono bloccati con un'unica soluzione che non può essere cambiato.

Answer 3

Dovresti dare un'occhiata a B-splines . Il loro vantaggio rispetto alle curve di Bezier è che ogni parte dipende solo dai punti locali. Quindi spostare un punto non ha alcun effetto su parti della curva che sono lontane, dove & Quot; molto lontano & Quot; è determinato da un parametro della spline.

Il problema con il polinomio di Langrange è che l'aggiunta di un punto può avere effetti estremi su parti apparentemente arbitrarie della curva; non c'è " locality " come descritto sopra.

Answer 4

Hai esaminato il comando Unix spline ? Può essere costretto a fare quello che vuoi?

Answer 5

Esistono diversi algoritmi per interpolare (ed esrapolare) tra un insieme di punti aribtrari (ma finali). Dovresti dare un'occhiata a ricette numeriche , che includono anche implementazioni C ++ di tali algoritmi.

Answer 6

Sfortunatamente il Lagrange o altre forme di interpolazione polinomiale non funzioneranno su una serie arbitraria di punti. Funzionano solo su un set in cui in una dimensione, ad es. x

x _i < x _{i + 1}

Per una serie di punti arbitrari, ad es. una traiettoria di volo in aereo, dove ogni punto è una coppia (longitudine, latitudine), starai meglio semplicemente modellando il viaggio dell'aereo con l'attuale longitudine & amp; latitudine e velocità. Regolando la velocità con cui l'aereo può girare (la sua velocità angolare) a seconda di quanto è vicino al waypoint successivo, è possibile ottenere una curva uniforme.

La curva risultante non sarebbe matematicamente significativa né ti darebbe punti di controllo più bezier. Tuttavia, l'algoritmo sarebbe semplice dal punto di vista computazionale, indipendentemente dal numero di waypoint e potrebbe produrre un elenco interpolato di punti con granularità arbitraria. Inoltre non richiederebbe di fornire il set completo di punti in primo piano, è possibile semplicemente aggiungere waypoint alla fine del set come richiesto.

Answer 7

Ho avuto lo stesso problema e l'ho implementato con alcuni amici l'altro giorno. Mi piace condividere il progetto di esempio su github.

https://github.com/johnjohndoe/PathInterpolation
Sentiti libero di rovesciarlo.

Answer 8

Google " regressione ortogonale " ;.

Mentre le tecniche dei minimi quadrati cercano di minimizzare la distanza verticale tra la linea di adattamento e ciascuna f (x), la regressione ortogonale minimizza le distanze perpendicolari.

Addendum

In presenza di dati rumorosi, vale la pena dare un'occhiata anche al venerabile RANSAC .

Answer 9

Nel mondo della grafica 3D, NURBS è popolare. Ulteriori informazioni sono facilmente disponibili su Google.