¿Cómo triangular un polígono arbitrario?

Necesito triangular un polígono para renderizar en OpenGL ES en Android (no hay triangulación GLU disponible).

¿Existe un algoritmo ya conocido para la triangulación de polígonos? El polígono puede ser convexo o cóncavo (sin agujeros).

Hay varios algoritmos por ahí. Uno de los algoritmos más utilizados es el algoritmo de recorte del oído . Aquí hay una página con más detalles sobre este algoritmo de triangulación.

Hay algunos algoritmos e implementación de la triangulación de polígonos en estos libros:

• Geometría Computacional: Algoritmos y Aplicaciones. Capítulo 3: Triangulación de polígonos.
• Geometría computacional en C. Capítulo 1: Triangulación poligonal.