course 2013-2014

Enginyeria en Informàtica

Geometria Computacional (12478)

Introducció
La Geometria és una disciplina molt utilitzada en algunes àrees d'Informàtica, especialment en Infografia, Robòtica, CAD/CAM, i Sistemes d'Informació Geogràfica. La Geometria Computacional s'orienta a resoldre problemes en aquestes àrees, sobre una base geomètrica, i subministrant algorismes eficients, amb estructures de dades adients.

Objectius
Aquesta assignatura de Geometria Computacional té dos objectius:
- consolidar els conceptes geomètrics bàsics, de forma que la seva comprensió pugui ajudar al seu millor maneig en el desenvolupament de noves aplicacions.
- introduir els aspectes més característics de l'aproximació moderna a la Geometria Computacional.

Temari

La consolidació dels apectes geomètrics bàsics comprèn temes linials, afins i de perspectiva, així com també una mica les corbes i superfícies.
Es fa combinant l'explicació dels temes amb un conjunt d'exercicis que han de fer els alumnes, dins l'horari de teoria.
La introducció dels aspectes més específics de Geometria Computacional es farà seguint dos threads; un dels fils serà fonamentalment pràctic, que començarà des de la primera semana, que inclou tres pràctiques, la primera relativament elemental, la segona més avançada, i la tercera d'iniciació a temes de recerca. Aquest fil es desenvolupa dins l'horari de pràctiques. L'altre fil es farà a la darrera part de l'horari de teoria, i serà una introducció més conceptual als temes de Geometria Computacional.

Els temes de consolidació són:

Tema 1 Geometria afí i mètrica

Tema 2 Transformacions geomètriques 2D i 3D; representació perspectiva

Tema 3 Corbes i superfícies que es complementaràn amb el:

Tema 4 Aspectes de Geometria Computacional

El fil de pràctiques és:

Pràctica 1 (3 setmanes): Creació d'un octree a partir d'un mesh

Pràctica 2 (3 setmanes): Triangulació de Delaunay

Pràctica 3 (4 setmanes): Treball de recerca

Avaluació
L'avaluació serà fonamentalment contínua, respecte al lliurament de problemes de llistes, i de les tres pràctiques. Criteris específics per a cada pràctica es donen als respectius enunciats.

Bibliografia
Hi ha una web de recursos de Geometria Computacional a http://compgeom.cs.uiuc.edu/~jeffe/compgeom/compgeom.html

Els llibres bàsics recomanats són:

Joan Trias Pairó: Geometria per a la informàtica gràfica i el CAD, Edicions UPC, Barcelona, 1999.
(Aquest llibre té un acompanyant de laboratori: Joan Trias Pairó: Laboratori de Geometria Computacional, Edicions UPC, Barcelona, 1996.)

Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications (Second Edition), Springer-Verlag, 2000. (Es pot consultar la introducció, taula de continguts i un capítol (el 7) a http://www.cs.uu.nl/geobook/)

També són interessants els problemes M. Mora, V. Sacristán, J. Trias: Problemes de GeoC, accessibles des de http://www-ma2.upc.es/~geoc/geoc.html, 2000.
Els apunts del curs de Geometria per a sistemes multimèdia de V. Sacristán compilen de forma eficient un conjunt de conceptes bàsics i útils (es poden baixar des de http://www-ma2.upc.es/~vera/docencia.html).
També són interessants com a referència de diferents apartats els apunts que es troben a http://www-ma2.upc.es/~geoc/geoc.html.

Altres llibres de consulta són:
Franco P. Preparata, Michael Ian Shamos: Computational Geometry: an Introduction, Springer Verlag, New York [etc.], 1985.

Són interessants també alguns capítols dels llibres:
Michael F. Worboys: Geographic Information Systems: a Computing Perspective, Taylor & Francis, London, 1995.
Marc van Kreveld et al. (eds.): Algorithmic Foundations of Geographic Information Systems, Springer Lecture Notes in Computer Science 1340, Berlin & New York, 1997.
Theodosios Pavlidis: Algorithms for Graphics and Image Processing, Springer Verlag, 1982.