Corso di Algoritmi Geometrici (a.a. 2004-2005)

Nuova Laurea in Informatica

Corso Algoritmi Geometrici (a.a. 2004-2005)

Docente: Prof. Enrico Puppo (email puppo@disi.unige.it)

Ricevimento studenti: martedì 14:30-16:30

Pre-requisiti

Linguaggio C, strutture dati di base (Programmazione)
Strutture dinamiche, puntatori (Algoritmi e strutture dati)
Strutture dati avanzate (CASD)

Sviluppo di interfacce, programmazione event-driven (Interfacce utente)

Vettori, matrici, sistemi di coordinate (Geometria)
Primitive geometriche, trasformazioni (Grafica interattiva)

Contenuti

Geometria computazionale nel piano
Strutture dati ed algoritmi per la rappresentazione e manipolazione di entità geometriche nel piano
Apprendimento di strumenti per la programmazione geometrica

Orario

Lunedì 9-11 Aula 710
Venerdì 8-11 Aula 710

Testi consigliati

Testi base per la geometria computazionale:

F.P. Preparata, M.I. Shamos, Computational Geometry - An Introduction, 1985, Springer-Verlag, ISBN 0-387-96131-3
M. de Berg, M. Van Kreveld, M. Overmars, O. Schwartzkopf, Computational Geometry - Algorithms and applications, Springer-Verlag, 1997, ISBN 3-540-61270-X

C++:

M. Black, Java to C++ transition tutorial: www.cs.brown.edu/courses/cs032/resources/C++tutorial.html
B. Stroustrup, The C++ Programming Language (3rd edition). Addison Wesley Longman, Reading, MA. 1997. ISBN 0-201-88954-4. 920 pages

Va bene qualunque altro manuale di C++

Materiale didattico

Dispense disponibili in rete

Lezioni:

Lezione 0 (28/9/04): notizie sul corso - file pdf 2 slide per pagina file pdf 6 slide per pagina
Lezione 1 (28/9/04): Entità geometriche nel piano - file pdf 2 slide per pagina file pdf 6 slide per pagina - Dispense Cap.1bis
Lezione 2 (1/10/04): Localizzazione di un punto in un poligono - file pdf 2 slide per pagina file pdf 6 slide per pagina - Dispense Cap.4 (prima parte)
Lezione 3 (1-5-12/10/04): Guscio convesso - file pdf 2 slide per pagina file pdf 6 slide per pagina - Dispense Cap.2
Lezione 4 (12-15/10/04): Suddivisioni piane - file pdf 2 slide per pagina file pdf 6 slide per pagina - Dispense Cap.3 (prima parte)
Lezione 5 (15-22-26-29/10/04 - 2/11/04): Strutture dati per suddivisioni piane - file pdf 2 slide per pagina file pdf 6 slide per pagina - Dispense Cap.3 (seconda parte)
Lezione 6 (5-16/11/04): Strutture dati per triangolazioni - file pdf 2 slide per pagina file pdf 6 slide per pagina - Dispense Cap.3 (seconda parte)
Lezione 7 (19-23-26/11/04): Localizzazione di un punto in una suddivisone piana (non è disponibile il file pdf - lezione basata sulle dispense Cap.4 - seconda parte)
Lezione 8 (26-30/11/04 - 3/12/04): Intersezione di segmenti (non è disponibile il file pdf - lezione basata sulle dispense Cap.5 - Prima parte)
Lezione 9 (3-14/12/04): Intersezione di poligoni (non è disponibile il file pdf - lezione basata sulle dispense Cap.5 - Seconda parte. Non è disponibile materiale sull'algoritmo sweep-line per intersecare poligoni semplici - Fare riferimento agli appunti.)
Lezione 10 (14/12/04): Triangolazione di poligoni semplici (non è disponibile il file pdf - lezione basata sulle dispense Cap.6)
Lezione 11 (17/12/03): Regolarizzazione di una suddivisione piana - sono disponibili le dispense da fotocopiare in segreteria didattica)
Lezione 12 (17-21/12/03): Localizzazione di un punto in una sufddivisione mediante il metodo delle catene - sono disponibili le dispense da fotocopiare in segreteria didattica)
Lezione 13 (21/12/03): Triangolazione di un poligono monotono (cenni) - sono disponibili le dispense da fotocopiare in segreteria didattica)

Risorse software:

FAQ

Q: Le lezioni si sovrappongono con quelle di altri corsi che seguo. Cosa posso fare?
A: Se siete in una situazione “standard” fatecelo presente e vedremo di modificare gli orari se possibile. Se invece siete in una situazione particolare (esami indietro, lavoro, …) fatecelo presente lo stesso, ma non credo potremo farci granché.