Triangulación de ventiladores

En geometría computacional , la triangulación en abanico es una forma sencilla de triangular un polígono eligiendo un vértice y trazando aristas hacia todos los demás vértices del polígono. No todos los polígonos pueden triangularse de esta manera, por lo que este método generalmente solo se utiliza para polígonos convexos . ^{[ 1 ]}

Además de las propiedades de todas las triangulaciones, las triangulaciones en abanico tienen las siguientes propiedades:

• Todos los polígonos convexos, pero no todos los polígonos, pueden ser triangulados en abanico.
• Los polígonos con un solo vértice cóncavo siempre se pueden triangular mediante un método de abanico, siempre que las diagonales se tracen desde el vértice cóncavo.
• Se puede saber si un polígono se puede triangular en abanico resolviendo el problema de la galería de arte , para determinar si hay al menos un vértice que sea visible desde cada punto del polígono.
• La triangulación de un polígono con${\displaystyle n}$vértices utiliza${\displaystyle n-3}$diagonales, y genera${\displaystyle n-2}$triángulos. ^{[ 2 ]}
• Generar la lista de triángulos es trivial si se dispone de una lista ordenada de vértices, y se puede calcular en tiempo lineal. Por lo tanto, no es necesario almacenar explícitamente la lista de triángulos y, en consecuencia, muchas bibliotecas gráficas implementan primitivas para representar polígonos basándose en esta triangulación. ^{[ 3 ]}
• Si bien esta triangulación es adecuada para resolver ciertos problemas, como la rasterización o la detección de colisiones , puede resultar inadecuada para otras tareas debido a que el vértice de origen acumula un elevado número de vecinos y los ángulos internos de la triangulación están distribuidos de forma desigual.

• Ventilador triangular