De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Para una cobertura más amplia de este tema, consulte Triangulación (geometría) .
Triangulación de polígono

En la geometría computacional , la triangulación de polígonos es la descomposición de un área poligonal ( polígono sencillo ) P en un conjunto de triángulos , [1] es decir, la búsqueda de un conjunto de triángulos con interiores pairwise que no se cruzan, cuya unión es P .

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

Triangulación de polígonos sin vértices adicionales [ editar ]

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

Casos especiales [ editar ]

Las 42 triangulaciones posibles para un heptágono convexo (polígono convexo de 7 lados). Este número viene dado por el quinto número catalán .

Es trivial triangular cualquier polígono convexo en tiempo lineal en una triangulación en abanico , agregando diagonales desde un vértice a todos los demás vértices.

El número total de formas de triangular un n -gon convexo con diagonales que no se cruzan es el ( n −2) nd número catalán , 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]

Método de recorte de orejas [ editar ]

Una oreja poligonal

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] Entonces, el algoritmo consiste en encontrar una oreja de este tipo, 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 algunos 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 las orejas . [6]

Triangulación de polígonos monótonos [ editar ]

Romper un polígono en polígonos monótonos

Un polígono simple es monótono con respecto a una línea L , si alguna 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 monótono y . Un polígono monótono con n vértices se puede triangular en O ( n ) tiempo. Suponiendo que un polígono dado es monótono en y, el algoritmo codicioso comienza caminando en 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.

Triangular un polígono no monótono [ editar ]

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 huecos. Generalmente, este algoritmo puede triangular una subdivisión plana con n vértices en el tiempo O ( n log n ) usando el espacio O ( n ) . [1]

Gráfico dual de una triangulación [ editar ]

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 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 solo si comparten una diagonal. Es fácil observar que G ( T P ) es un árbol con grado máximo 3.

Complejidad computacional [ editar ]

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 se puede triangular 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 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 huecos tiene un límite inferior Ω ( n log n ) , en modelos de árbol de cálculo algebraico . [1] Es posible calcular el número de triangulaciones distintas de un polígono simple en tiempo polinomial usando programación dinámica , y (basado 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 realizar en tiempo polinomial. [dieciséis]

Objetos y problemas relacionados [ editar ]

  • Ambos problemas de triangulación son un caso especial de triangulación (geometría) y un caso especial de partición poligonal .
  • 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 punto-set es una triangulación polígono de la envolvente 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 Associahedron es un politopo cuyos vértices corresponden a las triangulaciones de un polígono convexo.
  • Revestimiento de triángulo poligonal , 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.

Ver también [ editar ]

  • Regla distinta de cero
  • Número catalán
  • Gráfico plano
  • Voltear gráfico

Referencias [ editar ]

  1. ^ a b c d e Mark de Berg , Marc van Kreveld , Mark Overmars y Otfried Schwarzkopf (2000), "3: Triangulación de polígonos", Geometría computacional (2ª ed.), Springer-Verlag , págs. 45-61, ISBN 3-540-65620-0CS1 maint: multiple names: authors list (link)
  2. ^ Pickover, Clifford A. (2009), El libro de matemáticas , Sterling, p. 184
  3. ^ Fournier, Alain ; Montuno, Delfin Y. (1984), "Triangulación de polígonos simples y problemas equivalentes", ACM Transactions on Graphics , 3 (2): 153–174, doi : 10.1145 / 357337.357341 , ISSN 0730-0301 , S2CID 33344266  
  4. ^ Toussaint, Godfried T. (1984), "Un nuevo algoritmo lineal para triangular polígonos monótonos", Cartas de reconocimiento de patrones , 2 : 155-158, doi : 10.1016 / 0167-8655 (84) 90039-4
  5. ^ Meisters, Gary Hosler (1975), "Los polígonos tienen orejas" , American Mathematical Monthly , 82 : 648–651, doi : 10.2307 / 2319703
  6. ^ ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried T. (1993), "Cortar una oreja con podar y buscar", Pattern Recognition Letters , 14 (9): 719–722, doi : 10.1016 / 0167-8655 (93) 90141-y
  7. ^ Tarjan, Robert E .; Van Wyk, Christopher J. (1988), "Un algoritmo de tiempo O ( n log log n ) para triangular un polígono simple", SIAM Journal on Computing , 17 (1): 143-178, CiteSeerX 10.1.1.186.5949 , doi : 10.1137 / 0217010 , MR 0925194  
  8. ^ Kirkpatrick, David G .; Klawe, Maria M .; Tarjan, Robert E. (1992), "Triangulación de polígonos en el tiempo O ( n log log n ) con estructuras de datos simples", Geometría discreta y computacional , 7 (4): 329–346, doi : 10.1007 / BF02187846 , MR 1148949 
  9. ^ Clarkson, Kenneth L .; Tarjan, Robert ; van Wyk, Christopher J. (1989), "Un algoritmo rápido de Las Vegas para triangular un polígono simple", Geometría discreta y computacional , 4 (5): 423–432, doi : 10.1007 / BF02187741
  10. ^ Seidel, Raimund (1991), "Un algoritmo aleatorio incremental simple y rápido para calcular descomposiciones trapezoidales y para triangular polígonos", Geometría computacional , 1 : 51-64, doi : 10.1016 / 0925-7721 (91) 90012-4
  11. ^ Clarkson, Kenneth L .; Cole, Richard; Tarjan, Robert E. (1992), "Algoritmos paralelos aleatorios para diagramas trapezoidales", International Journal of Computational Geometry & Applications , 2 (2): 117-133, doi : 10.1142 / S0218195992000081 , MR 1168952 
  12. ^ Chazelle, Bernard (1991), "Triangulación de un polígono simple en tiempo lineal", Geometría discreta y computacional , 6 (3): 485–524, doi : 10.1007 / BF02574703 , ISSN 0179-5376 
  13. ^ Amato, Nancy M .; Goodrich, Michael T .; Ramos, Edgar A. (2001), "Un algoritmo aleatorio para triangular un polígono simple en tiempo lineal" , Geometría discreta y computacional , 26 (2): 245-265, doi : 10.1007 / s00454-001-0027-x , ISSN 0179-5376 
  14. ^ Li, Fajie; Klette, Reinhard (2011), caminos más cortos euclidianos , Springer , doi : 10.1007 / 978-1-4471-2256-2 , ISBN 978-1-4471-2255-5
  15. ^ Epstein, Peter; Sack, Jörg-Rüdiger (1994), "Generación de triangulaciones al azar", ACM Transactions on Modelling and Computer Simulation , 4 (3): 267–278, doi : 10.1145 / 189443.189446 , S2CID 14039662 
  16. ^ Eppstein, David (2019), "Contar triangulaciones de polígonos es difícil", Proc. 35a Int. Symp. Geometría computacional , Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl, págs. 33: 1–33: 17, arXiv : 1903.04737 , doi : 10.4230 / LIPIcs.SoCG.2019.33 , S2CID 75136891 

Enlaces externos [ editar ]

  • Demostración como Flash swf , algoritmo A Sweep Line.
  • Explicación de Song Ho del teselador OpenGL GLU