Enginyeria en Informàtica (3371)
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.
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.