2012-07-17 13 views
7

Quindi ho un set speciale di spline cubiche, i cui punti di controllo 2d generano sempre una curva che non si incrocerà mai nell'asse x . Cioè, le curve sembrano essere una semplice funzione polinomiale tale che y = f (x). Voglio creare in modo efficiente una serie di coordinate e lungo la spline che corrispondono a coordinate x uniformemente distribuite che eseguono la lunghezza del segmento spline.Trasforma la funzione spline 2d f (t) in f (x)

voglio trovare efficientemente y coordinate lungo la spline dove, per esempio, x = 0.0, x = 0,1, x = 0.2, ecc, o avvicinato un altro modo, trasformare efficacemente il f x, y ( t) funzione di stile in una funzione f ( x).

Attualmente sto usando un 4x4 costante matrice e quattro punti di controllo 2d per descrivere la spline, usando le costanti di matrice sia per Hermite o Catmull-Rom spline e collegandoli una funzione cubica di t che va da 0 a 1.

Data la matrice e i punti di controllo, qual è il modo migliore per ottenere questi valori Y sull'asse x?

MODIFICA: Devo aggiungere che un'approssimazione abbastanza buona da disegnare è sufficiente.

+1

Il metodo più semplice che ho trovato finora è solo prendere un campione di punti dalla curva a intervalli regolari di t, quindi interpolare tra quelli lungo l'asse x per raccogliere i valori f (x). Questo sembra ok per la maggior parte del tempo, ma a volte manca i dettagli, perché è difficile sapere dove si trovano gli spigoli; l'aumento della frequenza di campionamento aiuta, ma non è esattamente efficiente né soddisfacente. Sono sicuro che c'è un modo intelligente che è efficiente dal punto di vista computazionale e non perde i dettagli. – vercellop

+0

@vervellop, con la domanda modificata, il tuo approccio attuale potrebbe essere la risposta migliore, quindi ti suggerisco di postarlo come risposta, quindi alla fine puoi accettarlo se non si presenta nulla di meglio. E gli utenti possono revocarlo se lo considerano una soluzione buona/appropriata a questo problema. – MvG

+0

Ci potrebbe essere una contraddizione nella tua domanda: la domanda originale richiede coordinate * x * uniformemente spaziate, mentre la modifica richiede una soluzione adatta per il disegno. In presenza di cuspidi pronunciate, un campionamento uniformemente distanziato probabilmente non sarà in grado di catturare queste cuspidi. Quindi ti suggerisco di lasciare la domanda come era in origine, poiché è a questo che si riferiscono le risposte. Potresti voler fare una nuova domanda sul problema del disegno, preferibilmente fornendo dettagli su cosa esattamente cerchi di ottenere, ovvero perché semplicemente disegnare la spline 2D non è sufficiente. – MvG

risposta

2

La domanda indica che si desidera uniformare gli spazi x e le soluzioni approssimative vanno bene. Quindi propongo il seguente algoritmo:

  • Decidi i punti della griglia che desideri, ad es. uno ogni 0,1 x unità.
  • Inizio con l = 0 e r = 1.
  • Calcola f x ( l) e f x ( r) e considerare l'intervallo indicato con questi endpoint.
    • Se l'intervallo è sufficientemente piccolo e contiene esattamente un punto della griglia, utilizzare il parametro centrale t = ( l + r)/2 come una buona approssimazione per questo punto della griglia, e restituire che come elenco di un elemento.
    • Se v'è almeno un punto della griglia in quell'intervallo, dividerlo in due utilizzando ( l + r)/2 come punto di divisione, e concatenare gli elenchi derivanti da entrambi i calcoli.
    • Se non vi è alcun punto di griglia nell'intervallo, saltare il ramo corrente del calcolo, restituendo una lista vuota.

Ciò ingrandire i punti della griglia, che attraversa lo spazio dei parametri in ogni fase, e si presenti con parametri adeguati per tutti i punti della griglia.

+1

Questo è un metodo di bisezione ([link] (http://en.wikipedia.org/wiki/Bisection_method)), uno dei molti metodi di ricerca della radice. Controlla wikipedia per i punti di forza e di debolezza degli algoritmi che potrebbero funzionare meglio (o peggio) per problemi simili. –

2

Beh, si potrebbe risolvere il tuo f x ( t) = x per t. Questa sarebbe un'equazione cubica; brutto ma ancora possibile risolvere in modo esplicito. Se la tua spline è come la descrivi, allora due delle soluzioni saranno coniugate complesse, quindi l'unica che rimane è quella da prendere. Usalo per calcolare y = f y ( t). Dubito che tu possa accompagnare qualsiasi cosa più facilmente se vuoi delle soluzioni esatte.

È possibile utilizzare general formula from Wikipedia per calcolare la soluzione dell'equazione cubica.

+0

Grazie, è utile. In effetti, ho esaminato le soluzioni per te e sono piuttosto brutte. Certamente più brutto di qualsiasi cosa vorrei calcolare in grande quantità. Ho aggiunto che un'approssimazione (adatta per disegnare la curva come una funzione f (x)) è sufficiente. – vercellop

+0

@vercellop, ho pubblicato un collegamento che ti fornisce una formula per risolvere un'equazione cubica. – MvG