Teoría
- Triangulación de nube de puntos
- Triangulación de polígono
- Triangulación de peso mínimo (MWT)
- Aristas ligeras
- Triangulación de Greedy (Voraz)
- Triangulación de Delaunay
- Recortado de orejas (Triangulación de polígonos)
- MWT de un polígono
- MLT de un polígono
- MWT - Estrategia 1
- MWT - Estrategia 2
- MWT - Estrategia 3
- MLT - Estrategia 4
- MWT - Estrategia 5
Dado un conjunto S de puntos en el plano, una triangulación de S es una descomposición de la envolvente convexa de S en triángulos cuyos vértices son los de S y tal que cada par de triángulos de la descomposición tiene sus interiores disjuntos (Peñalver, 2006).
Dado un conjunto S de puntos en el plano, una triangulación de S es un grafo geométrico maximal sin cortes sobre S. Análogamente se define una triangulación de una nube de puntos del plano como una partición del cierre convexo en triángulos.

En geometría, la triangulación de un polígono o área poligonal es una partición de dicha área en un conjunto de triángulos.

De manera más precisa, una triangulación es una división del área en un conjunto de triángulos que cumplen las siguientes condiciones: la unión de todos los triángulos es igual al polígono original, los vértices de los triángulos son vértices del polígono original y cualquier pareja de triángulos es disjunta o comparte únicamente un vértice o un lado.
La triangulación de peso mínimo (MWT) es una triangulación completa con el menor peso posible. El problema de computar la MWT de un conjunto de puntos en el plano ha recibido una atención importante, especialmente cuando el peso es la distancia euclidea entre las aristas.
Se trata de un problema con complejidad NP-duro, e intentar encontrar una la triangulación MWT por fuerza bruta está fuera de cuestión: un grafo con 10 puntos puede tener hasta 2000 triangulaciones distintas.
La triangulación de Greedy y la triangulación de Delaunay se aproximan, pero no devuelve el resultado exacto de una MWT (Tan, 1993).
Una arista es ligera si su peso es el mínimo entre todas las demás aristas del grafo que corte con ella. Todas las aristas del cierre convexo de una nube de puntos son ligeras, ya que ninguna otra arista las corta.
A continuación vemos un ejemplo gráfico del cálculo de una arista ligera en una nube de puntos. La imagen que aparece más a la derecha son todas las aristas ligeras de una nube de puntos.

Se podría pensar que todas las aristas ligeras de una nube de puntos generasen una triangulación. Pero se puede ver en la imagen anterior que eso no es del todo cierto. Ya que se genera huecos al obtener todas las aristas ligeras de la nube de puntos.
El nombre de Voraz que recibe esta triangulación se debe a su método de construcción; las aristas se van añadiendo al grafo una a una en orden creciente de tamaño, con la salvedad de que una arista no puede cortar a otra más corta, ya añadida al grafo (Loera, 2009).
El algoritmo recibe una lista de puntos como entrada. El pseudocódigo del algoritmo es el siguiente:
1- Obtener todas las aristas posibles de la nube de puntos.
2- Ordenar la lista de aristas por tamaño de las aristas.
3- Obtner la primera arista de la lista (la más corta). Insertarla en el nuevo grafo si no se cruza con ninguna otra.
4- Repetir el paso 3 para todas las aristas de la lista.

Es una de las triangulaciones más interesantes por ser aplicable para la resolución de multitud de problemas aparentemente sin relación entre sí, debido a sus propiedades geométricas, y por contar con algoritmos bastante eficientes para su cálculo.

La triangulación de Delaunay es considerada uno de las triangulaciones “más uniformes”, es decir, es la que más se acerca una triangulación regular, es decir, asegura que los ángulos del interior de los triángulos son lo más grande posibles, la longitud de los lados de los triángulos es mínima y la triangulación formada es única.
Las propiedades principales de la triangulación de Delaunay son (Loera, 2009):
1. Es la triangulación que minimiza tanto el ángulo máximo como el radio de las circunferencias de sus triángulos.
2. Tres puntos de la nube de puntos son vértices de un mismo triángulo de la triangulación de Delaunay si y sólo si puede trazarse un círculo cuyo contorno
3. Dos puntos de la nube definen una arista de la triangulación si y sólo si es posible trazar un círculo cuyo contorno contenga a esos dos puntos pero en su interior no contenga ningún otro punto de la nube.
Se trata de un algoritmo para obtener una triangulación de un polígono, de complejidad O(n3), desarrollado por Meisters, en 1975. El algoritmo se base en buscar las orejas del polígono. Las orejas que se encuentran comprenden la triangulación.
Una diagonal es un segmento que está totalmente incluido en el polígono y que une dos vértices no consecutivos:

Un vértice Pi se llama oreja si el segmento (Pi-1, Pi+1) es una diagonal del polígono:

El algoritmo se base en la búsqueda de orejas. Cuando encuentra una, la arista creada con sus puntos adyacentes se añade a la triangulación. Se elimina el nodo oreja del polígono y sigue buscando otras orejas, hasta que el polígono tenga solamente 3 puntos.
En la imagen a continuación, vemos el resultado de aplicar el algoritmo sobre un determinado polígono:

Podemos construir la triangulación MWT de un polígono utilizando programación dinámica a través de un algoritmo de complejidad cúbica (Gilbert y Klincsek).
Preposición: Sea P = {p1, p2, p3, ... , pn} un conjunto de vértices de un polígono P orientado negativamente (a favor de las agujas del reloj). Entonces existe un algoritmo de complejidad O(n3) que calcula la triangulación de P que minimiza la suma de la longitud euclidiana de las aristas interiores (Tan, 1993).

Como el polígono P puede que no sea necesariamente convexo, la longitud de una arista inválida (una arista que tiene algún punto en el interior del polígono) es infinito.

Llamaremos de optcost(i,j) la longitud mínima de una triangulación del subpolígono cuyos puntos son pi, pi+1, ..., pj. La idea principal del algoritmo, sabiendo que están dentro de un polígono simple, la siguiente igualdad se mantiene:

El pseudocódigo del algoritmo es el siguiente:

Donde “L” es una matriz que guarda la los pesos de la triangulación. Se actualiza el valor de la matriz si el resultado parcial de la triangulación estudiada es menor que el resultado que aparece en la posición correspondiente en la matriz.
La matriz “S” guarda la información de las aristas de la triangulación. Se actualiza cuando se actualiza la matriz “L”.
La función “IsValidEdge” comprueba si la arista es válida. Es decir, si no es una arista exterior o que no se cruce con ninguna otra arista. Primero comprueba que la arista no se cruza con otra cualquiera. Si se cruza, la arista es válida. Si no se cruza, hay que comprobar si la arista es una arista exterior de un polígono cóncavo.
Una triangulación que de un polígono que minimiza la longitud de la arista más grande se llama “minmax length triangulation”: MLT.
Para encontrar la triangulación minmax de un polígono, basta modificar una función del algoritmo presentado en el apartado anterior (el de calcular la triangulación de peso mínimo de un polígono).
Se modifica la función Circunference(i,j,k). En vez de devolver el perímetro del triángulo, devolverá la longitud de la mayor arista.
Eso garantiza que se elija siempre las triangulaciones parciales que minimice la mayor de las longitudes de las aristas de las triangulaciones. Además, las triangulaciones MWT y MLT del mismo polígono no tienen por qué ser iguales:

En este ejemplo, se puede ver que ni la triangulación, ni el peso son iguales al comparar los dos algoritmos.
Como ya se ha dicho anteriormente, las estrategias son acciones que se ejecutan en secuencia para encontrar una aproximación de la triangulación de peso mínimo. La primera estrategia ejecuta los siguientes pasos:
- Calcular el cierre convexo de una nube de puntos.
- Poligonizar la nube de puntos utilizando el algoritmo de poligonización monótona.
- Calcular las regiones encontradas.
- Para cada región, aplicar el algoritmo MWT.
El cierre convexo y la poligonización se obtienen ejecutando los algoritmos correspondientes explicados en apartados anteriores. Una vez ejecutado los dos algoritmos, tenemos conjuntos de vértices, que representan diferentes polígonos: CC y Pol:

En la imagen de la izquierda vemos la nube de puntos, que contiene 14 nodos. En la imagen de la derecha, el resultado de aplicar los dos primeros pasos de la estrategias: poligonización y cierre convexo.
Visualmente, podemos ver que hay 5 regiones: la primera es la región que genera la poligonización, y las demás son los huecos que generan el cierre convexo y la poligonización.
El siguiente paso es aplicar MWT en cada región encontrada. Este paso es bastante sencillo, ya que el algoritmo MWT ya ha sido implementado anteriormente. El resultado es el siguiente:

La segunda estrategia para encontrar una aproximación de la triangulación de peso mínimo se basa en los siguientes pasos:
- Calcular el cierre convexo de la nube de puntos.
- Calcular la triangulación de Greedy.
- Calcular el árbol generador mínimo (MST) de la triangulación de Greedy.
- Unir las aristas del cierre y del MST.
- Obtener las ramas.
- Se formarán regiones. Obtener las regiones que se forman sin tener en cuenta las ramas generadas por el árbol mínimo.
- Asociar las ramas a las regiones encontradas.
- Para cada región encontrada, ejecutar el algoritmo de MWT.
El cierre convexo, la triangulación de Greedy y el MST se calculan utilizando las funciones explicadas en anteriores apartados. La gran dificultad de este algoritmo reside en dos partes: la primera es calcular las regiones, y la segunda es calcular la MWT teniendo en cuenta las ramas.
Una vez obtenido el cierre convexo y el MST, hay que identificar las ramas y eliminarlas del grafo para poder calcular las regiones. El algoritmo para identificar las aristas que pertenecen a rama es el siguiente:

El siguiente paso es obtner las regiones y añadirles las ramas. El último paso es aplicar MWT a cada región encontrada. Pero debido al hecho de que las regiones tienen “ramas” (nodos repetidos con la misma coordenada), hay que hacer algunas modificaciones del algoritmo MWT:
- Comprobar si la arista es válida: Si algún punto de la arista (i,j) pertenece a una rama, la arista es inválida solamente si se cruza con alguna arista existente.
- Comprobar si la arista es externa al polígono: Si uno de los puntos a estudiar es el inicio de la rama, no se tienen en cuenta los puntos de la rama para obtener el siguiente punto y el anterior en la lista de puntos.
- Comprobar si el triángulo es válido: Además de comprobar que las aristas son válidas, hay que comprobar que no haya ninguna rama en el interior del triángulo.
Además, aparece otro problema en la ejecución del algoritmo. Por tener puntos multiplicados, las matrices L y S tienen distintos índices que representan los mismos puntos. Lo que se hace en estos casos, es acceder siempre a solo una columna que correspondan los índices multiplicados. Por ejemplo, la secuencia de puntos del polígono anterior es: P = {1, 2, 3, 4, 5, 6, 5, 4}. Los índices 4 y 8 corresponden al punto 4, y por lo tanto, corresponderán a una solo columna. Lo mismo pasa con los índices 5 y 7, que corresponden al punto 5.
En algunos casos especiales, cuando se dan casos de alineaciones por causa de las ramas, o cuando la complejidad de la rama es muy alta, el algoritmo falla y no llega a ejecutar de forma satisfactoria. Pero en la mayoría de los casos, el algoritmo ejecuta con éxito.
Un ejemplo de una parte de la ejecución del algoritmo es la siguiente:

La estrategia 3, en general, es muy parecida a la estrategia anterior. La única diferencia es que se calcula el árbol generador mínimo de la nube de puntos, y no de la triangulación de Greedy. Por lo tanto, los pasos a ejecutar son:
1. Calcular el cierre convexo de la nube de puntos.
2. Calcular la triangulación de Greedy.
3. Calcular el árbol generador mínimo (MST) de la nube de puntos.
4. Unir las aristas del cierre y del MST.
5. Obtener las ramas.
6. Se formaran regiones. Obtener las regiones que se forman sin tener en cuenta las ramas generadas por el árbol mínimo.
7. Asociar las ramas a las regiones encontradas.
8. Para cada región encontrada, ejecutar el algoritmo de MWT.
Como se puede ver, la única diferencia en relación en la estrategia anterior es el paso 3.
A diferencia de las demás estrategias comentadas en el apartado anterior, la estrategia 4 es la única que no devuelve una aproximación, sino el resultado exacto. Por tanto, la complejidad deja de ser NP-hard, como las triangulaciones MWT, y pasa a ser de un algoritmo de tiempo polinomial (Tan, 1993).
La estrategia ejecuta las siguientes operaciones:
- Cálculo del cierre convexo
- Cálculo del grafo RNG.
- Juntar el cierre convexo y el grafo RNG
- Triangular (MLT) las regiones que se obtienen.
El algoritmo se basa en la idea de que las aristas del cierre convexo y del grafo RNG pertenecen a la triangulación MLT de la nube de puntos (Tan, 1993). Al juntar las aristas del cierre convexo y del grafo RNG, obtenemos un grafo donde podemos obtener regiones menores.

Sin embargo, las regiones que se obtienen no siempre son regiones simples, ya que algunas de ellas pueden contener ramas. Por tanto, se aplica el algoritmo modificado para triangulación MLT de regiones con ramas (parecido a lo que se hizo en las estrategias 2 y 3).
Se ha tenido que implementar otra forma de obtener las regiones, debido a que pueden aparecer regiones interiores, donde las aristas del cierre convexo no sirvan como soporte para buscar todas las regiones. Para ello, se ha implementado la estructura DCEL.
Lo que queda del algoritmo es similar a las demás estrategias: triangular cada una de las regiones obtenidas. Algunos pasos del algoritmo pueden ser vistos en la siguiente secuencia de imágenes:

La quinta estrategia implementada se base en las aristas ligeras de la nube de punto. Se dice que una arista es arista ligera si no existe otra arista que la cruce y que sea de menor longitud. Por tanto, los pasos de la estrategia son los siguientes:
- Obtener todas las aristas ligeras de la nube de puntos.
- Para todas las regiones que no sean triángulos, aplicar el algoritmo de triangulación MWT de polígonos.
Como ya se ha dicho anteriormente, el cálculo de todas las aristas ligeras de una nube de puntos no genera ninguna rama, es decir, todas las regiones son o triángulos u otros polígonos.
Si las aristas ligeras de una nube de puntos forman una triangulación, entonces la triangulación de Greedy de la nube de puntos es una triangulación MWT (Loera, 2009).
A continuación vemos la secuencia de pasos de la triangulación de una nube de puntos utilizando la quinta estrategia:
