Triangulación en abanico

En Geometría computacional, la Triangulación en abanico (en inglés, Fan triangulation) es un método sencillo para calcular una triangulación de un polígono que consiste en elegir un vértice del polígono y trazar todas las diagonales con origen en ese vértice. No todos los polígonos pueden ser triangulados por este método, por lo que generalmente sólo es empleado en polígonos convexos.^[1]​

Triangulación en abanico de un polígono convexo, empleando las diagonales de un vértice.

Triangulación en abanico de un polígono cóncavo con un único vértice entrante.

Propiedades

Además de las propiedades de toda triangulación, las triangulaciones en abanico tienen las siguientes propiedades:

• No todos los polígonos admiten una triangulación en abanico, aunque es notable que los polígonos convexos siempre la admiten.
• Los polígonos con un único vértice cóncavo también la admiten, siempre que el único vértice entrante sea elegido como origen de las diagonales.
• Para saber si un polígono genérico admite una triangulación en abanico, es necesario resolver el Problema de la galería de arte y verificar que existe al menos un vértice que proporcione visibilidad a todo el polígono.
• La triangulación de un polígono con ${\displaystyle n}$  vértices usa ${\displaystyle n-3}$  diagonales, y genera ${\displaystyle n-2}$  triángulos.^[2]​
• La generación de la lista de triángulos es trivial si se dispone de la lista ordenada de los vértices del polígono, y puede calcularse en tiempo lineal. Esta propiedad hace que no sea necesario almacenar de forma explícita la lista de triángulos, por lo que varias librerías gráficas implementan primitivas para representar polígonos basados en esta triangulación. En este sentido, OpenGL introdujo la primitiva GL_TRIANGLE_FAN^[3]​ y Direct3D la primitiva D3DPT_TRIANGLEFAN (aunque se declaró obsoleta a partir de Direct3D 10).^[4]​ Estas primitivas son especialmente aptas para pintar elipses y círculos.
• Aunque esta triangulación es apta para resolver algunos problemas, como rasterización de polígonos o detección de colisiones, puede no serlo para otras debido a que el vértice origen acumula una valencia (número de vecinos) muy alta y los ángulos internos de la triangulación se distribuyen de forma poco equitativa.

Pseudoalgoritmo

Para generar la lista de triángulos de un polígono de ${\displaystyle N}$  vértices, suponiendo que el origen sea el vértice 0, se puede usar el pseudo-algoritmo:

Algoritmo triangulación en abanico para N vértices

Crear lista de triángulos vacía Para i en el rango [1 .. N-2] Añadir el triángulo de vértices (0, i, i+1)

Referencias y enlaces externos

1. Loera, Jesús A.; Rambau, Joerg; Santos, Francisco (2010). Triangulations: Structures and Algorithms. (en inglés). Springer Science & Business Media. pp. 103. ISBN 9783642129711. Consultado el 21 de febrero de 2017. (requiere registro). 
2. O'Rourke, Joseph. Computational Geometry in C (2 edición). Cambridge University Press. ISBN 9780521649766. 
3. Segal, Mark (24 de octubre de 2016). «The OpenGL Graphics System: A Specification». Consultado el 2 de marzo de 2017. 
4. «Deprecated Features (Direct3D 10)». Programming Guide for Direct3D 10. Consultado el 2 de marzo de 2017. 

•   Datos: Q28860822