En aquest curs es presenten els algorismes geomètrics més freqüents que es troben darrera de moltes aplicacions informàtiques en àmbits tals com la informàtica gràfica, la visualització, la reconstrucció de formes, la visió per ordinador, els sistemes d'informació geogràfica, la robòtica, etc.
S'hi aprenen les eines adequades per al tractament de dades geomètriques massives (algorismes i estructures de dades) i explotar les propietats geomètriques dels problemes plantejats, per trobar-ne solucions òptimes.
Professorat
Responsable
Rodrigo Ignacio Silveira (
)
Hores setmanals
Teoria
2
Problemes
1.1
Laboratori
0.9
Aprenentatge dirigit
0
Aprenentatge autònom
6
Competències
Competències Transversals
Tercera llengua
G3 [Avaluable] - Conèixer l'idioma anglès amb un nivell adequat de forma oral i escrita, i en consonància amb les necessitats que tindran els graduats i les graduades en Enginyeria Informàtica. Capacitat de treballar en un grup multidisciplinar i en un entorn multilingüe i de comunicar, tant per escrit com de forma oral, coneixements, procediments, resultats i idees relacionats amb la professió d'enginyer tècnic en informàtica.
G3.2
- Estudiar amb materials escrits en anglès. Redactar un informe o un treball de tipus tècnic en anglès. Participar en una reunió tècnica en anglès.
Objectius
Conèixer els diversos tipus de problemes que estudia la Geometria Computacional, així com les seves aplicacions.
Competències relacionades:
Conèixer les capacitats de la combinació de les eines geomètriques amb les estructures de dades i els paradigmes algorísmics més adequats.
Competències relacionades:
Veure en acció diversos paradigmes algorísmics i diverses estructures de dades útils en problemes geomètrics.
Competències relacionades:
Aplicar resultats geomètrics a problemes reals.
Competències relacionades:
Saber resoldre problemes bàsics que es plantegen a la geometria computacional.
Competències relacionades:
Saber implementar les solucions plantejades a classe o les que es troben a la bibliografia bàsica de l'assignatura.
Competències relacionades:
Saber reconèixer els problemes geomètrics subjacents a les aplicacions, i proposar eines algorísmiques adequades per resoldre'ls.
Competències relacionades:
Practicar i millorar la capacitat de treballar en un entorn professional en llengua anglesa
Competències relacionades:
G3.1,
G3.2,
G3.3,
Continguts
Introducció a la Geometria Computacional
Els problemes que estudia la Geometria Computacional. Aplicacions. Terminologia. Eines bàsiques.
Una eina bàsica
Àrea orientada. Esquerra/dreta. Intersecció de dues rectes. Intersecció de dos segments. Gir orientat.
Algorismes d'escombrat
Algorisme de Bentley-Ottmann.
Problemes geomètrics bàsics sobre polígons
Intersecció recta/polígon, localització d'un punt en un polígon, rectes de suport a un polígon des d'un punt, etc.
Envolupant convexa
Algorismes de construcció de l'envolupant convexa d'un núvol de punts 2D.
Dualitat. Intersecció de semiplans.
Dualitat geomètrica. La dualitat associada a la paràbola unitat. Intersecció de semiplans i envolupant convexa.
Triangulació de polígons
Triangulació de polígons monòtons, descomposició d'un polígon en polígons monòtons.
Proximitat
Diagrames de Voronoi i les seves aplicacions
Triangulacions de núvols de punts
Triangulació de Delaunay.
Arranjaments de rectes i plans
Descripció, propietats i construcció. Nivells. Relació amb els diagrames de Voronoi.
Localització en descomposicions del pla
Diversitat d'estratègies. Complexitat del preprocessament vs eficiència de les consultes.
Reconstrucció de formes
Alpha-shapes, crust, anti-crust i beta-skeletons.
Presentació de temes per part dels estudiants
Extensions del temari de l'assignatura.
Activitats
ActivitatActe avaluatiu
Presentacions de teoria
Les sessions finals seran a càrrec dels estudiants. Objectius:1238 Continguts:
Només algunes sessions aniran a càrrec de la professora. La resta consistirà en la presentació i discussió de la resolució de problemes per part dels estudiants. Objectius:578 Continguts:
A les classes de teoria s'exposaran els continguts de l'assignatura, orientats a la resolució d'exemples i aplicacions.
Les classes de problemes consistiran en la resolució de problemes per part del professorat i també per part dels estudiants. Aquests problemes s'hauran enunciat i assignat amb prou antel·lació per tal que els estudiants encarregats de la seva resolució els hagin pogut pensar i puguin plantejar a la classe les seves propostes de solució. Els problemes seran de caire algorísmic.
L'objectiu de les classes de laboratori és implementar les solucions discutides a les classes de teoria i problemes, ja que la solució efectiva de problemes és objectiu de l'assignatura. Els problemes a resoldre a classe de laboratori començaran sent de complexitat elemental, per acabar amb la resolució d'un problema, preferiblement aplicat i real.
Mètode d'avaluació
Es tindrà en compte el treball dut a terme per cada estudiant all llarg del curs. Les quatre notes a considerar seran:
Problemes presentats a classe (P)
Exposició final del tema triat (T)
Exercicis de laboratori (L)
Examen (E)
La nota final de l'assignatura es calcularà d'acord amb les ponderacions següents:
- Programació
- Coneixements bàsics d'estructures de dades
- Coneixements bàsics de tècniques algorísmiques
Aquesta assignatura es recomana per a estudiants amb coneixements i interès en computació. Es recomana que els estudiants d'altres especialitats o sense especialitat tinguin això present en matricular-s'hi.
Els estudiants han de fer les seves presentacions en anglès. No es recomana l'assignatura a estudiants amb nivells d'anglès molt rudimentaris.