Triangulación de polígonos

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.

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

${\displaystyle {\frac {n(n+1)...(2n-4)}{(n-2)!}}}$,

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 ² ) . 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 puede triangularse 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 usando 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]

• Ambos problemas de triangulación son un caso especial de triangulación (geometría) y un caso especial de partición de polígonos .
• La triangulación de peso mínimo es una triangulación en la que el objetivo es minimizar la longitud total del borde.
• Una triangulación de conjunto de puntos es una triangulación poligonal de la envoltura convexa de un conjunto de puntos. Una triangulación de Delaunay es otra forma de crear una triangulación basada en un conjunto de puntos.
• El asociaedro es un politopo cuyos vértices corresponden a las triangulaciones de un polígono convexo.
• Recubrimiento de triángulos poligonales , en el que los triángulos pueden superponerse.
• Mosaico por polígonos , donde el objetivo es cubrir todo el plano con polígonos de formas predefinidas.

• Regla de valores distintos de cero
• Número catalán
• Gráfico planar
• Gráfico invertido

• Demostración como Flash swf, algoritmo A Sweep Line.
• Explicación de Song Ho sobre el teselado GLU de OpenGL