Questo programma mostra una possibile implementazione di alcuni algoritmi di quadratura e
di triangolazioni dipendenti dai dati (data dependent triangulation).
In particolare e' stato preso in esame l'algoritmo del LOP (Local Optimization Procedure), che cerca,
modificando la triangolazione, di approssimare alcuni criteri di ottimalità.
Nella nostra implementazione sono stati presi in esame 3 diversi criteri, dando la
possibilità all'utente di confrontarli su 10 funzioni di test diverse.
Sulla mesh (triangolazione) è anche possibile valutare la quadratura (integrale di volume) usando 4 diverse formule.
Il programma permette anche di visualizzare triangolazioni vincolate, con la
possibilità di applicare l'algoritmo del LOP e le formule di quadratura sulla mesh vincolata.
Oltre a questo viene fornito un piccolo programma di utilità che permette di convertire una triangolazione del TRIPACK(una libreria matematica scritta in fortran che permette di
costruire triangolazioni vincolate) nel nostro formato di input.
Il programma può essere lanciato con due diversi tipi di linea di comando:
nome-programma file-dei-vertici file-dei triangoli
nome-programma file-dei vertici file-dei-triangoli file-dei-triangoli-vincolati
Nel primo caso viene caricata la triangolazione descritta dal file dei vertici. Nel secondo caso è data la possibilità di rappresentare una triangolazione vincolata. Il secondo file dei triangoli descrive i triangoli che formano i vincoli della triangolazione. L'unione dei triangoli descritti nei due files deve essere una partizione del dominio. Coppie di files di questo tipo possono essere ottenute con il programma tri2our con input un file elaborato con il TRIPACK.
La struttura del file dei vertici è:
n+1
x0 y0
x1 y1
...
xn yn
Nella prima riga è specificato il numero di vertici componenti la triangolazione e in sequenza sono elencati i vertici a coppie in formato decimale a virgola mobile. Da notare che i vertici sono codificati partendo da 0.
La struttura del file dei triangoli è:
n+1
p0 q0 r0
p1 q1 r1
...
pn qn rn
Nella prima riga è specificato il numero di triangoli formanti la triangolazione e successivamente in ogni riga è specificato un triangolo. Il triangolo è descritto con gli indici dei vertici corrispondenti nel file dei vertici.
In questa sezione sono descritti i comandi per interagire con il programma.
Mouse:
tasto sinistro più movimento causa una rotazione della superficie,
tasto destro più movimento verticale causa uno zoom dell'immagine,
tasto centrale più movimento causa una traslazione dell'immagine.
Tastiera:
n: sposta il lato evidenziato sul successivo nel triangolo di appartenenza
N: sposta il lato sul triangolo adiacente (apparentemente non cambia niente, provate a premere n)
z: suddivide la triangolazione in una più fitta. I nuovi vertici aggiunti sono i baricentri dei triangoli esistenti
x: abilita e disabilita la visualizzazione dei bordi dei triangoli
p: abilita e disabilita il disegno delle normali associate a ciascun triangolo
q: seleziona la modalità di visualizzazione (triangolazione, funzione originale, sovrapposizione delle precedenti)
u: avvia il LOP utilizzando il criterio ABN
i: avvia il LOP utilizzando il criterio JND
o: avvia il LOP utilizzando il criterio DLP
t: impone uno scambio di diagonale nei due triangoli adiacenti al lato evidenziato
0 - 9 Funzioni test (per maggiori informazioni fare riferimento alla bibliografia)
c: calcola gli integrali con i 4 criteri sulla triangolazione attiva e stampa i risultati.
Strutture dati
Nel programma per la rappresentazione interna della triangolazione è stata utilizzata una struttura denominata Half Edge. Ogni lato della triangolazione è associato a due mezzi lati (half edge). Ogni half edge comprende un vertice e un puntatore al lato successivo, nonché un puntatore alla faccia di appartenenza. In questo modo è semplice gestire le operazioni di disegno e modifica della struttura. Intuitivamente un half edge può essere immaginato come un vettore applicato ad un vertice e che punta ad un altro.
Procedure interessanti
LOP: esegue l'algoritmo di ottimizzazione locale sulla mesh utilizzando il criterio passato come input (CrABNCriteria,CrJNDCriteria,CrDLPCriteria).
OperateFlip: esegue lo scambio della diagonale sul quadrilatero corrente.
Integral: applica un metodo di integrazione alla mesh sommando i contributi di ogni triangolo ottenuti con la formula passata come parametro.
Criteri del LOP
Il LOP analizza tutti i lati che compongono la mesh, e per ognuno, attraverso un criterio di
ottimalità, sceglie se mantenere il quadrilatero o scambiare la diagonale
(vedere in figura).
I criteri implementati in questo programma sono 3 :
1) ABN (Angle Between Normal) Questo criterio sceglie i due triangoli che minimizzano l'angolo compreso tra le due normali ai piani interpolanti.
2) JND (Jump of Normal Derivatives) Questo criterio sceglie i due triangoli che minimizzano l'angolo tra
il vettore differenza tra le due normali ai piani e il lato ortogonale alla diagonale del quadrilatero in esame.
3) DLP Questo criterio sceglie i due triangoli che minimizzano l'errore tra la funzione
nota nei 4 vertici e i piani interpolanti.
Criteri di integrazione
Il primo criterio implementato è di ordine 1 e interpola il triangolo con un piano passante per il baricentro.
Nota: in questa presentazione si utilizzano le coordinate baricentriche del triangolo.
Il secondo criterio è di ordine 2 e utilizza i punti medi sui lati del triangolo.
Il terzo criterio è di ordine 2 e utilizza punti interni descritti qui di seguito.
L'ultimo criterio è di ordine 3 e utilizza 4 punti, tra cui il baricentro.
Il programma e' stato scritto in C++ e richiede la presenza delle OpenGL e delle librerie GLut (freeware). Informazioni sul pacchetto GLut possono essere reperite in questi siti: www.pobox.com/~nate/glut.html (versione per Windows e source code) e http://www.opengl.com.
voronoi: questo programma scritto da Fortune è stato utilizzato per generare una triangolazione di Delaunay di partenza (I nostri files di esempio sono stati generati con questo programma). Il programma comunque opera con una qualsiasi triangolazione passata come input.
tri2our: questo programma di conversione trasforma una triangolazione vincolata del TRIPACK nel nostro formato di input, suddividendo in due file i triangoli vincolati e quelli liberi.
Funzione di Franke triangolata
Funzione di Franke con gli stessi vertici ma ottimizzata con LOP con criterio ABN
Esempio di visualizzazione di triangolazione vincolata
Funzione WaterFalls ottimizzata con LOP con criterio ABN (triangolazione e vista 3D)
File .zip con sorgenti ( 14Kb )
Il makefile incluso è scritto per gcc
Files di esempio di triangolazioni
N. Dyn and S. Rippa, Data dependent triangulation for scattered data interpolation and finite element approximation, Applied Numerical Mathematics 12 (1993)
N. Dyn D.Levin and S. Rippa, Data dependent triangulation for Piecewise Linear Interpolation, IMA Journal of Numerical Analysis 10 (1990)
Tripack files e documentazione
