Triangulación de un polígono

Una triangulación genérica de un polígono cóncavo

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 por un conjunto máximal de diagonales que no se cruzan.[1]​

Definición

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.
• Cualquier pareja de triángulos es disjunta o comparte únicamente un vértice o un lado.

La definición anterior es la estándar en geometría computacional aunque en ciertos contextos, al hablar de triangulaciones, se puede hacer caso omiso del segundo requisito. En tal caso, no se requiere que los vértices de los triángulos sean vértices del polígono y para referirse a las triangulaciones que sí satisfacen el requisito se habla de triangulaciones completas.[2]​[3]​

La partición de una superficie en triángulos se denomina también malla triangular en trigonometría y en geometría elemental. Y desde el punto de vista de la teoría de grafos, las triangulaciones son «grafos no orientados sin aristas múltiples», cuyos subgrafos son "círculos de tres nodos" (y correspondientemente tres aristas). Una generalización de las mallas triangulares son las mallas poligonales.

Propiedades de las triangulaciones de un polígono

Las 42 posibles triangulaciones para un heptágono. Este número viene dado por el número de Catalan.

A continuación se muestran propiedades de la triangulación de un polígono simple:

• Todo polígono simple admite siempre al menos una triangulación.

Demostración

Demostramos la existencia de triangulaciones por inducción fuerte sobre el número de vértices del polígono. Caso base: ${\displaystyle n=3}$ En este caso, el polígono es un triángulo, por lo que, de hecho, ya está triangulado y, en particular, existe una triangulación. Paso inductivo: Sea ${\displaystyle n>3}$ y suponemos el teorema cierto para todo ${\displaystyle m<n}$. Veamos que se cumple para ${\displaystyle n}$. Demostramos en primer lugar que existe una diagonal. Dibujemos el polígono ${\displaystyle P}$ de ${\displaystyle n}$ lados. Sea ${\displaystyle v}$ el vértice (o uno de los vértices) de más hacia la izquierda de ${\displaystyle P}$. Sean ${\displaystyle u,w}$ los dos vértices vecinos de ${\displaystyle v}$ en la frontera de ${\displaystyle P}$. Si el segmento ${\displaystyle {\overline {uw}}}$ cae en el interior e ${\displaystyle P}$, hemos encontrado una diagonal. (Nótese que esto no es necesario, pues el polígono no tiene por qué ser convexo). Supongamos pues que el segmento ${\displaystyle {\overline {uw}}}$ no cae completamente en el interior de ${\displaystyle P}$. Esto quiere decir, porque hemos elegido ${\displaystyle v}$ un vértice de más hacia la izquierda de ${\displaystyle P}$, que existe algún vértice en el interior del triángulo ${\displaystyle \triangle uvw}$ o sobre la diagonal ${\displaystyle {\overline {uw}}}$. De entre estos vértices, elijamos el (o uno de los) más alejado(s) de la diagonal ${\displaystyle {\overline {uw}}}$ y llamémosle ${\displaystyle v'}$. El segmento ${\displaystyle {\overline {vv'}}}$ no puede ser cruzado por ningún lado de ${\displaystyle P}$, porque ese lado tendría un extremo en el interior del triángulo ${\displaystyle \triangle uvw}$ más alejado de ${\displaystyle {\overline {uw}}}$ que ${\displaystyle v'}$, lo que entra en contradicción con la definición de este último. Por tanto, ${\displaystyle {\overline {vv'}}}$ es una diagonal de ${\displaystyle P}$. En cualquier caso, hemos visto que existe una diagonal. Esa diagonal divide a ${\displaystyle P}$ en dos subpolígonos de un número de vértices estrictamente menor que ${\displaystyle n}$. Por tanto, por inducción, cada unos de esos subpolígonos puede ser triangulado y estas dos triangulaciones, junto con la diagonal encontrada, inducen una triangulación en ${\displaystyle P}$ que, en particular, es triangulable. Esto concluye la demostración. ${\displaystyle \quad \square }$

• Toda triangulación de un polígono simple con ${\displaystyle n}$ vértices consiste en exactamente ${\displaystyle n-2}$ triángulos.[1]​[4]​

Demostración

Hacemos la demostración por inducción fuerte sobre el número de lados ${\displaystyle n}$. Caso base: ${\displaystyle n=3}$. Trivialmente, cuando ${\displaystyle n=3}$, el polígono es directamente un triángulo, es decir, ya está triangulado, y esta es su única triangulación. En particular, hay ${\displaystyle n-2=3-2=1}$ triangulación. Paso inductivo: Sea ${\displaystyle n>3}$ y supongamos el teorema cierto para toda ${\displaystyle m<n}$. Dada una triangulación cualquiera de ${\displaystyle P}$, elegimos una diagonal cualquiera de esta. La arista divide ${\displaystyle P}$ en dos subpolígonos ${\displaystyle P_{1},P_{2}}$ con un número de vértices ${\displaystyle m_{1},m_{2}}$ estrictamente menor en cada caso que ${\displaystyle n}$. Cada vértice de ${\displaystyle P}$ está en exactamente en uno de los dos subpolígonos excepto los de los extremos de la diagonal, que están en ambos. Por tanto, ${\displaystyle m_{1}+m_{2}=n+2}$. Ahora, por hipótesis de inducción, todas las triangulaciones de ambos subpolígonos tienen ${\displaystyle m_{1}-2,m_{2}-2}$ triángulos. Por tanto, la triangulación arbitraria de ${\displaystyle P}$ tiene ${\displaystyle m_{1}-2+m_{2}-2=n+2-2-2=n+2}$ triángulos, lo que acaba la demostración. ${\displaystyle \quad \square }$

• Cada triangulación de un polígono simple de ${\displaystyle n}$ vértices usa ${\displaystyle n-3}$ diagonales.[1]​[4]​

Demostración

Demostramos el resultado por inducción fuerte sobre el número de vértices ${\displaystyle n}$. Caso base: ${\displaystyle n=3}$. En este caso, el polígono es un triángulo, que ya está triangulado sin añadir diagonales. En particular, el número de diagonales de la triangulación es de ${\displaystyle 0=3-3=n-3}$. Paso inductivo: Sea ${\displaystyle n>3}$. Supongamos el teorema cierto para todo ${\displaystyle m<n}$ y veamos que se cumple para ${\displaystyle n}$. Tomemos una triangulación arbitraria del polígono ${\displaystyle P}$, que sabemos que existe por la primera demostración. Tomemos una diagonal cualquiera de esa triangulación. Dividamos ${\displaystyle P}$ por esa diagonal en dos subpolígonos ${\displaystyle P_{1},P_{2}}$ con número de vértices ${\displaystyle m_{1},m_{2}}$, respectivamente, estrictamente más pequeños que ${\displaystyle n}$. Tenemos, además, como en la segunda demostración, que cada vértice de ${\displaystyle P}$ está exactamente en uno de los dos subpolígonos excepto los extremos de la diagonal por la que han sido definidos, que están en ambos. Por tanto, ${\displaystyle m_{1}+m_{2}=n+2}$. Por hipótesis de inducción, las triangulaciones de cada uno de los subpolígonos que induce la triangulación arbitrariamente tomada en ${\displaystyle P}$ tienen ${\displaystyle m_{i}-3}$ diagonales. Por tanto, la triangulación inicial tiene, sumando la diagonal que definía los subpolígonos, ${\displaystyle m_{1}-3+m_{2}-3+1=n+2-3-3+1=n-3}$ diagonales, como queríamos demostrar. ${\displaystyle \quad \square }$

• Todo polígono convexo de ${\displaystyle n}$ vértices puede ser triangulado en abanico en ${\displaystyle n-2}$ triángulos, escogiendo un vértice y trazando todas las diagonales a vértices no vecinos.
• De forma similar, todo polígono con un único vértice cóncavo puede ser triangulado en abanico en ${\displaystyle n-2}$ triángulos, escogiendo como origen el único vértice cóncavo y trazando las diagonales al resto de vértices.
• La cantidad total de triangulaciones posibles de un polígono convexo de ${\displaystyle n}$ vértices es igual al (${\displaystyle n-2}$)-ésimo número de Catalan, es decir: ${\displaystyle t_{n}=C_{n-2}={\frac {1}{n-1}}{\binom {2n-4}{n-2}}}$, la demostración fue encontrada por Leonhard Euler,[5]​[6]​ y se basa en hacer una biyección entre triangulaciones de un polígono de ${\displaystyle n}$ lados y árboles binarios de ${\displaystyle n-1}$ hojas poniendo la raíz de estos en el triángulo de un lado prefijado del polígono, un nodo en cada otro triángulo, y ramas entre nodos de triángulos contiguos. Como de árboles binarios hay ${\displaystyle C_{n-2}}$ y hay una biyección con las triangulaciones, hay la misma cantidad de estas últimas.

Triangulaciones especiales

Ejemplos de triangulación de un polígono. 1. Abanico. 2. Mínimo peso 3. Delaunay

Triangulación voraz de un polígono ejecutada paso a paso.

Con frecuencia interesa calcular una triangulación que presente alguna propiedad especial, como por ejemplo evitar que algún triángulo tenga un área mayor de un umbral dado.

• La Triangulación de Delaunay que, entre otras propiedades, maximiza el ángulo mínimo de los triángulos (evitando que aparezcan ángulos demasiado agudos).
• La Triangulación voraz, que trata de emparejar los vértices más cercanos entre sí.
• La Triangulación de peso mínimo (Minimum-weight Triangulation), que minimiza la suma total de longitudes de las aristas de los triángulos.
• La Triangulación en abanico de un polígono convexo, eligiendo un vértice y trazando diagonales a los vértices no vecinos. Esta triangulación puede ser rápidamente calculada en tiempo lineal.

Un polígono monótono puede ser triangulado en tiempo lineal mediante alguno de los algoritmos siguientes:

• Algoritmo de Alain Fournier y D.Y. Montuno,[7]​
• Algoritmo de Godfried Toussaint.[8]​

Aplicaciones

Existen muchas aplicaciones que utilizan la triangulación de un polígono como uno de los pasos para la solución del problema. Por ejemplo:

• Desde la antigüedad se ha utilizado para calcular el área de parcelas de terreno de forma irregular. El método más habitual es dividir la parcela en triángulos, cuyo cálculo de área es trivial conociendo la longitud de los lados, y sumar las áreas de los mismos. Posteriormente se desarrolló la llamada fórmula del agrimensor, para calcular áreas de terrenos y polígonos en general.
• El problema de la galería de arte donde se resuelve el problema de visibilidad desde el mínimo número de puntos posible.
• La deformación de superficies (especialmente tejidos) mediante el método de elementos finitos.

Generalización a dimensiones superiores

Descomposición de un cubo en 6 tetraedros, el simplejo de ${\displaystyle \mathbb {R} ^{3}}$

La definición de triangulación puede ser fácilmente adaptada para elementos de dimensiones superiores. Así, se define una triangulación de un politopo en un espacio ${\displaystyle \mathbb {R} ^{n}}$ como un complejo simplicial formado por una colección de simplejos de ${\displaystyle \mathbb {R} ^{n}}$tales que:

• La unión de todos los simplejos es igual al politopo.
• Los vértices de los simplejos son vértices del polítopo original.
• Cualquier par de simplejos es disjunto o su intersección es exactamente alguna cara común.

Por ejemplo, en caso del espacio ${\displaystyle \mathbb {R} ^{3}}$cualquier volumen encerrado en el interior de una superficie discreta cerrada, puede ser descompuesto en una serie de tetraedros (que es el simplejo de ${\displaystyle \mathbb {R} ^{3}}$). Esto tiene aplicaciones importantes como el cálculo de volúmenes de objetos complejos, o la deformación mediante el método de elementos finitos.

Referencias

1. de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark. Computational Geometry (3 edición). Springer. ISBN 978-3-540-77973-5. 
2. Trias Pairó, Joan (2003). «3.9 Triangulación de polígonos simples». Geometría para la informática gráfica y CAD. Vol. 129 de Politext: Matemática y Estadística (1ª edición). Barcelona: Edicions UPC. p. 151. ISBN 9788483017029. Consultado el 25 de noviembre de 2011. 
3. Hernández Cifre, María Ángeles y José Antonio Pastor González. «6.2.1 Triangulaciones. La característica de Euler-Poincaré». Un curso de geometría diferencial: teoría, problemas, soluciones y prácticas con ordenador. Vol. 47 de Textos universitarios, Consejo Superior de Investigaciones Científicas (España). España: CSIC, Ediciones Doce Calles. p. 232. ISBN 9788400091545. Consultado el 25 de noviembre de 2011. 
4. O'Rourke, Joseph. Computational Geometry in C (2 edición). Cambridge University Press. ISBN 9780521649766. 
5. Pickover, Clifford A., The Math Book, Sterling, 2009: p. 184.
6. Jesús D. Loera; Jörg Rambau; Francisco Santos (2010). Triangulations:Structures for Algorithms and Applicaciones. Algorithms and Computation in Mathematics (en inglés) 25. Springer. ISBN 9783642129704. 
7. Fournier, A.; Montuno, D. Y. (1984), «Triangulating simple polygons and equivalent problems», ACM Transactions on Graphics 3 (2): 153-174, ISSN 0730-0301, doi:10.1145/357337.357341 .
8. Toussaint, Godfried T. (1984). «A new linear algorithm for triangulating monotone polygons». Pattern Recognition Letters 2 (3): 155-158. doi:10.1016/0167-8655(84)90039-4.  |fechaacceso= requiere |url= (ayuda)

• Datos: Q3045660
• Multimedia: Polygon triangulation / Q3045660