Fecha de lanzamiento: 1 Diciembre
Fecha de entrega: 19 Enero 2011
Puntuación: 25 puntos
Parte básica (15 puntos): Desarrollar un proyecto Eclipse con Processing que permita introducir un conjunto de puntos en una ventana y calcular su convex hull utilizando los siguientes algoritmos:
El programa debe también permitir generar un número determinardo de puntos aleatorios, calcular su convex hull y guardar el tiempo consumido para poder realizar un análisis del coste real de los algoritmos (igual que hacíamos con la intersección de segmentos).
Parte avanzada (10 puntos): Añadir los siguientes algoritmos:
Parte básica (15 puntos): Desarrollar un proyecto Eclipse con Processing que permita al usuario introducir un conjunto de puntos en una ventana y calcular su triangulación de Delaunay mediante el algoritmo incremental basado en la legalización de aristas. El programa debe permitir también generar un número determinardo de puntos aleatorios, calcular su triangulación de Delaunay y guardar el tiempo consumido para poder realizar un análisis del coste real del algoritmo (igual que hacíamos con la intersección de segmentos).
Para la parte básica no es necesario definir estructuras de datos que optimicen el funcionamiento del algoritmo. Por ejemplo, se puede implementar utilizando un ArrayList de triángulos y realizando búsquedas en la lista cada vez que se necesita modificar o eliminar alguno de ellos.
Parte avanzada (10 puntos): Mejorar el algoritmo anterior utilizando alguna estructura de datos que mantenga referencias entre los objetos geométricos (aristas y triáungulos) que intervienen en el cálculo de la triangulación. La operación de legalizar arista debe utilizar estas referencias para evitar las búsquedas secuenciales en la lista de triángulos y debe actualizar correctamente la estructura de datos.
Se deberá entregar un documento en el que se incluya:
Además, se entregará un fichero zip con el proyecto Eclipse comprimido (incluyendo los fuentes).