TIN: Triangulation Irregular Net
Para una mejor explicación se puede revisar:
http://es.wikipedia.org/wiki/Triangulación_de_Delaunay
A continuación trataré de explicar los procedimientos seguidos para su implementación en Autolisp.
El algoritmo desarrollado corresponde al incremental aleatorio, la secuencia de
operaciones, en grandes rasgos, es la siguiente:
En autolisp se puede aprovechar las funciones para el manejo de listas, como que se puede tener una lista con las coordenadas de los puntos y a partir de ella generar la lista que contiene la forma en que estos puntos se conectan entre sí formando la triangulación.
Teniendo una lista que contiene a los puntos representados por sus coordenadas, cada uno de esos puntos tienen una posición en la lista de manera que se les puede identificar por la posición que ocupan en la lista, de esta manera, al formar triángulos, lo vértices de cada uno de éstos se identifican con el índice de posición de cada punto en la lista de puntos.
Al obtener el triángulo grande que contiene a toda la nube se les asigna las posiciones 0, 1 y 2, es decir estos "puntos auxiliares" ocupan las primeras posiciones de toda la nube dejando a los puntos reales las posiciones de la 3 para adelante. Si se quiere se puede asignar, a estos tres puntos, las posiciones finales y empezar a insertar puntos contándolos desde la posición 0. El primer triángulo estaría definido por sus vértices (0 1 2).Con el primer punto de la nube se forman los tres primeros triángulos. En la siguiente figura se ilustra el triangulo grande que contiene a todos los puntos, el primer punto a insertar es el que se ha numerado como punto 3.
Se forma, con los vértices del triángulo grande, la siguiente secuencia de 3 triángulos:
3 - 0 - 1 … triángulo 1
3 - 1 - 2 … triángulo 2
3 - 2 - 0 … triangulo 3
… y el triángulo original (0 1 2) desaparece, o debe ser eliminado, o es reemplazado por estos 3 nuevos triángulos.
Estructura de datos para procesar la triangulación
Un aspecto importante para el desarrollo de los algoritmo de la triangulación, es la definición de una estructura de datos que facilite el procesamiento.
Al insertar el segundo punto de la nube, se deben generar 3 nuevos triángulos en reemplazo del triangulo que contiene al nuevo punto y la lista de triángulos quedaría de la siguiente forma suponiendo que el nuevo punto (punto 4) queda dentro del triángulo 3 – 1 – 2:
3 - 0 - 1 … triángulo 1
3 - 1 - 2 … triángulo a eliminar
3 - 2 - 0 … triangulo 2
4 - 3 - 1 … triangulo 3
4 - 1 - 2 … triangulo 4
4 - 2 - 3 … triangulo 5
- Dada la nube de puntos, determinar las coordenadas extremas, es decir las X máxima y mínima y las Y máxima y mínima.
- Con estos datos establecer un triángulo grande que contiene a todos los puntos y con el primer punto de la lista de puntos formar los tres primeros triángulos.
- Insertar punto por punto en la red de triangulos, identificando el triángulo que contiene a cada nuevo punto.
- Con el nuevo punto formar 3 nuevos triangulos con los vértices del triangulo que lo contiene.
- Verificar el cumplimiento de las condiciones de Delaunay, de no cumplir hacer el "flip" formando 2 nuevos triangulos en lugar de los 2 triangulos que no cumplen las condiciones.
- Terminados de insertar los puntos, finalmente hacer el dibujo de los triángulos y generar las curvas de nivel.
En autolisp se puede aprovechar las funciones para el manejo de listas, como que se puede tener una lista con las coordenadas de los puntos y a partir de ella generar la lista que contiene la forma en que estos puntos se conectan entre sí formando la triangulación.
Teniendo una lista que contiene a los puntos representados por sus coordenadas, cada uno de esos puntos tienen una posición en la lista de manera que se les puede identificar por la posición que ocupan en la lista, de esta manera, al formar triángulos, lo vértices de cada uno de éstos se identifican con el índice de posición de cada punto en la lista de puntos.
Al obtener el triángulo grande que contiene a toda la nube se les asigna las posiciones 0, 1 y 2, es decir estos "puntos auxiliares" ocupan las primeras posiciones de toda la nube dejando a los puntos reales las posiciones de la 3 para adelante. Si se quiere se puede asignar, a estos tres puntos, las posiciones finales y empezar a insertar puntos contándolos desde la posición 0. El primer triángulo estaría definido por sus vértices (0 1 2).Con el primer punto de la nube se forman los tres primeros triángulos. En la siguiente figura se ilustra el triangulo grande que contiene a todos los puntos, el primer punto a insertar es el que se ha numerado como punto 3.
Se forma, con los vértices del triángulo grande, la siguiente secuencia de 3 triángulos:
3 - 0 - 1 … triángulo 1
3 - 1 - 2 … triángulo 2
3 - 2 - 0 … triangulo 3
… y el triángulo original (0 1 2) desaparece, o debe ser eliminado, o es reemplazado por estos 3 nuevos triángulos.
Estructura de datos para procesar la triangulación
Un aspecto importante para el desarrollo de los algoritmo de la triangulación, es la definición de una estructura de datos que facilite el procesamiento.
Al insertar el segundo punto de la nube, se deben generar 3 nuevos triángulos en reemplazo del triangulo que contiene al nuevo punto y la lista de triángulos quedaría de la siguiente forma suponiendo que el nuevo punto (punto 4) queda dentro del triángulo 3 – 1 – 2:
3 - 0 - 1 … triángulo 1
3 - 1 - 2 … triángulo a eliminar
3 - 2 - 0 … triangulo 2
4 - 3 - 1 … triangulo 3
4 - 1 - 2 … triangulo 4
4 - 2 - 3 … triangulo 5
Aquí se puede hablar de padre e hijos, cuando un "triángulo padre" (el que contiene al nuevo punto) engendra "hijos" (los 3 triangulos que se forman con el nuevo punto) heredan su espacio, y el padre es sacrificado (eliminado).
De acuerdo a esto, el proceso de insertar un nuevo punto en la triangulación conlleva a determinar el triángulo que lo contiene, una vez encontrado este triángulo es reemplazado por 3 nuevos triángulos. El proceso que se sugiere implica que cada uno de estos triángulos nuevos debe pasar la prueba de Delaunay, a esto se le llama " legalizar" los triángulos. Una vez asegurada la legalización se tiene una triangulación "apta" para recibir un nuevo punto.
¿Cómo se verifica que un triángulo contiene o no a un punto?, una manera es, calculando el área de cada uno de los triángulos que se componen entre el punto y cada uno de los lados del triángulo, si cada área tiene el mismo signo que el del triángulo original, entonces el punto está dentro; si alguna de esas áreas es de signo contrario, el punto está afuera.
El área de un triángulo, dadas las coordenadas de sus vértices, es:
La secuencia de lectura de vértices debe conservar el sentido antihorario. Esto es muy importante porque permite asegurar que el cálculo del área de cualquiera de los triángulos tenga siempre el mismo signo.