1 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones TEMA 4: TRIANGULACIONES
2 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Triangulaciones de nubes de puntos (modelado de terrenos) Triangulaciones de polígonos
3 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Modelado de terrenos
4 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
5 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones ¿QUÉ ES UN S.I.G.? (Sistema de Información Geográfica) Visualización de la información: geográfica, numérica, estadística, etc. Transformación Análisis Recolección DATOS Taquímetro / GPS Interpolación de información Sistema dinámico Mapas topográficos
6 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones ¿QUÉ ES UN S.I.G.? (Sistema de Información Geográfica) Visualización de la información: geográfica, numérica, estadística, etc. Transformación Análisis Recolección DATOS
7 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
8 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
9 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
10 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
11 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
12 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
13 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
14 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
15 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
16 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones 10 0 0 6 4 1240 19 20 36 28 23 890 1000 980 990 1008 0 0 10 6 4 1240 19 20 36 28 23 890 1000 980 990 1008
17 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones 10 0 0 6 4 1240 19 20 36 28 23 890 1000 980 990 1008 0 0 10 6 4 1240 19 20 36 28 23 890 1000 980 990 1008 23 985
18 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
19 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
20 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones P={p 1,p 2,...,p n } conjunto de puntos en el plano T= triangulación de P con m triángulos Vector de ángulos de T: V(T)={ 1, 2,..., 3m } con 1 2 3m V(T) > V(T’) si existe i {1,...,3m} tal que j = ’ j si j’ii>’i T es la triangulación Equilátera de P={p 1,p 2,...,p n } si V(T) V(T’), para toda triangulación T’ de P.
21 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
22 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Triangulación de Delaunay (dual de Voronoi)
23 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Objetivo: Probar que la triangulación de Delaunay es la equilátera.
24 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones p3p3 p1p1 p2p2 p4p4 11 22 33 44 55 66 p3p3 p1p1 p2p2 p4p4 11 22 33 44 55 66 *=min { i } *=min { j } p 1 p 2 es legal si * * Triangulación legal: todas sus aristas internas son legales Equilátera implica legal
25 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Flip diagonal Triangulaciones legales
26 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Flip diagonal
27 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Caracterización de las triangulaciones legales p3p3 p2p2 p1p1 p4p4 p 1 p 2 es legal p 4 C(p 1,p 2,p 3 ) Criterio del Circunciclo
28 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones p3p3 p2p2 p1p1 p4p4 p 1 p 2 es legal p 3 C(p 1,p 2,p 4 ) Criterio del Circunciclo Caracterización de las triangulaciones legales
29 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones p2p2 p1p1 p3p3 Teorema del Arco Capaz (Thales) p 1 > p 2 > p 3
30 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
31 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
32 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones * = 1 > 5
33 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Algoritmo para encontrar triangulaciones legales Partir de cualquier triangulación En cada arista interior: comprobar si es legal por el criterio del circunciclo si no lo es, realizar un flip
34 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Dado un punto q llamaremos círculo máximo vacío al mayor círculo centrado en q que no contiene a ningún generador del diagrama en su interior. La bisectriz entre dos generadores define un borde de Vor(P) si y sólo si existe un punto q sobre dicha bisectriz tal que el círculo máximo vacío centrado en q contiene solamente a estos dos generadores en su frontera. Un punto q es vértice de Vor(P) si y sólo si el círculo máximo vacío centrado en q contiene tres o (en el caso de tratarse de un diagrama degenerado) más generadores en su frontera
35 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Proposición 1. P={p 1,p 2,...,p n } puntos en el plano. p i p j p k es un triángulo de Delaunay si y sólo si C(p i,p j,p k ) no contiene a ningún punto de P en su interior.
36 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Proposición 1. P={p 1,p 2,...,p n } puntos en el plano. p i p j p k es un triángulo de Delaunay si y sólo si C(p i,p j,p k ) no contiene a ningún punto de P en su interior.
37 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Proposición 1. P={p 1,p 2,...,p n } puntos en el plano. p i p j p k es un triángulo de Delaunay si y sólo si C(p i,p j,p k ) no contiene a ningún punto de P en su interior.
38 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Proposición 1. P={p 1,p 2,...,p n } puntos en el plano. p i p j p k es un triángulo de Delaunay si y sólo si C(p i,p j,p k ) no contiene a ningún punto de P en su interior.
39 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Proposición 2. P={p 1,p 2,...,p n } puntos en el plano. p i p j es una arista de Delaunay si y sólo si existe un círculo a través de p i p j que no contiene a ningún punto de P en su interior.
40 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Proposición 2. P={p 1,p 2,...,p n } puntos en el plano. p i p j es una arista de Delaunay si y sólo si existe un círculo a través de p i p j que no contiene a ningún punto de P en su interior.
41 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Teorema 1. P={ p 1,p 2,...,p n } puntos en el plano. T = triangulación de P. T es legal si y sólo si T es la triangulación de Delaunay de P.
42 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Algoritmo para encontrar la triangulación de Delaunay Partir de cualquier triangulación En cada arista interior: comprobar si es legal por el criterio del circunciclo si no lo es, realizar un flip
43 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Algoritmo de flips (Sibson, 1978) O(n 2 ) Transforma una triangulación arbitraria en la de Delaunay realizando flips en triángulos adyacentes y decidiendo por el criterio del circunciclo. Divide y vencerás (Guibas y Stolfi, 1985) O(nlog n) Algoritmo del barrido plano (Fortune, 1987) O(nlog n) Algoritmo incremental de inserción aleatoria (Guibas, Knuth y Sharir, 1992) O(nlog n) Comienza con un triángulo ficticio e inserta aleatoriamente los puntos en la triangulación. Se generaliza a R 3.
44 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones El algoritmo incremental
45 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones El algoritmo incremental
46 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
47 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
48 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
49 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
50 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
51 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
52 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
53 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
54 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
55 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
56 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Las aristas creadas por la inserción de un nuevo punto son aristas de Delaunay
57 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Las aristas ilegales se transforman en aristas de Delaunay tras un único flip.
58 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Tras el proceso: No quedan aristas ilegales No se produce un bucle infinito Obtenemos la triangulación de Delaunay
59 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones ¿Qué hacer con las líneas de rotura?
60 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Construimos la triangulación de Delaunay
61 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones El problema de las líneas de rotura
62 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones p y q son visibles si el segmento pq no corta a la restricción. El problema de las líneas de rotura
63 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones pqr es un triángulo de la TDR si C(p,q,r) no contiene puntos que sean visibles desde p, q y r. El problema de las líneas de rotura
64 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones pqr es un triángulo de la TDR si C(p,q,r) no contiene puntos que sean visibles desde p, q y r. El problema de las líneas de rotura
65 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones pqr es un triángulo de la TDR si C(p,q,r) no contiene puntos que sean visibles desde p, q y r. El problema de las líneas de rotura
66 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
67 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
68 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
69 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones
70 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Bibliografía Computational Geometry: an introduction. F. P. Preparata y M. I. Shamos. Springer-Verlag, 1985. Computational Geometry in C. J. O’Rourke. Cambridge University Press, 1998.
71 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Triangulación de Delaunay http://wwwpi6.fernuni-hagen.de/Geometrie-Labor/VoroGlide/ http://www.cs.cornell.edu/Info/People/chew/Delaunay.html Modelado de terrenos http://www.cs.ubc.ca/spider/snoeyink/terrain/Demo.html http://www.fhi-berlin.mpg.de/grz/pub/preusser/java1.1/ TrivialApplet.html Applets
72 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Triangulaciones de polígonos
73 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Problema de la Galería de Arte En 1973, Víctor Klee planteó el problema de determinar el mínimo número de guardias suficientes para cubrir el interior de una galería de arte con un número n de paredes. C En 1975, Chvatal dio la respuesta a dicha pregunta y en 1978 Fisk dio otra demostración. El primer paso de su demostración era triangular el polígono. ¿Es todo polígono triangulable?
74 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Lema 4.1: Todo polígono tiene al menos un vértice convexo.
75 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Lema 4.2: Todo polígono con más de cuatro vértices admite una diagonal. Teorema 4.2: Todo polígono admite una triangulación.
76 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Lema 4.3: Toda triangulación de un n-polígono tiene n-2 triángulos y utiliza n-3 diagonales. Lema 4.4: La suma de los ángulos internos de un n- polígono es (n-2)p.
77 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Proposición 4.1: El dual de una triangulación es un árbol de valencia máxima tres.
78 Matemática Aplicada I Alberto Márquez http://ma1.eii.us.es/miembros/almar Tema 4: Triangulaciones Ejercicios 1.¿Cuál es la suma de los ángulos exteriores de un polígono? 2.Probar o dar un contraejemplo: todo árbol binario es el dual de la triangulación de un polígono. 3.Cuántas triangulaciones tiene el siguiente polígono: 4.Probar que toda triangulación de un polígono tiene al menos dos orejas, donde una oreja es un triángulo que sólo comparte una arista con otro triángulo. ¿Ocurre lo mismo con triangulaciones de nubes de puntos?