Geometria Computacional

Crèdits
6
Tipus
  • GRAU: Optativa
  • GCED: Optativa
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
MAT
Web
https://dccg.upc.edu/courses-geoc/
Mail
rodrigo.silveira@upc.edu
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

Altres

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.1, G3.2, G3.3,

    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àsic

    Complementari

    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.