Geometria Computacional

Esteu aquí

Inici » Estudis » Graus » Grau en Enginyeria Informàtica » Pla d'estudis » Assignatures » Geometria Computacional
Crèdits
6
Tipus
Optativa
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
MAT
Web
https://dccg.upc.edu/courses-geoc/
Mail
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

  1. Conèixer els diversos tipus de problemes que estudia la Geometria Computacional, així com les seves aplicacions.
    Competències relacionades:
  2. 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:
  3. Veure en acció diversos paradigmes algorísmics i diverses estructures de dades útils en problemes geomètrics.
    Competències relacionades:
  4. Aplicar resultats geomètrics a problemes reals.
    Competències relacionades:
  5. Saber resoldre problemes bàsics que es plantegen a la geometria computacional.
    Competències relacionades:
  6. Saber implementar les solucions plantejades a classe o les que es troben a la bibliografia bàsica de l'assignatura.
    Competències relacionades:
  7. Saber reconèixer els problemes geomètrics subjacents a les aplicacions, i proposar eines algorísmiques adequades per resoldre'ls.
    Competències relacionades:
  8. Practicar i millorar la capacitat de treballar en un entorn professional en llengua anglesa
    Competències relacionades: G3.2, G3.3, G3.1,

Continguts

  1. Introducció a la Geometria Computacional
    Els problemes que estudia la Geometria Computacional. Aplicacions. Terminologia. Eines bàsiques.
  2. Una eina bàsica
    Àrea orientada. Esquerra/dreta. Intersecció de dues rectes. Intersecció de dos segments. Gir orientat.
  3. Algorismes d'escombrat
    Algorisme de Bentley-Ottmann.
  4. 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.
  5. Envolupant convexa
    Algorismes de construcció de l'envolupant convexa d'un núvol de punts 2D.
  6. Dualitat. Intersecció de semiplans.
    Dualitat geomètrica. La dualitat associada a la paràbola unitat. Intersecció de semiplans i envolupant convexa.
  7. Triangulació de polígons
    Triangulació de polígons monòtons, descomposició d'un polígon en polígons monòtons.
  8. Proximitat
    Diagrames de Voronoi i les seves aplicacions
  9. Triangulacions de núvols de punts
    Triangulació de Delaunay.
  10. Arranjaments de rectes i plans
    Descripció, propietats i construcció. Nivells. Relació amb els diagrames de Voronoi.
  11. Localització en descomposicions del pla
    Diversitat d'estratègies. Complexitat del preprocessament vs eficiència de les consultes.
  12. Reconstrucció de formes
    Alpha-shapes, crust, anti-crust i beta-skeletons.
  13. Presentació de temes per part dels estudiants
    Extensions del temari de l'assignatura.

Activitats

Activitat Acte avaluatiu



Resolució de problemes

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: 5 7 8
Continguts:
Teoria
0h
Problemes
16.5h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
25h

Laboratori

Implementació d'algorismes geomètrics
Objectius: 4 6 8
Continguts:
Teoria
0h
Problemes
0h
Laboratori
13.5h
Aprenentatge dirigit
0h
Aprenentatge autònom
45h


Metodologia docent

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:

Nota Final = 0.2*P + 0.2*T + 0.35*L + 0.25*E

Bibliografia

Bàsica:

Complementaria:

Web links

Capacitats prèvies

- 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.