Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Esamuele Santoro » 8.Interpolazione ed approssimazione di punti


Interpolazione di Lagrange e di Bézier

X_{i-1}(1)=X_{i}(0)=x_{i},\;

..
X'_{i-1}(1)=X'_{i}(0),\;


X''_{i-1}(1)=X''_{i}(0),\;1\leq i\leq n-1

….
L_{n.i}(x_{i})=1,\: L_{n,i}(x_{j})=0,\; j\neq i

Il problema dell’interpolazione o approssimazione si presenta ogni qual volta si conoscono le coordinate di punti e si vuole determinare la funzione che passi o approssimi tali punti.

L’interpolazione viene effettuata se i punti sono pochi e ben regolari, viceversa se i punti sono molti si preferisce determinare una funzione approssimante.

Siano dati n+1 punti Pi={xi,yi,zi} , i=0,n e delle funzioni F(x,y,z;V) dove V∈Rm è un vettore che rappresenta i parametri della funzione. Quando m=n+1 è possibile definire il seguente problema dell’interpolazione, che consiste nel determinare il vettore V tale che:

F(x_{i},y_{i},z_{i};\mathbf{V})=0,\; i=0,1,..,n ~~~~~(5.1)

Interpolazione di Lagrange e di Bézier

La (5.1) vista nella slide precedente, rappresenta un sistema di n+1 equazioni nell’incognita V.

In generale si sceglie come funzione interpolante una funzione algebrica. Ad esempio se si vogliono interpolare con una conica dei punti appartenenti ad un piano si ha che la conica è data da:

\mathrm{a}x^{2}+\mathrm{b}y^{2}+2\mathrm{c}xy+\mathrm{d}x+\mathrm{e}y+1=\left[\begin{array}{ccc} x & y & 1\end{array}\right]\left[\begin{array}{ccc}\mathrm{a} & \mathrm{c} & 0\\\mathrm{c} & \mathrm{b} & 0\\\mathrm{d} & \mathrm{e} & 1\end{array}\right]\left[\begin{array}{c}x\\y\\1\end{array}\right]

che ha cinque incognite V=(a,b,c,d,e), per cui occorre assegnare 5 condizioni.

Interpolazione di Lagrange e di Bézier

Mentre se si vuole ottenere una quadrica (superficie di secondo grado) che interpola dei punti nello spazio si ha che la quadrica è data da:

\mathrm{a}x^{2}+\mathrm{b}y^{2}+cz^{2}+2\mathrm{e}xy+2fxz+2gyz+hx+\mathrm{m}y+\mathrm{n}\mathit{z}+1=0

che in notazione matriciale è data da:

\left[\begin{array}{cccc}x & y & z & 1\end{array}\right]\left[\begin{array}{cccc}\mathrm{a} & \mathrm{e} & \mathrm{f} & 0\\\mathrm{e} & \mathrm{b} & \mathrm{g} & 0\\\mathrm{f} &\mathrm{g} & \mathrm{c} & 0\\\mathrm{h} & \mathrm{m} & \mathrm{n} & 1\end{array}\right]\left[\begin{array}{c}x\\y\\z\\1\end{array}\right]=0

La quadrica ha nove incognite V=(a,b,c,e,f,g,h,m,n), per cui occorre assegnate nove condizioni, che possono essere 9 punti da interpolare.

Interpolazione di Lagrange e di Bézier

Le interpolazioni più diffuse si riferiscono a punti appartenenti ad un piano con funzioni interpolanti polinomiali.
Nel caso dell’interpolazione polinomiale piana, per cui Pi=(xi,yi), e per xi#xj , si ottiene un sistema di equazioni lineari che ammette una ed una sola soluzione dato da:

y_{i}=\overset{n}{\sum_{j=0}}\mathrm{a}_{i}x_{i}^{j}=0,\; i=0,1,..,n

dove V=(a0,a1,..,an)

Se sono assegnati n punti, aventi ascisse differenti, esiste sempre un polinomio di grado n-1 che interpola tale punti. Pertanto, per tre punti esiste una ed una sola parabola che interpola tali punti.

Uno dei metodi che in passato è stato proposto per risolvere il problema dell’interpolazione polinomiale è quello di Lagrange, che evita di risolvere il sistema di equazioni. Lagrange utilizzò i seguenti polinomi per risolvere il problema dell’interpolazione:

L_{n,i}(x)=\frac{(x-x_{0})\cdot....(x-x_{i-1})(x-x_{i+1})\cdot....(x-x_{n})}{(x_{i}-x_{0})\cdot....(x_{i}-x_{i-1})(x_{i}-x_{i+1})\cdot....(x_{i}-x_{n})}=\overset{n}{\prod_{j=0,j\neq i}}\frac{(x-x_{j})}{(x_{i}-x_{j})}

che assumono i seguenti valori nelle ascisse date:

L_{n.i}(x_{i})=1,\: L_{n,i}(x_{j})=0,\; j\neq i

Interpolazione di Lagrange e di Bézier

Utilizzando i polinomi di Lagrange si ha che la funzione interpolante polinomiale è data da:

y=F(x)=\overset{n}{\sum_{i=0}}y_{i}L_{n,i}(x)

Esercizio: Calcolare mediate i polinomi di Lagrange la parabola passante per i punti P0=(0,1), P1=(2,1) e P3=(3,0).

Le funzioni di Lagrange sono:

L_{2,0}(x)=\frac{(x-2)(x-3)}{6}

L_{2,1}(x)=\frac{x(x-3)}{2}

L_{2,2}(x)=\frac{x(x-2)}{3}

per cui la parabola interpolante è data da:

y=F(x)=\frac{(x-2)(x-3)}{6}-\frac{x(x-3)}{2}

Interpolazione di Lagrange e di Bézier

Le formule che definiscono l’algoritmo di Bézier possono essere utilizzate sia per avere delle curve definite mediate punti di controllo, oppure di determinare una curva interpolante che passi per assegnati punti e dove i punti di controllo rappresentano le incognite da determinare.

Nel caso che si utilizzi la curva di Bézier per interpolare n punti ri=(xi,yi,zi), la (5.1) diventa:

\mathbf{r}_{i}=\mathbf{r}(t_{i})=\overset{n}{\sum}_{j=0}\mathbf{P}_{j}B_{n,j}(t_{i})=(x_{i},y_{i},z_{i})~~~~~(5.4)

Nella (3.4) le incognite sono i punti di controllo Pj e i valori dei parametri ti. I valori di ti possono essere assunti utilizzando differenti metodi.

Il più utilizzato metoso è quello che si basa sulla distanza tra ri e r0 e viene indicato come metodo centripeto, che assume i seguenti valori:

t_{0}=0,\: t_{i}=t_{i-1}+\frac{\left\Vert \mathbf{r}_{i}-\mathbf{r}_{i-1}\right\Vert ^{1/2}}{\sum_{j=1}\left\Vert \mathbf{r}_{j}-\mathbf{r}_{j-1}\right\Vert ^{1/2}},\; t_{n=1} ~~~~~~(5.5)

Il denominatore della (5.5) è lunghezza della poligonale avente per vertici ri.

Interpolazione di Lagrange e di Bézier

La curva di Bezier soddisfa la proprietà di essere interpolante per gli estremi per cui P0=r(0) e Pn=r(1). Pertanto i vertici incogniti Pi del poligono di controllo sono n-1.

Sviluppando la (5.4) si perviene al seguente sistema di equazioni lineare:

…….

\left[\begin{array}{cccc}B_{n,1}(t_{1}) & B_{n,2}(t_{1}) & ... & B_{n,n-1}(t_{1})\\B_{n,1}(t_{2}) & B_{n,2}(t_{2}) & ... & B_{n,n-1}(t_{2})\\.... & .... & ... & ...\\B_{n,1}(t_{n-1}) & B_{n,2}(t_{n-1}) & ... & B_{n,n-1}(t_{n-1})\end{array}\right]\left[\begin{array}{c}\mathbf{P}_{1}\\\mathbf{P}_{2}\\...\\\mathbf{P}_{n-1}\end{array}\right]=\left[\begin{array}{c}\mathbf{r}_{1}-B_{n,0}(t_{1}\mathbf{r}_{0}-B_{n,n}(t_{1})\mathbf{r}_{n}\\\mathbf{r}_{2}-B_{n,0}(t_{2})\mathbf{r}_{0}-B_{n,n}(t_{2})\mathbf{r}_{n}\\................\\\mathbf{r}_{n-1}-B_{n,0}(t_{n-1})\mathbf{r}_{0}-B_{n,n}(t_{n-1})\mathbf{r}_{n}\end{array}\right]

Interpolazione mediante funzioni polinomiali spline

Quando il numero dei punti da interpolare diventa grande si ha che il polinomio interpolante presenta delle oscillazioni che sono inaccettabili se dovessimo rappresentare la geometria di un oggetto.

Per ridurre tali oscillazioni fu introdotta l’interpolazione mediante spline, che consiste nel suddividere tutta la curva in segmenti polinomiali (polinomial piecewice) a cui vengono imposti delle condizioni di continuità quando si passo da un segmento al successivo.

Il termine inglese spline significa curvilineo flessibile, ed è lo strumento utilizzato dai disegnatori per interpolare dei punti.
Lo strumento spline può essere considerato come una trave incastrata che viene sollecitata a flessione e operando per tratti si riesce a interpolare un numero elevato di punti.
Dalla teoria delle travi soggette a flessione si dimostra che la funzione interpolante ottenuta con lo spline è di tipo polinomiale e in particolare il grado del polinomio è tre, per cui si ha una cubica.

Con l’interpolazione mediante spline il grado del polinomio non dipende dal numero dei punti ma è un input e dalla teoria si dimostra che le curve spline hanno interessanti proprietà come quella di minimizzare alcuni grandezze geometriche come la curvatura, ottenendo delle curve interpolanti lisce che ben raccordano i punti da interpolare.

I gradi dispari dei polinomi spline hanno una migliore stabilità numerica e spesso si utilizzano le spline cubiche che hanno una continuità fino alla derivata seconda. La poligonale passante tra punti assegnati è la più semplice curva interpolante e rappresenta una funzione spline di grado uno.

Interpolazione mediante funzioni polinomiali spline

Se m è il grado della funzione spline si ha che la continuità tra segmenti successivi della spline è fino alla derivata (m-1).
Se si considera un’interpolazione mediante una spline cubica di n+1 punti appartenenti al piano xy, essa è costituita da n segmenti di polinomi pi(x)=ai,0+ai,1x+ai,2x2+ai,3x3, dove le incognite sono i 4 parametri (ai,0,ai,1,ai,2,ai,3).
Considerando le condizioni di continuità di grado 0, 1 e 2 si ottengono le equazioni:

p_{i}(x_{i+1})=y_{i+1},\; p_{i+1}(x_{i+1})=y_{i+1},\;0\leq i\leq n-2

p_{i}'(x_{i+1})=p_{i+1}^{'}(x_{i+1}),\; p_{i}''(x_{i+1})=p_{i+1}^{''}(x_{i+1}),\;0\leq i\leq n-2

p_{0}(x_{0})=y_{0},\; p_{n-1}(x_{n})=y_{n}

il cui numero è 2+4(n-1)=4n-2.
Poiché le incognite sono 4n occorre assegnare altre due equazioni per poter risolvere il problema dell’interpolazione con spline cubica.
In generale, le due ulteriori condizioni si ottengono imponendo che la curva abbia agli estremi dei valori assegnati di pendenza o curvatura. Se si impone che la derivata seconda sia uguale a zero, la spline che si ottiene viene indicata come spline naturale.

Interpolazione mediante funzioni polinomiali spline

Una differente formulazione del problema dell’interpolazione mediante spline si ottiene considerando la formulazione parametrica da cui è possibile ottenere l’interpolazione anche in uno spazio a 3 o più dimensioni.

Se consideriamo uno spazio a 3 dimensioni si ha che ogni segmento di spline è dato in forma parametrica da pi(t)={Xi(t),Yi(t),Zi(t)} per i=0,..,n-1. Considerando per semplicità la spline cubica e solo la componente X(t) si ha:

X_{i}(t)=\mathrm{a}_{i}+\mathrm{b}_{i}t+\mathrm{c}_{i}t^{2}+\mathrm{d}_{i}t^{3},\;0\leq t\leq1

….

Se consideriamo solo le condizioni di continuità di grado 0 e 1 si hanno le seguenti 4n equazioni:

X_{i}(0)=x_{i}=\mathrm{a}_{i},\; X'_{i}(0)=\mathrm{b}_{i}=\mathrm{D}_{i}

X_{i}(1)=x_{i+1}=\mathrm{a}_{i}+\mathrm{b}_{i}+\mathrm{c}_{i}+\mathrm{d}_{i},\; X'_{i}(1)=\mathrm{b}_{i}+2\mathrm{c}_{i}+3\mathrm{d}_{i}=\mathrm{D}_{i+1}

dove Di=dXi(0)/dt indica il valore della derivata prima nel punto i-mo.
Le precedenti quattro equazioni permettono di esprimere i coefficienti della cubica in funzione delle coordinate e della derivata prima

Interpolazione mediante funzioni polinomiali spline

\mathrm{a}_{i}=x_{i},\;\mathrm{b}_{i}=\mathrm{D}_{i},\;\mathrm{c}_{i}=3(x_{i+1}-x_{i})-2\mathrm{D}_{i}-\mathrm{D}_{i+1},\;\mathrm{d}_{i}=-2(x_{i+1}-x_{i})+\mathrm{D}_{i}+\mathrm{D}_{i+1} ~~~~(5.9)

Se sono noti i valori della pendenza nei punti assegnati, con la precedente equazione si determina la cubica. Se si impongono le condizioni di continuità di grado 0, 1 e 2 nei punti interni si ottiene:

X_{i-1}(1)=X_{i}(0)=x_{i},\;
X'_{i-1}(1)=X'_{i}(0),\;
X''_{i-1}(1)=X''_{i}(0),\;1\leq i\leq n-1

mentre dalla condizione di passaggio per i punti estremi si ha X0(0)=x0, Xn-1(1)=xn.

Pertanto anche in questo caso abbiamo 4n incognite e 4n-2 equazioni. Esplicitando la condizione della continuità sulla derivata seconda si ha:

\mathrm{c}_{i-1}+3\mathrm{d}_{i-1}=\mathrm{c}_{i},\;1\leq i\leq n-1

che per la (5.9) si può scrivere:

\left[3(x_{i}-x_{i-1})-2\mathrm{D}_{i-1}-\textrm{D}_{i}\right]+3\left[2(x_{i-1}-x_{i})+\mathrm{D}_{i-1}+\mathrm{D}_{i}\right]=\left[3(x_{i+1}-x_{i})-2\mathrm{D}_{i}-\mathrm{D}_{i+1}\right]

La precedente equazione si semplifica:

\mathrm{D}_{i-1}+4\mathrm{D}_{i}+\mathrm{D}_{i+1}=3(x_{i+1}-x_{i}),\;1\leq i\leq n-1

Interpolazione mediante funzioni polinomiali spline

Pertanto abbiamo n-1 equazioni mentre le incognite sono le n+1 pendenze. Le ulteriori due condizioni si ottengono supponendo che la spline sia naturale o che abbia assegnate pendenze agli estremi. Se la spline è quella naturale si ha:

X''_{0}(0)=0\rightarrow c_{0}=0\rightarrow2\mathrm{D}_{0}+\mathrm{D}_{1}=3(x_{1}-x_{0})
X''_{n-1}(1)=0\rightarrow c_{n-1}+3\mathrm{d}_{n-1}=
=0\rightarrow3(x_{n}-x_{n1})-2\mathrm{D}_{n-1}-\mathrm{D}_{n}+3\left[-2(x_{n}-x_{n-1})+\mathrm{D}_{n-1}+\mathrm{D}_{n}\right]=0\rightarrow\mathrm{D}_{n-1}+2\mathrm{D}_{n}=3(x_{n}-x_{n-1})

Le precedenti equazioni rappresentano un sistema di n+1 equazioni in n+1 incognite e può essere scritto nella seguente forma matriciale:

\left[\begin{array}{cccccccc}2 & 1\\1 & 4 & 1\\& 1 & 4 & 1\\.. & .. & .. & .. & .. & .. & .. & ..\\& & & & & 1 & 4 & 1\\& & & & & & 1 & 2\end{array}\right]\left[\begin{array}{c}\mathrm{D}_{0}\\\mathrm{D}_{1}\\\mathrm{D}_{2}\\...\\\mathrm{D}_{n-1}\\\mathrm{D}_{n}\end{array}\right]=3\left[\begin{array}{c}x_{1}-x_{0}\\x_{2}-x_{0}\\x_{3}-x_{1}\\....\\x_{n}-x_{n-2}\\x_{n}-x_{n-1}\end{array}\right]~~~~~(5.10)

Interpolazione mediante funzioni polinomiali spline

In Fig. 3.1 è riportata la curva spline ottenuta con AUTOCAD che interpola 5 punti e richiede come due ulteriori condizioni le due tangenti agli estremi. Eseguendo il comando spline si osserva che l’andamento della curva è molto sensibile ai valori delle due tangenti.

In Fig. 3.1 è riportata la curva spline ottenuta con AUTOCAD che interpola 5 punti e richiede come due ulteriori condizioni le due tangenti agli estremi. Eseguendo il comando spline si osserva che l'andamento della curva è molto sensibile ai valori delle due tangenti.


Interpolazione mediante funzioni polinomiali spline

Risolto il sistema di equazioni lineare (5.10), mediante le (5.9) è possibile calcolare i parametri dei segmenti delle cubiche della spline x=x(t). Si procede in modo analogo per le altre componenti y e/o z , così alla fine si ottiene la spline interpolante r(t)=r(x(t),y(t),z(t)).

Si ribadisce che la matrice della (5.10) è valida solo se la spline è naturale, se si impongono diverse condizioni occorre modificare in modo coerente la prima e l’ultima sua riga.

Scambio dati tra sistemi CAD

La diffusione di differenti modelli geometrici insieme alle differenze hardware dei sistemi CAD comportò che il database di un modello geometrico creato su un sistema CAD era differente dagli altri sistemi CAD, per cui era molto difficile e complicato trasferire uno stesso modello geometrico tra diversi sistemi CAD.

Pertanto, già alla fine degli anni ‘70 si pose il problema di come poter trasferire il database dei modelli geometrici tra differenti sistemi CAD.

In generale i dati che definiscono completamente un modello geometrico sono di quattro tipi: forma, non-forma, progetto e produzione.

I dati di forma sono tutte le informazioni geometriche e topologiche di un modello geometrico.
I dati non di forma sono le unità di misura, dati grafici per la visualizzazione dell’oggetto, ecc..
I dati di progetto sono informazioni che il progettista ottiene a seguito alle analisi sul modello geometrico, come le proprietà di massa, la meshiatura per analisi FEM, ecc..
Infine i dati di produzione sono informazioni riguardanti i processi di lavorazione, le tolleranze, lista dei materiali, ecc..

La prima descrizione di un formato dati standard (Neutral Format) si ebbe alla fine degli anni ‘70 in America con il formato IGES (Initial Graphics Exchange Specification) e riguardava solo dati di forma e non di forma, perché allora l’unico problema era di scambiare dati tra i sistemi CAD.

Scambio dati tra sistemi CAD

Nel 1980 l’ANSI adottò la prima versione IGES come standard nazionale e nel 1986 uscì la versione 3.0 che permetteva lo scambio anche di alcuni dati di progetto. Infine la versione 4.0 del 1988 includeva anche dati ottenuti dai modelli CSG.

Il modello di database dell’IGES si basa sul concetto di identità, che è l’unita fondamentale di informazione.

Tutti i dati di un prodotto sono espressi come una lista di entità predefinite a cui corrispondono dei numeri. L’IGES ha tre tipi di dati : geometrici, annotazioni e di struttura. Le entità geometriche definiscono la forma e includono: curve, superfici e solidi. Le annotazioni includono i vari tipi di dimensioni, le note, i simboli, ecc.. Le entità struttura includono i disegni, le proprietà di massa, materiali, ecc..

L’IGES utilizza due sistemi cartesiani di riferimento per memorizzare le entità geometriche, che sono lo MCS e il WCS. Se un’entità viene definita nel WCS , le viene assegnata anche una matrice di trasformazione che permette di poter passare dal WCS allo MCS.

Per ottenere una migliore integrazione tra sistemi CAD e CAM ne scaturì la necessità di scambiare anche i dati di produzione. Così nel 1985 venne definito il formato PDES ( Product Definition Exchange Specification) che permetteva lo scambio di tutti i quattro tipi di dati.

Lo sviluppo di questi ed altri formati indusse nel 1988 l’ISO a definire lo standard STEP (Standard for the Transfer and Exchange of Product Model Data) che si basava essenzialmente sui risultati ottenuti da IGES e PDES.

Scambio dati tra sistemi CAD

Con lo STEP è possibile trasferire tutti i quattro tipi i dati che definiscono completamente un modello geometrico, perché lo STEP considera tutti i dati dell’intero ciclo di vita del prodotto.

Lo STEP è stato progettato per essere completamento compreso in modo automatico dai sistemi CAD e non prevede l’intervento dell’uomo. Ad esempio, le tolleranze sono descritte non in forma simbolica che richiedono l’intervento dell’uomo per specificare le grandezze, ma in una forma che viene letta direttamente dal sistema CAD.

La principale differenza tra l’IGES e lo STEP è che mentre l’IGES si basa sul concetto di entità, lo STEP si basa sul concetto di applicazione, che contiene vari tipi di entità.

Oltre ai precedenti standard esistono altri standard proposti da produttrici di sistemi CAD, come lo DXF (Data eXchange Format), che è stato proposto dall’AUTOCAD, che permette di trasferire modelli CAD.

In generale, esistono due soluzioni per poter trasferire i dati tra differenti sistemi CAD/CAM, che sono: diretto e indiretto.

Scambio dati tra sistemi CAD

La soluzione diretta converte il database di un sistema CAD direttamente nell’altro, per cui richiede la conoscenza dei formati dei due nativi database.

La soluzione indiretta tiene conto degli standard, e consiste nel convertire il database di un sistema CAD in una struttura standard di database neutrale (neutral file), che è indipendente dal sistema CAD/CAM. Il database neutrale può essere così compreso e utilizzato da altri sistemi CAD.


Scambio dati tra sistemi CAD

La soluzione diretta richiede che per poter trasferire il database tra due sistema CAD, ogni sistema abbia due traslatori, uno per trasferire e l’altro per importare il database.
Pertanto, se vi sono n sistemi CAD che si devono scambiare i dati ci devono essere complessivamente n(n-1) traslatori.

Mentre con la soluzione indiretta ogni sistema CAD ha due traslatori, per se n sono il numero dei sistemi CAD, complessivamente ci devono essere2n traslatori.

Si osserva che quando n>3 è preferibile utilizzare la soluzione indiretta.

Attualmente, si preferisce utilizzare sempre la soluzione indiretta, perché permette di essere più sicuri di poter utilizzare anche in futuro un database che presenta un format di un neutral file.

Il programma software di un sistema CAD/CAM che trasla un file nativo in un format standard è chiamato preprocessore; viceversa il programma inverso è chiamato post_processore.

I file nativi di un sistema CAD si riconoscono per il tipo di estensione del file, così i file ottenuti dal modulo PART Design del CATIA hanno un’estensione CAD_Part, quelli creati dall’AUTOCAD hanno un’estensioni DWG, ecc..

I materiali di supporto della lezione

Appunti a cura del docente

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion