Data
|
Què hem fet ?
|
Material
|
05/10/2010
|
Presentació
de l'assignatura.
Conceptes bàsics.
LLista de Problemes. |
Complexitat
d'algorismes (pdf)
Conceptes geomètrics bàsics (ps)
Transformacions 2D (pdf),
Transformacions 3D (pdf), Projeccions (pdf)
|
| 15/10/2010 |
Algorisme d'escombrat per a calcular la intersecció de segments (D. Mount pp 26-31).
|
Algorismes d'escombrat:
intersecció de segments (ppt1,ppt2,web)
|
| 19/10/2010 |
Test
d’intersecció de intervals sobre recta.
Test d'intersecció de segments.
Fita inferior intersecció d'intervals sobre recta
i de segments del pla.
Polígons. Test de simplicitat d'un polígon.
Intersecció de polígons.
|
Test d'intersecció de segments (web)
Polígons (pdf)
Intersecció de polígons i tests d'intersecció (ppt).
|
| 22/10/2010 |
Classe Problemes. |
Resolució Exercicis.
1. Complexitat de funció suma zero.
2. Complexitat ordenació per selecció.
3. Comprovar complexitat dividir i vèncer.
4. Ordenar la unió de dues llistes
ordenades de n elements en total i de m llistes ordenades de n elements en
total.
5. Ordenar per abscisses els vèrtexs d’un polígon convex.
6. Ens donen de forma desordenada els costats d’un polígon
convex, orientats de manera que el poligon queda a l’esquerra de cada costat.
Donar els vèrtexs del polígon en sentit positiu.
|
| 26/10/2010 | Test d'intersecció de polígons.
Envolupant convexa 2D.
Algorismes càlcul envolopant convexa
(Mount pp 12-26).
Fita
inferior.
Poliedres. |
Envolopant convexa al pla (pdf,ppt,web).
Poliedres (pdf). |
| 02/11/2010 | DCEL (Mount pp 103-104).
Envolupant convexa a l'espai.
Intersecció de
semiplans.
Algorisme Dividir i Vèncer.
| DCEL (pdf1, pdf2, web).
Envolopant convexa a l'espai (ppt,
web1, web2) .
Intersecció de semiplans (ppt).
|
| 05/11/2010 | Classe Problemes. | Resolució Exercicis:
7. Test intersecció regions poligonals convexes: temps O(n+m).
8.
Test punt interior polígon convex: temps O(n). Test repetit punt
interior polígon convex: temps O(log n) amb preprocés O(n).
9. Càcul tangent superior a dos polígons convexos separats per recta vertical en temps O(n).
10. Determinar cares visibles poliedre convex
visibles des de punt exterior en temps O(n).
Aclariments dubtes enunciats Problemes 1 a 6. |
| 09/11/2010 | Intersecció de
semiplans (cont):
Comentar algorisme increm. aleat.
Fita inferior.
Programació lineal: introducció.
Solució en dimensió 1.
|
Programació lineal: introducció (ppt).
|
| 12/11/2010 | Solució en dimensió 2 (Mount pp 40-45).
Test d'intersecció de semiplans.
| Mètode
incremental (pdf, ppt)
Entrega Problemes 1 a 6 en format pdf via e-mail. |
| 16/11/2010 | Triangulacions.
Triangulació d'un polígon (Mount pp 31-35)
Triangulació d'un conjunt de punts.
Triangulació de Delaunay: propietats.
Triangulació de Delaunay: algorismes Dividir i vèncer, incremental aleatori (Mount pp 62-66).
| Triangulacions (pdf).
Triangulació d'un polígon (pdf)
Fita inferior (pdf). |
| 19/11/2010 | Triang. Delaunay: algorismes de Watson i Lawson
Triangulació d'un
PSLG.
Diagrames de Voronoi.
Dualitat: D. Voronoi
<--> T. Delaunay.
Algorismes Dividir i
Vèncer i Fortune.
Diagrames de Voronoi generalitzats.
| Triangualció de Delaunay (ppt).
D. Voronoi (ppt1).
Dualitat entre D.
Voronoi i T. Delaunay (pdf).
Algorisme Dividir i
Vèncer (web), Algorisme Fortune (ppt2, web).
Diagrames de Voronoi generalitzats (ppt).
|
| 23/11/2010 | Localització de punts en subdivisions
planars.
Tetraedralitzacions.
Malles.
Generació de malles.
Simplificació de malles.
| Localització de punts (ppt).
Tetraedralitzacions (pdf).
Malles (pdf1, pdf2).
Generació de malles al
pla (ppt).
Generació de malles sobre supeficies (ppt).
Simplificació i nivells de detall (pdf).
|
| 26/11/2010 | Classe Problemes. | Entrega Problemes 7 a 9 en format pdf via e-mail.
Comentaris solució problemes 1 a 6.
Pensar possibles treballs voluntari.
|
| 30/11/2010 | Càcul parell de punts més propers.
Càlcul veins més propers.
| Algorisme càcul parell de punts més propers (ppt).
Algorismes de Càlcul veins més propers (ppt) |
| 03/12/2010 | Classe Problemes. | Comentaris solució problemes 7 a 9.
Aclariments dubtes enunciats Problemes 10 a 15.
Propostes treball voluntari. |
| 07//12/2010 | No lectiu
| |
| 10/12/2010 | No hi ha classe | |
| 14/12/2010 | Estructures de cerca en dominis geomètrics (Mount pp 75-82). | Cerca en dominis ortogonals (ppt1, pdf1, pdf2, ppt2, pdf3) |
| 17/12/2010 | No hi ha classe | |
| 21/12/2010 | Aclariments dubtes Problemes 10 a 15. | Entrega Problemes 10 a 15 en format pdf via e-mail. |
| 28/01/2011 | | Entrega treball voluntari. |
