Triangulación en abanico

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.

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: