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.