Corso di Interazione Uomo-Macchina: Modellazione Geometrica
(a.a. 2000-2001)
-
E' richiesto aver frequentato il corso di Algoritmi e Strutture Dati.
Il corso si propone come obiettivo l'apprendimento dei fondamenti
teorici, delle tecniche e delle metodologie necessarie alla
rappresentazione e manipolazione di entita' geometriche per applicazioni
nell'ambito della computer graphics, dei sistemi informativi geografici,
e dei sistemi CAD.
-
Parte prima:
Strutture dati per entita' geometriche nel piano
-
Regioni piane: rappresentazioni mediante il contorno e
mediante lo spazio occupato; quadtree
-
Grafi planari e grafi piani: formula di Eulero e corollari
-
Suddivisioni piane: entita' geometriche e relazioni topologiche;
strutture dati per suddivisioni piane: liste di adiacenza,
struttura DCEL e struttura simmetrica
-
Strutture dati per triangolazioni: specializzazione delle strutture dati
per suddivisioni piane;
una struttura dati basata su triangoli
-
Algoritmi per estrazione di relazioni da strutture dati nel caso di
suddivisoni piane e triangolazioni
-
Parte seconda:
Algoritmi per la manipolazione di entita'
geometriche nel piano
-
Paradigmi per il progetto di algoritmi grometrici: uso di tecniche
algoritmiche classiche e introduzione a tecniche specifiche per il
trattamento dell'informaziione geometrica.
-
Primitive geometriche di base: calcolo dell'orientamento di una
terna di punti e applicazioni
-
Il problema della determinazione del guscio convesso:
nozioni di base, considerazioni di complessita' temporale.
-
Algoritmi per la costruzione del guscio convesso di un
insieme di punti: algoritmo di Graham, algoritmo di Jarvis,
QUICKHULL, un algoritmo basato su un approccio divide-et-impera
-
Problemi di ricerca geometrica nel piano: localizzazione di un punto
in un poligono semplice e
localizzazione di un punto in un poligono convesso (due metodi).
Localizzazione di un punto in una suddivisione piana: metodo
diretto e metodo delle strisce; uso della
tecnica di sweepline per la costruzione della struttura a strisce.
-
Problemi di intersezione nel piano.
Algoritmi per il calcolo dell'intersezione di segmenti;
algoritmi per la determinazione dell'esistenza di una
intersezione in un insieme di segmenti.
Il problema del calcolo dell'intersezione di poligoni semplici;
un algoritmo per il test di intersezione di poligoni semplici;
un algoritmo per il calcolo dell'intersezione di poligoni
convessi.
Altri testi consigliati
-
J.O'Rourke, Computational Geometry in C, Cambridge Univ. Press, 1993.
-
M. de Berg, M. Overmars, M. van Kreveld, O. Schwarzkopf,Computational
Geometry: Algorithms and Applications,Springer-Verlag, 1997.
-
M.J. Laszlo,
Computational Geometry and Computer Graphics in C++, Prentice Hall, 1996.