Ricco- maresca-outsider-art-gallery-1024x576.png...
21
Geometría Computacional , MAT-125 Triangulación de Polígonos: Problema de la Galería de Arte. http://ilevel.biz/wp-content/uploads/2013/07/Ricco- maresca-outsider-art-gallery-1024x576.png
Transcript of Ricco- maresca-outsider-art-gallery-1024x576.png...
Geometría Computacional , MAT-125
Triangulación de Polígonos: Problema de la Galería de Arte.
http://ilevel.biz/wp-content/uploads/2013/07/Ricco-maresca-outsider-art-gallery-1024x576.png
¿Cuántas cámaras necesitamos para vigilar una galería y cómo decidimos dónde ponerlas?
Problema de la Galería de Arte
Galería: Región poligonal en R2. consideramos solamente polígonos simples (no auto-intersecciones, no hoyos).
Posición de la cámara: Punto en el polígono. No hay restricciones de rango en la cámara. ¿Cuándo ve una cámara a un punto del polígono?
Cuando el segmento de recta entre la posición de la cámara y el punto del polígono es un segmento abierto completamente contenido en el polígono.
Polígono
Un polígono (simple) P es la región cerrada del plano, acotada por una colección finita de segmentos de recta que forman una curva cerrada que no se auto-interseca.
Teorema de curvas (polígonos) de Jordan
La frontera @P de un polıgono P particiona el plano en dos partes. En
particular, los dos componentes de R2 \ @P son el interior acotado y el exterior
no acotado.
https://www.ics.uci.edu/~eppstein/161/960307.html
https://www.ics.uci.edu/~eppstein/161/960307.html
Todos los puntos en un segmento de recta que no intersequen a ∂P deben estar en el mismo conjunto.
los conjuntos pares y los conjuntos impares están conectados.
Si hay un camino entre puntos de diferentes conjuntos, entonces el camino debe intersecar a ∂P.
Podemos obtener una descomposición de un polygono P en pedazos más simples por medio de diagonales. Una diagonal de un polígono, es un segmento de recta que conecta dos vértices de P y que está en el interior de P, sin tocar ∂P excepto en sus puntos extremos. Decimos que dos diagonales no se cruzan si no comparten ningún punto interior.
Triangulación de un polígono
Una triangulación de un polígono P es la descomposición de P en triángulos por un conjunto maximal de diagonales sin cruces.
Devadoss, O´Rourke. Discrete and Computational Geometry.
Triangulaciones
¿Cuántas triangulaciones diferentes tiene un polígono? ¿Cuántos triángulos hay en cada triangulación de un polígono dado? ¿Es cierto que todo polígono tiene una triangulación? ¿Tiene que tener todo polígono al menos una diagonal?
Todo polıgono con mas de tres vertices tiene una diagonal.
Como podemos descomponer cualquier polígono (con más de 3 vértices) en dos polígonos más pequeños usando una diagonal, por inducción vemos que existe una triangulación.
Devadoss, O´Rourke. Discrete and Computational Geometry.
Todo polígono tiene una triangulación.
Probar que toda región poligonal con hoyos poligonales admite una triangulación de su interior.
Ejercicio:
Número de triángulos en una triangulación.
Toda triangulación de un polígono P con n vértices tiene n-2 triángulos y n-3 diagonales.
Muchas pruebas y algoritmos de triangulaciones de polígonos requieren de un triángulo particular para iniciar la inducción o la recursión. Triángulos “oreja” : Tres vértices consecutivos a, b, c forman una oreja de un polígono si ac es una diagonal del polígono. El vértice b se llama punta de la oreja.
El número de triangulaciones que tenga un polígono dado P dependerá de la “forma” del polígono. Una medida crucial de la forma son los ángulos internos en sus vértices. Un vértice de P se llama reflex si su ángulo es mayor a π. Un vértice de P se llama convex si su ángulo es menos o igual a π. Algunas veces distinguiremos a los vértices flat cuyo ángulo es exactamente π. Un vértices es estrictamente convex si su ángulo es estrictamente menor a π. Un polígono P es convexo si todos sus vértices son convex.
Devadoss, O´Rourke. Discrete and Computational
Existe una diagonal entre cualquiera dos vértices no adyacentes de un polígono P si y solo si, P es un polígono convexo.
Para un polígono convexo P, donde cada par de vértices no adyacentes determina una diagonal, es posible contar el número de triangulaciones de P usando solamente el número de vértices. El resultado es el número de Catalan (por el matemático belga Eugène Catalan).
Cn =1
n+ 1
✓2n
n
◆.
Devadoss, O´Rourke. Discrete and Computational Geometry.
Una oreja de un polígono es un triángulo formado por tres vertices consecutivos dentro del cual no hay otro vértice del polígono.
El segmento de recta entre vi-1 e vi+1 se llama diagonal.
El vértice vi se llama punta de la oreja.
Un triángulo consiste en una sola oreja aunque se puede poner como punta de la oreja cualquiera de los tres vértices.
Un polígono de cuatro o más lados siempre tiene al menos dos orejas que no traslapan ( probado por G.H. Meisters, Polygons have ears, Amer. Math. Monthly). Esto sugiere un algoritmo recursivo para la triangulación.
Si podemos encontrar una oreja en un polígono con n≥4 vertices y removerla, tendremos un polígono de n-1 vertices y podemos repetir el proceso.
Una implementación inmediata tomaría O(n3).
D. Eberly. Geometric Tools. (www.geometrictools.com)
Ear clipping triangulation
Almacenar el polígono como una lista doblemente ligada de manera a poder eliminar rápidamente las puntas de las orejas:
• construir la lista toma O(n).
Iterar sobre los vértices para encontrar orejas.
• para cada vértice vi y su triángulo correspondiente (vi-1, vi, vi+1) (el indexado es módulo n por lo que vn=v0 y v-1 = vn-1) probar todos los otros vértices para ver si hay alguno dentro del triángulo.
• Si no hay ninguno dentro del triángulo es una oreja, si hay al menos uno no lo es.
D. Eberly. Geometric Tools. (www.geometrictools.com)
Ear clipping triangulation
Es suficiente considerar solamente los vértices reflex para ver si están contenidos en el triángulo.
• vértice reflex - el ángulo interior formado entre las dos aristas que lo comparten es mayor a 180 grados.
• vertex convex - el ángulo interior formado entre las dos aristas que lo comparten es menor a 180 grados.
La estructura de datos de polígono mantiene 4 listas doblemente ligadas simultáneamente:
• los vertices del polígono en una lista ligada cíclica,
• los vertices convex en una lista lineal,
• los vertices reflex en una lista lineal,
• las puntas de orejas en una lista ligada cíclica.
reflex
convex
D. Eberly. Geometric Tools. (www.geometrictools.com)
Una vez construida la lista inicial de vertices reflex y orejas, se eliminan las orejas una a una.
si vi es una oreja que se elimina, la configuración de la arista en los vertices adyacentes puede cambiar. Si el vertice adyacente es...
• convexo es fácil convencerse que va a seguir siendo convexo.
• oreja, no se queda oreja necesariamente después de eliminar a vi.
• reflex, es posible que se vuelva convex o posiblemente oreja después de eliminar a vi.
Después de eliminar a vi, si un vértice adyacente es convex, probar si es una oreja iterando sobre los vértices reflex y probando si están contenidos en el triángulo de ese vertex. Hay O(n) orejas, hay que verificar O(n) veces por oreja. El proceso total de eliminación de orejas toma O(n2).
D. Eberly. Geometric Tools. (www.geometrictools.com)
Vertices convex C = { 0, 1, 3, 4, 6, 9 }
Vertices reflex R = { 2, 5, 7, 8 }
Vertices oreja E = { 3, 4, 6, 9 }
1
2
3
45
6
78
9
0
Ejemplo
D. Eberly. Geometric Tools. (www.geometrictools.com)
Vertices convex C = { 0, 1, 3, 4, 6, 9 }
Vertices reflex R = { 2, 5, 7, 8 }
Vertices oreja E = { 3, 4, 6, 9 }
D. Eberly. Geometric Tools. (www.geometrictools.com)
1
2
3
45
6
78
9
0
Eliminar oreja 3 :
Primer triángulo en la triangulación T0 = ⟨ 2, 3, 4⟩.
