Conclusión

Para que nuestra aplicación basada en OpenGL funcione de una forma correcta, robusta, tolerante y eficiente tenemos que tratar listas de puntos que supuestamente definen polígonos tridimensionales de la siguiente manera:

1. Eliminamos puntos múltiples consecutivos de la lista.
2. Calculamos las tres proyecciones en los planos del sistema de coordenadas.
3. Calculamos las áreas ponderadas de los tres polígonos.
4. Construímos un vector normal. Si no es posible rechazamos el polígono.
5. Calculamos el centro de los puntos.
6. Proyectamos los puntos al plano definido por el centro y el vector normal y
   1. aceptamos el polígono ``corregido'' o
   2. rechazamos el polígono si la distancia de algún punto a este plano es demasiado grande.
7. Proyectamos el polígono (ahora es seguro que es plano) al plano del sistema de coordenadas dado por la componente dominante del vector normal.
8. Comprobamos si el polígono es simple y convexo. Si no es asi:
   1. subdividimos el polígono en partes simples y convexos o
   2. rechazamos el polígono.

Salvo la última, todas las operaciones se pueden realizar en un tiempo de ejecución lineal en el número de esquinas del polígono.

Para l@s interesad@s: se ha desarrollado también un algoritmo que realiza la subdivisión de un polígono simple pero no-convexo en triángulos que se ejecuta en tiempo lineal en el número de esquinas del polígono. Los polígonos no-simples siempre necesitan más tiempo de cálculo, porque pueden tener muchas regiones que haya que tratar.

Además: las operaciones no salen del espacio de los números racionales, que es una propiedad muy importante en el ámbito de la geometría algorítmica, ya dijimos antes: si se trabaja con los flotantes de los procesadores, muchas veces la tarea se convierte en una verdadera aventura, o mejor dicho, una verdadera pesadilla si la meta es hacer algo bién hecho.

Antes de inventar la rueda por quinta vez, usamos la librería Leda que nos proporciona las estructuras de datos básicos.