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 por pares que no se cruzan y cuya unión es P.
Las triangulaciones pueden verse como casos especiales de gráficos planos de líneas rectas . Cuando no hay agujeros ni puntos añadidos, las triangulaciones forman gráficos planos exteriores máximos .
Con el 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 en abanico , agregando diagonales de 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 -gon convexo mediante diagonales que no se cruzan es el ( n −2)nd número catalán , que es igual
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 con el algoritmo de Godfried Toussaint . [4]
Una forma de triangular un polígono simple se basa en el teorema de las dos orejas , ya 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 que son los bordes 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 aún 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 solo funciona en polígonos sin agujeros. Una implementación que mantiene 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 eficaz para cortar orejas . [6]
Un polígono simple es monótono con respecto a una recta L , si cualquier recta ortogonal a L corta al 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 codicioso 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 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 . Generalmente, este algoritmo puede triangular una subdivisión plana con n vértices en O ( n log n ) tiempo usando el espacio O( n ) . [1]
Una gráfica útil que a menudo se asocia con una triangulación de un polígono P es la gráfica dual . Dada una triangulación T P de P , se define el gráfico G ( T P ) como el gráfico cuyo conjunto de vértices son los triángulos de T P , siendo dos vértices (triángulos) adyacentes si y sólo 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 el tiempo O ( n log n ) 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 la 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 árbol de cálculo algebraico . [1] Es posible calcular el número de triangulaciones distintas de un polígono simple en tiempo polinómico usando programación dinámica y (basándose en este algoritmo de conteo) generar triangulaciones uniformemente aleatorias en tiempo polinómico. [15] Sin embargo, contar las triangulaciones de un polígono con agujeros es #P-completo , por lo que es poco probable que pueda realizarse en tiempo polinómico. [dieciséis]
{{citation}}: CS1 maint: multiple names: authors list (link)