Corso di Interazione Uomo-Macchina: Modellazione Geometrica
Sillabo - A.A. 1998-99
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 geometrici: uso di tecniche
algoritmiche classiche e introduzione a tecniche specifiche per il
trattamento dell'informazione geometrica
-
Il problema della determinazione del guscio convesso
(rif. cap.3 Preparata Shamos)
- 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
-
Costruzione di una triangolazione di un poligono semplice
(rif. cap.1 O'Rourke + note)
-
Problemi di ricerca geometrica nel piano (rif. cap.2 Preparata Shamos)
- localizzazione di un punto in un
poligono semplice e in un poligono convesso,
- 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.
-
Quadtree come indici spaziali:
- costruzione di un quadtree per una triangolazione;
- localizzazione di un punto in una triangolazione mediante quadtree
-
Problemi di intersezione nel piano
(rif. cap.7 Preparata Shamos)
- Algoritmi per il calcolo dell'intersezione di segmenti
- Algoritmi per la determinazione dell'esistenza di una
intersezione in un insieme di segmenti
Riferimenti
-
F.P. Preparata, I. Shamos, Computational Geometry, Springer-Verlag,
II edizione, 1988, capitoli 2,3,7.
-
J. O'Rourke,
Computational Geometry in C, Cambridge University Press, II edizione,
1998, capitolo 1. Nota: in biblioteca c'e' anche I edizione (1994),
va bene anche quella.
-
Fotocopie dei lucidi fatti a lezione
-
Note sulla parte pratica disponibili
on-line