Triangulacion

PARTE I: TRIANGULACIÓN DE UNA NUBE DE PUNTOS
Definición: Dado un conjunto S={s1, ..., sn} de puntos de R2, llamamos triangulación de S a una partición de su cierre convexo en triángulos, tal que cada punto de S sea un vértice de un triángulo y viceversa.
Consideremos el siguiente algoritmo:
Entrada: S={s1, ..., sn}
1. Para cada par de vértices, añadir el segmento que los une si no corta aningún segmento anterior.
Este algoritmo voraz calcula una triangulación de S, con coste en tiempo O(n2). Sin embargo, la triangulación que proporciona dicho algoritmo no es útil en la mayoría de las aplicaciones, como por ejemplo en la interpolación de una función continua sobre una superficie.
Esta función puede representar un mapa de alturas, que se miden sólo en ciertos puntos (los de S), yque debe ser interpolada en el resto (esto es frecuente en los GIS). Podría darse una situación como la siguiente:
| |
FIGURA 1 | FIGURA 2 |
En la figura 1 se calcula la altura de P interpolando las de C, D, E. Si las alturas medidas en estos puntos son 100m, 70m y 20m respectivamente, la altura en P resultaría 53m. Si las alturas en A y B son 100m y 110m respectivamente, este valor para Presulta inadecuado. Esto no ocurre en la triangulación de la figura 2, en la que el valor en P depende de A, B y C, obteniéndose una altura de 106m.
Definición: Se dice que una triangulación T1 es mejor que otra T2, y se representa T2<=T1, si AT2<=AT1 (en orden lexicográfico), donde AT1 y AT2 son las listas de los ángulos ordenados de menor a mayor de T1 y T2 respectivamente.Definición: Una triangulación T se dice equilátera si no existe otra triangulación T’ tal que T<=T’.
La figura 2 es un ejemplo de triangulación equilátera, mientras que la de la figura 1 no lo es.
Una triangulación equilátera reduce el número de ángulos muy agudos, por lo que es mejor en cálculos que requieran precisión. Por esto es frecuente que en muchas aplicaciones sea preferible una triangulación deeste tipo a otra cualquiera.
La triangulación de una nube de puntos guarda una estrecha relación con el diagrama de Voronoi de dicha nube de puntos. Así, se tiene la siguiente
Definición: Dado un conjunto S={s1, ..., sn} de puntos de R2, el dual geométrico de su diagrama de Voronoi es una triangulación de los puntos de S. Dicha triangulación se llama triangulación de Delaunay.
Es decir, latriangulación de Delaunay se obtiene uniendo vecinos de Voronoi. Posee varias propiedades importantes:
* Minimiza el máximo radio de una circunferencia circunscrita.
* Maximiza el mínimo ángulo (de hecho, la triangulación de Delaunay es equilátera).
* Maximiza la suma de los radios de las circunferencias inscritas.
* La distancia entre cualquier par de vértices a través de aristas de latriangulación es, a lo sumo, una constante (2’42) por su distancia euclídea.
Sin embargo, calcular la triangulación de Delaunay a través del diagrama de Voronoi es difícil (a pesar de que el método sea óptimo, con coste O(n log n)), por lo que conviene disponer de otras técnicas para conseguirla.
Uno de estos métodos consiste en usar la siguiente relación:
Proposición: Sea S={s1, ..., sn} unconjunto de puntos de R2. Si proyectamos S sobre un paraboloide con ecuación z=x2+ y2 (esto es, asociamos a cada punto si=(xi, yi) del plano el punto (xi, yi, xi 2+ yi 2) de R3), entonces la proyección sobre R2 de la parte inferior del casco convexo de los puntos en el paraboloide es la triangulación de Delaunay de S.
Así, el algoritmo sería el siguiente
Entrada: S={s1, ..., sn}
1. Proyectarlos puntos de S sobre el paraboloide z=x2+ y2.
2. Calcular el casco convexo de los nuevos puntos.
3. Proyectar la parte inferior sobre el plano.
Un método más fácil de calcular la triangulación de Delaunay, aunque con un coste O(n2), es mediante giros de aristas, modificando una triangulación inicial hasta llegar a la de Delaunay.
Definición: Dados dos triángulos que comparten un...