Triangulación de polígonos

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En geometría computacional, triangulación poligonal es la partición de un área poligonal (poligo simple) $P$ en un conjunto de triángulos, es decir, encontrar un conjunto de triángulos con interiores pares sin intersección cuya unión es $P$ .

Las triangulaciones pueden verse como casos especiales de gráficos planos de línea recta. Cuando no hay agujeros ni puntos agregados, las triangulaciones forman gráficos planos externos máximos.

Triangulación de polígonos sin vértices extra

Con el tiempo, se han propuesto varios algoritmos para triangular un polígono.

Casos especiales

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-gón convexo mediante diagonales que no se cruzan es el (n−2)segundo número catalán, que es igual

{displaystyle {frac {n+1)... {n-4)}}}}}

una fórmula encontrada por Leonhard Euler.

Un polígono monótono se puede triangular en tiempo lineal con el algoritmo de A. Fournier y D.Y. Montuno, o el algoritmo de Godfried Toussaint.

Método de recorte de orejas

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 siendo los lados los bordes del polígono y el tercero completamente dentro de él. 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 repetirlo 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 $O(n 2)$ tiempo. 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.

Triangulación de polígonos monótonos

Romper un polígono en polígonos monotonos

Un polígono simple es monótono con respecto a una línea $L$ , si cualquier línea ortogonal a $L$ cruza 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 $O(n)$ tiempo. 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. Es fácil ver que el algoritmo se puede aplicar a cualquier polígono monótono.

Triangulación de un polígono no monótono

Si un polígono no es monótono, se puede dividir en subpolígonos monótonos en $O(n log n)$ tiempo usando 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 registre n)$ tiempo usando el espacio $O(n)$ .

Gráfica doble de una triangulación

(feminine)

Un gráfico útil que a menudo se asocia con 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 vértice conjunto 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.$

Complejidad computacional

Hasta 1988, si un polígono simple se puede triangular más rápido que $O(n log n)$ era una cuestión Problema abierto en geometría computacional. Entonces, Tarjan & Van Wyk (1988) descubrió un algoritmo de tiempo $O(n log n)$ para la triangulación, posteriormente simplificado por Kirkpatrick., Klawe & Tarjano (1992). Siguieron varios métodos mejorados con complejidad $O(n log* n)$ (en la práctica, indistinguible del tiempo lineal).

Bernard Chazelle demostró en 1991 que cualquier polígono simple puede triangularse en tiempo lineal, aunque el algoritmo propuesto es muy complejo. También se conoce un algoritmo aleatorio más simple con tiempo esperado lineal.

El algoritmo de descomposición de Seidel y el método de triangulación de Chazelle se analizan en detalle en Li & Klette (2011).

La complejidad temporal de la triangulación de un polígono de $n$ -vértice con agujeros tiene un $Ω(n log n)$ límite inferior, en modelos de cálculo de árbol de cálculo algebraico. 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. 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.

Objetos y problemas relacionados

Ambos problemas de triangulación son un caso especial de triangulación (geometría) y un caso especial de partición de polígono.
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 puntos es una triangulación de polígono del casco convexo de un conjunto de puntos. Una triangulación Delaunay es otra manera de crear una triangulación basada en un conjunto de puntos.
El associaedro es un politopo cuyos vértices corresponden a las triangulaciones de un polígono convexo.
Cubierta de triángulo poligonal, en la que los triángulos pueden superponerse.
Tiling by polygons, where the goal is to cover the entire plano with polygons of pre-specificified shapes.

Contenido relacionado

Más resultados...