Corso di Interazione Uomo-Macchina: Modellazione Geometrica
Sillabo - A.A. 2000-2001
Parte prima: Strutture dati per entita' geometriche nel piano
-
Regioni piane: rappresentazioni mediante lo spazio occupato (matrice e
quadtree), rappresentazioni mediante il contorno (regioni poligonali)
-
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
-
Primitive geometriche di base: calcolo dell'orientamento di una terna
di punti e applicazioni, intersezione fra due segmenti
-
Paradigmi per il progetto di algoritmi geometrici: uso di tecniche
algoritmiche classiche e introduzione a tecniche specifiche per il
trattamento dell'informazione geometrica
-
Rasterizzazione di una regione poligonale
-
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
-
Problemi di ricerca geometrica nel piano (rif. cap.2 Preparata Shamos)
- localizzazione di un punto in un
poligono semplice (algoritmo della semiretta)
e localizzazione di un punto in un
poligono convesso (algoritmo delle svolte, algoritmo dei settori)
- 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
(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
- Il problema del calcolo dell'intersezione di poligoni semplici
(cenno)
- Un algoritmo per il calcolo dell'intersezione di poligoni convessi
Riferimenti
-
F.P. Preparata, I. Shamos, Computational Geometry, Springer-Verlag,
II edizione, 1988, capitoli 2,3,7.
-
Dispense disponibili
on-line