2015-01-01 3 views
6

Sto cercando un algoritmo per la semplificazione e il livellamento del percorso per traiettorie 2D. Quindi ho una lista ordinata di punti 2D. Questi punti dovrebbero essere semplificati, ad es. con l'algoritmo Ramer-Douglas-Peucker. Ma l'output deve essere liscio, quindi il percorso risultante dovrebbe essere costruito da curve o spline di Bezier. C'è qualche modifica dell'algoritmo Ramer-Douglas-Peucker in grado di gestirlo?Algoritmo per la semplificazione del percorso e il livellamento delle traiettorie 2D

Ho trovato un algoritmo di semplificazione del percorso nella libreria paper.js, che fa esattamente quello che sto cercando: http://paperjs.org/examples/path-simplification/ Ma non ero in grado di capire l'algoritmo dal codice sorgente javascript non documentato.

risposta

10

Il lavoro che vuole fare rientra nella categoria di "adattamento della curva". Ci sono tonnellate di algoritmi diversi per l'adattamento della curva, ma quasi tutti gli algoritmi di adattamento della curva possono essere suddivisi in due diverse categorie: interpolazione e approssimazione. Gli algoritmi di interpolazione producono una curva che attraversa tutti i punti dati esattamente mentre gli algoritmi di approssimazione generano una curva che si trova vicino ai punti dati. Naturalmente esistono anche algoritmi ibridi.

Poiché si desidera che i punti dei dati siano smussati, è necessario cercare algoritmi di approssimazione. Per i due algoritmi che hai citato: algoritmo RDP e algoritmo Schneider (quello in Paper.js), sono entrambi algoritmi di approssimazione. Quindi, in pratica puoi usare entrambi. Per RDP, dopo aver ottenuto il percorso semplificato, è possibile utilizzare creare una spline Catmull Rom o una spline Overhauser attraverso i vertici del percorso semplificato per ottenere una curva uniforme. Tuttavia, non si ha il controllo diretto per la deviazione tra la spline risultante e i vertici nel percorso originale.

Per l'algoritmo di Schneider, inizierà con il montaggio dei punti di dati con una curva Bezier cubica con vincoli di tangenza finale. Se la deviazione rispetto alla curva risultante è troppo grande, divide i punti dati in due "regioni" e adatta ciascuna regione di dati con curve Bezier cubiche con vincoli di tangenza finale. Questo processo verrà ripetuto fino a quando la deviazione di tutte le curve cubiche di Bezier sarà abbastanza piccola.Di conseguenza, produce una serie di curve cubiche di Bezier collegate al meglio con continuità C1 (molto probabilmente è solo G1). Inoltre, dal momento che questo algoritmo valuta le tangenti finali dai punti dati originali, il rumore nel punto dati influenzerà la valutazione tangente finale e quindi il raccordo cubico di Bezier.

Se è possibile dedicare del tempo all'argomento dell'installazione della curva, è necessario considerare il raccordo minimo con curve B-spline. Ciò genererà una curva di uscita con alta continuità (C2 per le curve B-spline cubiche per esempio). Se non si ha molto tempo da dedicare, l'algoritmo di Schneider è una buona scelta che raggiunge un equilibrio tra il costo di implementazione (se è necessario re-implementarlo in una lingua specifica) e la qualità della curva risultante.

4

Quello che stai molto probabilmente dopo si chiama Curve Fitting.

Mentre il Ramer-Douglas-Peucker algoritmo leviga essenzialmente 'rumore' di una polilinea, eliminando i punti non necessari - una curva algoritmo di adattamento si adatta Bezier curve attraverso quei punti.

Here è un bell'esempio su Youtube e here è il documento originale che descrive l'algoritmo stesso.


Per quanto riguarda l'esempio Paper.js:

  • This è il legame Github per quella particolare funzionalità lei ha citato e questo è abbastanza ben commentato. Il documento di ricerca che è stato utilizzato è this.

  • anche here è una breve discussione sulla mailing list su ciò che è stato utilizzato e cosa no (apparentemente Ramer-Douglas-Peucker è stato utilizzato ma rimosso in seguito)