Corso di Interazione Uomo-Macchina: Modellazione Geometrica
Sillabo - A.A. 1999-2000
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
-
Primitive geometriche di base: calcolo dell'orientamento di una terna
di punti e applicazioni
-
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 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
(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
- Un algoritmo per il test di intersezione di poligoni semplici
- 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