Determinare i punti piu importanti di una funzione
Ciao a tutti, ho una domanda, data una funzione qual'è il miglior modo per graficarla? mi spiego, vorrei tracciare il grafico di una funzione (con una spline), per trovare i punti il metodo piu semplice è quello di trovare la y per ogni x del dominio, ma rischio di ottenere molti valori, alcuni dei quali possono essere inutili, ad esempio per y=x^2 sarabbe utile qualche punto sullo 0 e meno punti mano a mano che ci si allontana dall'origine...come posso procedere secondo voi?
Risposte
Quali tipo di informazioni puoi ottenere su questa funzione? Di quale grado sono le curve con le quali vorresti approssimare la funzione?
Le curve dovrebbero essere delle Bezier cubiche con 2 punti di controllo, se devo essere sincero non so come vengano costruite perchè per la parte grafico uso una libreria esterna, alla funzione che mi crea le curve passo solo l'array dei valori relativi all'equazione.
Cosa intendi per che informazioni posso ottenere sulla funzione?
Cosa intendi per che informazioni posso ottenere sulla funzione?
A occhio potresti prendere pochi campioni x dove la derivata è bassa (in valore assoluto), e molti campioni dove la derivata è alta. Es. poni il passo tra i campioni come inversamente proporzionale alla derivata, con un passo minimo/massimo. In questo modo i punti sulla curva restano a distanza grosso modo costante.
Oppure potresti prendere più campioni nei punti stazionari (massimi, minimi, flessi), quindi il contrario di prima. Dipende da quali caratteristiche della funzione vuoi mostrare.
Oppure potresti prendere più campioni nei punti stazionari (massimi, minimi, flessi), quindi il contrario di prima. Dipende da quali caratteristiche della funzione vuoi mostrare.
Questa era una delle idee, ma il problema è come calcolare la derivata attraverso un algoritmo, ho provato a fare qualche ricerca e ho trovato poche idee 
Se rappresenti la tua curva come un insieme di punti, il modo più naturale per calcolare la derivata è con il rapporto incrementale.
f'(x) = (f(x + dx) - f(x)) / dx
con dx piccolo (magari 1).
f'(x) = (f(x + dx) - f(x)) / dx
con dx piccolo (magari 1).
Che io sappia una curva di Beziér è una spline... Mi sembra incomprensibile che tu voglia calcolarne punti per poi costruire una spline. Probabilmente ci sono algoritmi per convertirla. Che metodo useresti poi per disegnare la spline?
http://boa.unimib.it/bitstream/10281/76 ... cagd04.pdf in questo per esempio converte da e per B-spline.
http://boa.unimib.it/bitstream/10281/76 ... cagd04.pdf in questo per esempio converte da e per B-spline.
no, cioè che voglio fare io è un'altra cosa, quando calcolo i punti di un'equazione devo dargli un dominio (le x) che può essere -50 +50, successivamente con un for trovo le y, il problema è che per avere dei valori precisi devo avere uno step nel ciclo for molto piccolo, in modo da calcolare i punti in -50,-49.5,-48 che oltre ad eliminare le potenzialità della spline genera molti punti, ciò che voglio fare io è avere uno step basso nei punti dove serve di piu (massimi, minimi, flessi) e step piu ampi dove serve di meno....
@claudio, grazie, proverò a fare un due ragionamenti co al tua soluzione.
@claudio, grazie, proverò a fare un due ragionamenti co al tua soluzione.
Se non ho capito male quello che vorresti fare è un campionamento adattivo in funzione della ripidità della funzione.
Io avevo fatto una cosa simile per un programma in java che, data una qualsiasi funzione come stringa la disegnava.
L'idea è quella che ti ha suggerito claudio: calcoli la derivata come rapporto incrementale e, se il valore è maggiore di una certa soglia che fissi te, allora colleghi i due punti che stai considerando con una retta, altrimenti aggiungi un punto (ad esempio il punto medio) al segmento che stai considerando e ripeti il procedimento in maniera ricorsiva.
P.S.: se procedi in questo modo dovresti anche limitare il numero di ricorsioni perchè per funzioni molto "brutte" rischi di farne davvero tante. Questo, però, dipende anche da quanto sono "brutte" le funzioni che devi disegnare.
Io avevo fatto una cosa simile per un programma in java che, data una qualsiasi funzione come stringa la disegnava.
L'idea è quella che ti ha suggerito claudio: calcoli la derivata come rapporto incrementale e, se il valore è maggiore di una certa soglia che fissi te, allora colleghi i due punti che stai considerando con una retta, altrimenti aggiungi un punto (ad esempio il punto medio) al segmento che stai considerando e ripeti il procedimento in maniera ricorsiva.
P.S.: se procedi in questo modo dovresti anche limitare il numero di ricorsioni perchè per funzioni molto "brutte" rischi di farne davvero tante. Questo, però, dipende anche da quanto sono "brutte" le funzioni che devi disegnare.
Per prima cosa non userei le curve di Bézier cubiche. È vero che sono in grado di rappresentare perfettamente funzioni di grado minore o uguale a tre, ma stimare la spline che meglio approssima la funzione, mantenendo il numero di curve il più basso possibile, è già computazionalmente gravoso anche senza fare ricorso a curve di terzo grado. Considerando che è (quasi) sempre necessario convertire la curva a spline di grado 1 (delle linee spezzate) per poterle disegnare, mi sembra uno spreco di risorse.
Per quale ragione desideri avere un grado elevato per le spline da usare per visualizzare la funzione? Per avere una curva "liscia" tra i punti della funzione? Quanto sono vicini i punti che descrivono la funzione? Quale tipo di regolarità desideri nel grafico?
Un metodo per fare quello che chiedi potrebbe essere quello di suddividere ricorsivamente l'intervallo a metà e di usare un qualche algoritmo di regressione per trovare la curva cubica che meglio approssima la sezione di funzione (aggiungendo eventualmente condizioni sui due punti estremi dell'intervallo). Se l'errore ottenuto approssimando la funzione con tale curva è troppo alto, si suddivide ulteriormente l'intervallo. La stessa idea per le curve di grado 1 è stata fornita da Lory314.
@claudio: a seconda delle occasioni potrebbe essere più comodo usare altre formule per le derivate. Per esempio
f'(x) = (f(x) - f(x - dx))/dx
f'(x) = (f(x + dx) - 2f(x) + f(x - dx))/2dx
EDIT: Riguardo al metodo di visualizzazione basato sull'uso di segmenti tra punti della funzione, non utilizzerei il calcolo della derivata per stabilire quando la funzione sia approssimabile da un segmento. Calcolerei piuttosto un errore basato sulla distanza tra i punti della funzione e il segmento. Questo metodo permette ad esempio di prendere decisioni come quella di fermarsi ad un certo livello di dettaglio quando le distanze tra i punti della funzione e il segmento siano inferiori ad un pixel. Ragionare in termini di derivate mi sembra più complicato e meno intuitivo.
Per quale ragione desideri avere un grado elevato per le spline da usare per visualizzare la funzione? Per avere una curva "liscia" tra i punti della funzione? Quanto sono vicini i punti che descrivono la funzione? Quale tipo di regolarità desideri nel grafico?
Un metodo per fare quello che chiedi potrebbe essere quello di suddividere ricorsivamente l'intervallo a metà e di usare un qualche algoritmo di regressione per trovare la curva cubica che meglio approssima la sezione di funzione (aggiungendo eventualmente condizioni sui due punti estremi dell'intervallo). Se l'errore ottenuto approssimando la funzione con tale curva è troppo alto, si suddivide ulteriormente l'intervallo. La stessa idea per le curve di grado 1 è stata fornita da Lory314.
@claudio: a seconda delle occasioni potrebbe essere più comodo usare altre formule per le derivate. Per esempio
f'(x) = (f(x) - f(x - dx))/dx
f'(x) = (f(x + dx) - 2f(x) + f(x - dx))/2dx
EDIT: Riguardo al metodo di visualizzazione basato sull'uso di segmenti tra punti della funzione, non utilizzerei il calcolo della derivata per stabilire quando la funzione sia approssimabile da un segmento. Calcolerei piuttosto un errore basato sulla distanza tra i punti della funzione e il segmento. Questo metodo permette ad esempio di prendere decisioni come quella di fermarsi ad un certo livello di dettaglio quando le distanze tra i punti della funzione e il segmento siano inferiori ad un pixel. Ragionare in termini di derivate mi sembra più complicato e meno intuitivo.
Aggiungo solo che un metodo per calcolare la derivata in modo adattivo è questo: http://en.wikipedia.org/wiki/Richardson_extrapolation
Come condizione di fine puoi usare la differenza tra due approssimazioni successive e/o condizioni sulla dimensione minima della suddivisione.
Come condizione di fine puoi usare la differenza tra due approssimazioni successive e/o condizioni sulla dimensione minima della suddivisione.
La domanda è già stata posta ma mi sembra pertinente: che senso ha fare quello che chiedi? Cioé, ti si chiede di calcolare punti di una generica curva di data equazione (apropos: in quanti assi ovvero in che dimensione?) di cui magari non conosci bene dominio e codominio, per poi passarli come parametri ad una funzione che, usando B-spline, la disegna su una viewport? Mi sembra un po' contorto...
Allora cerco di rispiegare quello che vorrei fare:
data un'equazione devo stamparla a video per un'applicazione iphone, la parte puramente grafica è gestitta da una libreria esterna che da un array di punti la disegna, il mio problema è che array di punti inviare.
Posso collegare i punti con una semplice retta o con una spline, risultato che per fare un bel grafico nel primo modo devo inviare 100 punti mentre nel secondo caso ne bastano la meta (numeri estremizzati).
Il problema che mi popngo è quello di inviare un array di valori appropriato all'equazione, da qui partono tutti i miei casini.
Per ora per la risoluzione dell'equazione usavo un semplice for (x=-10;x=10;x=x+step) y=x^2 con step che può avere un qualsiasi valore prefissato (0.1,0,5.1,ecc..) piu piccolo è e piu precisi sono i punti ma sono anche un bel po di valori, quindi aumentando lo step diminuisco i punti che copmorta ad una approssimazione grossolana se la retta è costruita con semplici linee che colegano due punti, diverso se uso una spline che mi disegna una curva molto piu realistica. Il mio problema è trovare un'insieme di punti che sia il minore possibile ma che allo stesso tempo mi permetta di disegnare una "bella" curva.
data un'equazione devo stamparla a video per un'applicazione iphone, la parte puramente grafica è gestitta da una libreria esterna che da un array di punti la disegna, il mio problema è che array di punti inviare.
Posso collegare i punti con una semplice retta o con una spline, risultato che per fare un bel grafico nel primo modo devo inviare 100 punti mentre nel secondo caso ne bastano la meta (numeri estremizzati).
Il problema che mi popngo è quello di inviare un array di valori appropriato all'equazione, da qui partono tutti i miei casini.
Per ora per la risoluzione dell'equazione usavo un semplice for (x=-10;x=10;x=x+step) y=x^2 con step che può avere un qualsiasi valore prefissato (0.1,0,5.1,ecc..) piu piccolo è e piu precisi sono i punti ma sono anche un bel po di valori, quindi aumentando lo step diminuisco i punti che copmorta ad una approssimazione grossolana se la retta è costruita con semplici linee che colegano due punti, diverso se uso una spline che mi disegna una curva molto piu realistica. Il mio problema è trovare un'insieme di punti che sia il minore possibile ma che allo stesso tempo mi permetta di disegnare una "bella" curva.
Credo proprio che tu non abbia alcuna idea di quelle che sono le implicazioni legate all'uso delle spline. Per prima cosa la frase
Non ha senso in quanto, come ti ho spiegato in un post precedente, è necessario convertire la spline in una curva spezzata per disegnarla. In pratica fai un sacco di calcoli per ridurre il numero di punti per poi richiedere alla libreria di farne altrettanti per riottenere nuovamente un numero di punti paragonabile (possibilmente anche più alto) del precedente. In pratica stai facendo il doppio (forse anche triplo/quadruplo..) del lavoro per niente. L'unica utilità che vedo nell'uso delle spline è quella di rendere la curva più liscia, ottenendo una curva non spezzata tra i diversi punti della funzione. Se questo non è il tuo obiettivo, lascia perdere le spline cubiche (soprattutto considerando che stai programmando per un cellulare).
Sinceramente sono tentato di considerare il tuo problema come "premature optimization" (e quindi qualcosa da evitare). A meno che tu non stia avendo problemi di performance con la soluzione naive di disegnare tutti i punti (e non dovresti averne a meno di disegnare milioni di punti), terrei la soluzione più semplice e immediata.
Posso collegare i punti con una semplice retta o con una spline, risultato che per fare un bel grafico nel primo modo devo inviare 100 punti mentre nel secondo caso ne bastano la meta (numeri estremizzati).
Non ha senso in quanto, come ti ho spiegato in un post precedente, è necessario convertire la spline in una curva spezzata per disegnarla. In pratica fai un sacco di calcoli per ridurre il numero di punti per poi richiedere alla libreria di farne altrettanti per riottenere nuovamente un numero di punti paragonabile (possibilmente anche più alto) del precedente. In pratica stai facendo il doppio (forse anche triplo/quadruplo..) del lavoro per niente. L'unica utilità che vedo nell'uso delle spline è quella di rendere la curva più liscia, ottenendo una curva non spezzata tra i diversi punti della funzione. Se questo non è il tuo obiettivo, lascia perdere le spline cubiche (soprattutto considerando che stai programmando per un cellulare).
Sinceramente sono tentato di considerare il tuo problema come "premature optimization" (e quindi qualcosa da evitare). A meno che tu non stia avendo problemi di performance con la soluzione naive di disegnare tutti i punti (e non dovresti averne a meno di disegnare milioni di punti), terrei la soluzione più semplice e immediata.
"apatriarca":
A meno che tu non stia avendo problemi di performance con la soluzione naive di disegnare tutti i punti (e non dovresti averne a meno di disegnare milioni di punti), terrei la soluzione più semplice e immediata.
Sottoscrivo: devi considerare che la viewport è rappresentata su pochi pixel(*), e puoi usare direttamente il fattore di scala che, calcolato una-tantum, ti permette di fare un ciclo di (al massimo) tante iterazioni quanti sono tali pixel, con l'ulteriore vantaggio di avere sempre lo stesso tempo di esecuzione.
(*) Le dimensioni degli schermi più evoluti non superano mai quelle di un monitor 17" per PC, al massimo 1280 pixel orizzontali (aka al massimo 1280 iterazioni). L'iphone è superiore?
La risoluzione dell'iPhone 5 dovrebbe essere 640×1136. Per cui una funzione in due variabili ha senso rappresentarla con al massimo un migliaio di punti (che la scheda video dell'iPhone 5 non dovrebbe avere alcun problema a visualizzare con grande fluidità).
"apatriarca":
Credo proprio che tu non abbia alcuna idea di quelle che sono le implicazioni legate all'uso delle spline.
Sinceramente si, è molto probabile che sia cosi! Studio meccanica quindi tutt'altro e l'informatica è solo un'hobby, ed essendo autodidatta non so tutte le cose con precisione (quindi perdonatemi se non capisco fino in fondo i vostri ragionamenti)....Voglio utilizzare la spline perchè facendo un test seguendo il ragionamento che ho scritto prima ho notato un'aumento di velocità nello scrolling e zoom del grafico (l'applicazione dovrà funzionare anche su ipad che nella versione retina ha una risoluzione circa 2 volte quella dell'iphone), ottenendo una curva pressochè uguale passando un array con meno punti.
Questo è il prinicipale motivo per cui voglio utilizzare una spline e avere piu punti dove serve e meno dove no serve.
kikko088
In ogni caso tu, di fatto, crei due volte la spline. Anche volendo usare le spline ti conviene calcolarla a partire dalla funzione di partenza invece che dalla curva di Bezier, anche perché l'approssimazione risulterà più precisa. Tieni comunque conto che, performance a parte, converrebbe trovarti nuovi punti quando fai lo zoom (cercando di mantenere il più possibile punti già calcolati) perché altrimenti se inizi con un range molto ampio e finisci con l'analizzare un intervallo molto piccolo finirai per avere una approssimazione senza senso.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo