Estudia

• CB01 Posseir i comprendre coneixements que aportin una base o oportunitat de ser originals en el desenvolupament i/o aplicació d'idees, sovint en un context de recerca.
• CTI09 Capacitat per aplicar mètodes matemàtics, estadístics i d'intel·ligència artificial per a modelar, dissenyar i desenvolupar aplicacions, serveis, sistemes intel·ligents i sistemes basats en el coneixement.
• CTI10 Capacitat per utilitzar i desenvolupar metodologies, mètodes, tècniques, programes d'ús específic, normes i estàndards de computació gràfica.

1. Introducció. Exemples d'aplicació: Google Maps, sistemes de navegació GPS, recerques locals (restaurants de Girona).

2. Subdivisions planars i la seva representació: DCEL, etc. Localització de punts en subdivisions planars.

3. Interseccions d'un conjunt de segments. Intersecció de polígons. Superposició de subdivisions planars. Simplificació de línies poligonals.

4. Triangulació d'un polígon. Triangulació d'un conjunt de punts. Triangulació de Delaunay.

5. Diagrama de Voronoi. Problemes de proximitat.

6. Estructures de dades espacials: quadtree, kd-tree, R-tree, etc. Cerca en rangs ortogonals.

7. Càlcul dels k-veïns més propers i k-veïns reversos més propers.

8. Representació de xarxes espacials (carreteres, carrers, etc).Models de terrenys: xarxes irregulars trianguladas (TINs).

9. Càlculs en xarxes espacials i TINs: camí més curt, diagrama de Voronoi, etc.

10. Patrons de moviment en bases de dades de trajectòries.

Activitats d'avaluació:

Avaluació del treball fet a les sessions pràctiques (25%) i del projecte final de la assignatura (75%). En ambdós casos no hi haurà recuperació.

Criteris específics de la nota «No Presentat»:
Es considerarà no presentat a qui no hagi entregat el treball fet a les sessions pràctiques o no hagi entregat el projecte final de l'assignatura.