Domanda: Come si adatta una curva ai punti su un piano se non sono valutati singolarmente?Punti di raccordo senza curve su un piano
Per l'esempio mostrato, come si potrebbe montare una curva (come quello nero) ai dati blu rumorosi? È simile allo spline smoothing, ma non conosco l'ordine dei dati.
Matlab sarebbe preferito, ma pseudocodice è soddisfacente. O un puntatore a ciò che la terminologia corretta per questo problema sarebbe grande.
Grazie
Controllare questo articolo: Shape-preserving least-squares approximation by polynomial parametric spline curves, sembra presentare una soluzione. Inoltre, vedi la bibliografia alla fine.
Dovrete fare a tratti più raccordo o spline. Non aspettarti che nessun algoritmo sia in grado di fare tutto in un colpo solo. Potrebbe essere almeno tre curve: la prima fino all'intersezione, il loop e quindi indietro dall'intersezione in avanti.
Modifica: nvm ha erroneamente interpretato la domanda. Lascerò comunque questa risposta qui.
magari provare a trovare il convex hull dei punti prima quindi montare l'involucro convesso in pianura
http://www.cse.unsw.edu.au/~lambert/java/3d/giftwrap.html < animazioni --includes java di attuazione http://en.wikipedia.org/wiki/Convex_hull_algorithms
Se non si desidera che l'efficienza ci sono alcuni implementazioni molto semplici come la versione regalo che è O (n^2) http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
La versione dividi e conquista è O (nlogn)
I tuoi dati sembrano uno parametric plot bidimensionale di (x,y) in funzione di alcuni parametri sottostanti t. Di conseguenza, potrebbe essere possibile eseguire un adattamento x(t) e se è possibile ottenere un modello ragionevole per loro. I tuoi dati sembrano descrivere un limacon.
+1 - molto bello. – duffymo
Mentre i dati mostrati * hanno * una curva sottostante (una funzione rosa), ciò è dovuto al fatto che è stato facile fare un grafico. Ho bisogno di adattare una curva a qualsiasi dato arbitrario. – tkw954
Devi conoscere qualcosa sui dati sottostanti per qualsiasi tipo di adattamento della curva utile. Dal tuo esempio precedente, non c'è una ragione particolare (per un algoritmo ingenuo) per scegliere di andare dritto all'incrocio, piuttosto che fare due svolte a destra. È possibile adattare qualsiasi curva a qualsiasi serie di punti, diventa solo una questione di "idoneità". È necessario un euristico per selezionare quale curva si intende utilizzare, quindi qualsiasi routine standard di minimizzazione degli errori si adatta alla curva ai punti. –
Questo problema è davvero difficile se non si dispone di un ordine. Facendo un minimi quadrati su alcuni (x (t), y (t)) è facile - a patto di saper l'ordinamento dei t.
Probabilmente avrai bisogno di un po 'di algoritmo di ricerca. Un algoritmo genetico potrebbe essere ok.
Si potrebbe provare a dedurre l'ordine dei punti, quindi applicare le procedure spline. c'è un'ambiguità in cui la curva si incrocia, naturalmente.
forse l'approccio più ingenuo sarebbe quello di calcolare la triangolazione di Delaunay (tempo di nlogn), dalla quale approssimare un ciclo hamiltoniano di distanza minima euclidea attraverso i punti. Dovresti ancora capire dove sono i "fini". Dall'ordinazione è quindi possibile applicare le tecniche di spline.Per un riferimento, vedere Finding Hamiltonian Cycles in Delaunay Triangulations Is NP-Complete, o la carta di Reinelt sull'euristica TSP, 1992, o EMST su Wikipedia
hth,
Per approssimazioni a tratti con B-spline è possibile utilizzare this Matlab pacchetto. Funziona su modalità automatica e semi-manuale.
Cosa ti piacerebbe ottenere, come risultato? È una singola equazione? O spline? O qualcos'altro? –
La migliore sarebbe una singola equazione (o meglio: due x = f (t) y = f (t)), sebbene anche le equazioni a tratti siano ok. – tkw954