Funzione per la restituzione di un elenco di punti su una curva di Bezier alla stessa lunghezza d'arco

Question

Qualcuno da qualche parte ha dovuto risolvere questo problema. Riesco a trovare molti ottimi siti web che spiegano questo problema e come risolverlo. Mentre sono sicuro che sono ben scritti e hanno senso per la matematica, non sono io. E mentre potrei capire in un modo vago, non capisco come trasformare quella matematica in una funzione che posso usare.

Quindi ti prego, se hai una funzione che può farlo, in qualsiasi lingua, (sicuramente anche fortran o diavolo 6502 assemblatore) - per favore aiutami.

• preferiscono un analitico per soluzione iterativa

EDIT: Meant per specificare che la sua un Bézier cubica che sto cercando di lavorare.

Answer 1

Quello che stai chiedendo è l'inverso della funzione di lunghezza dell'arco. Quindi, data una curva B, vuoi una funzione Linv (len) che restituisca una t tra 0 e 1 in modo che la lunghezza dell'arco della curva tra 0 e t sia len.

Se avevi questa funzione il tuo problema è davvero facile da risolvere. Sia B (0) il primo punto. Per trovare il punto successivo, devi semplicemente calcolare B (Linv (w)) dove w è la "lunghezza d'onda uguale" a cui fai riferimento. Per ottenere il punto successivo, basta valutare B (Linv (2 * w)) e così via, finché Linv (n * w) diventa maggiore di 1.

Ho avuto a che fare con questo problema di recente. Mi sono inventato, o ho trovato alcune soluzioni, nessuna delle quali è soddisfacente per me (ma forse saranno per te).

Ora, questo è un po 'complicato, quindi lasciatemi solo dare il link al codice sorgente prima: http://icedtea.classpath.org/~dlila/webrevs/perfWebrev/webrev/raw_files/new/src/share/classes/sun/java2d/pisces/Dasher.java. Quello che vuoi è nella classe LengthIterator. Non dovresti dover guardare altre parti del file. Ci sono un sacco di metodi che sono definiti in un altro file. Per arrivare a loro basta ritagliare tutto da/raw_files/alla fine dell'URL. Questo è come lo si usa. Inizializza l'oggetto su una curva. Quindi per ottenere il parametro di un punto con lunghezza d'arco L dall'inizio della curva basta chiamare next (L) (per ottenere il punto attuale basta valutare la curva con questo parametro, usando l'algoritmo di deCasteljau o il suggerimento di zneak). Ogni chiamata successiva di next (x) ti sposta di una distanza di x lungo la curva rispetto alla tua ultima posizione. next restituisce un numero negativo quando si esaurisce la curva.

Spiegazione del codice: quindi, avevo bisogno di un valore t tale che B (0) a B (t) avrebbe lunghezza LEN (dove LEN è noto). Ho semplicemente appiattito la curva. Quindi, è sufficiente suddividere la curva in modo ricorsivo fino a quando ogni curva è abbastanza vicina a una linea (è possibile verificarla confrontando la lunghezza del poligono di controllo con la lunghezza della linea che unisce i punti finali). È possibile calcolare la lunghezza di questa sotto-curva come (controlPolyLength + endPointsSegmentLen)/2. Aggiungi tutte queste lunghezze a un accumulatore e interrompi la ricorsione quando il valore dell'accumulatore è> = LEN. Ora, chiama l'ultima subcurve C e lascia che [t0, t1] sia il suo dominio. Sai che il t che vuoi è t0 < = t < t1, e conosci la lunghezza da B (0) a B (t0) - chiama questo valore L0t0. Quindi, ora è necessario trovare un t tale che C (0) a C (t) abbia lunghezza LEN-L0t0. Questo è esattamente il problema con cui abbiamo iniziato, ma su una scala più piccola. Potremmo usare la ricorsione, ma sarebbe terribilmente lenta, quindi usiamo semplicemente il fatto che C è una curva molto piatta. Facciamo finta che C sia una linea e calcoliamo il punto at usando P = C (0) + ((LEN-L0t0)/lunghezza (C)) * (C (1) -C (0)). Questo punto in realtà non giace sulla curva perché è sulla linea C (0) -> C (1), ma è molto vicino al punto che vogliamo. Quindi, risolviamo solo Bx (t) = Px e By (t) = Py. Questo è solo trovare le radici cubiche, che ha una soluzione closed source, ma ho appena usato il metodo di Newton. Ora abbiamo il t che vogliamo, e possiamo solo calcolare C (t), che è il punto attuale.

Devo dire che alcuni mesi fa ho sfogliato un foglio che aveva un'altra soluzione che ha trovato un'approssimazione alla parametrizzazione naturale della curva. L'autore ha pubblicato un link ad esso qui: Equidistant points across Bezier curves