En geometría computacional , la triangulación de polígonos es la partición de un área poligonal ( polígono simple ) P en un conjunto de triángulos , [1] es decir, encontrar un conjunto de triángulos con interiores que no se intersecan por pares cuya unión es P.
Las triangulaciones pueden considerarse casos especiales de grafos de líneas rectas planas . Cuando no hay agujeros ni puntos añadidos, las triangulaciones forman grafos planos exteriores máximos .
A lo largo del tiempo, se han propuesto varios algoritmos para triangular un polígono.
.svg/1280px-Polygon_Triangulations_(heptagon).svg.png)
Es trivial triangular cualquier polígono convexo en tiempo lineal en una triangulación de abanico , agregando diagonales desde un vértice a todos los demás vértices vecinos no más cercanos.
El número total de formas de triangular un n -gono convexo mediante diagonales que no se intersecan es el ( n −2)º número de Catalan , que es igual a
una fórmula encontrada por Leonhard Euler . [2]
Un polígono monótono se puede triangular en tiempo lineal con el algoritmo de A. Fournier y DY Montuno, [3] o el algoritmo de Godfried Toussaint . [4]
Una forma de triangular un polígono simple se basa en el teorema de las dos orejas , como el hecho de que cualquier polígono simple con al menos 4 vértices sin agujeros tiene al menos dos " orejas ", que son triángulos con dos lados siendo las aristas del polígono y el tercero completamente dentro de él. [5] El algoritmo consiste entonces en encontrar dicha oreja, eliminarla del polígono (lo que da como resultado un nuevo polígono que todavía cumple las condiciones) y repetir hasta que solo quede un triángulo.
Este algoritmo es fácil de implementar, pero más lento que otros algoritmos, y sólo funciona en polígonos sin agujeros. Una implementación que mantenga listas separadas de vértices convexos y cóncavos se ejecutará en tiempo O( n 2 ) . Este método se conoce como recorte de orejas y, a veces, recorte de orejas . Hossam ElGindy, Hazel Everett y Godfried Toussaint descubrieron un algoritmo eficiente para cortar orejas . [6]
Un polígono simple es monótono con respecto a una línea L , si cualquier línea ortogonal a L interseca el polígono como máximo dos veces. Un polígono monótono se puede dividir en dos cadenas monótonas . Un polígono que es monótono con respecto al eje y se llama y-monótono . Un polígono monótono con n vértices se puede triangular en tiempo O( n ) . Suponiendo que un polígono dado es y-monótono, el algoritmo voraz comienza caminando sobre una cadena del polígono de arriba a abajo mientras agrega diagonales siempre que sea posible. [1] Es fácil ver que el algoritmo se puede aplicar a cualquier polígono monótono.
Si un polígono no es monótono, se puede dividir en subpolígonos monótonos en tiempo O( n log n ) utilizando un enfoque de línea de barrido . El algoritmo no requiere que el polígono sea simple, por lo que se puede aplicar a polígonos con agujeros . En general, este algoritmo puede triangular una subdivisión plana con n vértices en tiempo O( n log n ) utilizando espacio O( n ) . [1]
Un gráfico útil que suele asociarse a una triangulación de un polígono P es el gráfico dual . Dada una triangulación T P de P , se define el grafo G ( T P ) como el grafo cuyo conjunto de vértices son los triángulos de T P , siendo dos vértices (triángulos) adyacentes si y solo si comparten una diagonal. Es fácil observar que G ( T P ) es un árbol con grado máximo 3.
Hasta 1988, si un polígono simple se puede triangular más rápido que O( n log n ) tiempo era un problema abierto en geometría computacional. [1] Luego, Tarjan y Van Wyk (1988) descubrieron un algoritmo de tiempo O( n log log n ) para triangulación, [7] posteriormente simplificado por Kirkpatrick, Klawe y Tarjan (1992). [8] Siguieron varios métodos mejorados con complejidad O( n log * n ) (en la práctica, indistinguible del tiempo lineal ). [9] [10] [11]
Bernard Chazelle demostró en 1991 que cualquier polígono simple puede triangularse en tiempo lineal, aunque el algoritmo propuesto es muy complejo. [12] También se conoce un algoritmo aleatorio más simple con tiempo esperado lineal. [13]
El algoritmo de descomposición de Seidel [10] y el método de triangulación de Chazelle se analizan en detalle en Li y Klette (2011). [14]
La complejidad temporal de la triangulación de un polígono de n vértices con agujeros tiene un límite inferior Ω( n log n ) , en modelos de cálculo de árboles algebraicos. [1] Es posible calcular el número de triangulaciones distintas de un polígono simple en tiempo polinomial utilizando programación dinámica y (basándose en este algoritmo de conteo) generar triangulaciones uniformemente aleatorias en tiempo polinomial. [15] Sin embargo, contar las triangulaciones de un polígono con agujeros es #P-completo , por lo que es poco probable que se pueda hacer en tiempo polinomial. [16]
{{citation}}: CS1 maint: multiple names: authors list (link)