Reciclando prácticas de la carrera

Triangulación de Delaunay

Organizando los cientos de CD que debía tener guardados (y que ya he organizado) he encontrado este applet Java que genera la triangulación de Delaunay y dibuja el diagrama de Voronoi a partir de una serie de puntos en un plano bidimensional. Es una de las prácticas que hice en la carrera, hace ya unos cuantos años, para la asignatura Razonamiento Geométrico del Dpto. de Ciencias de la Computación e Inteligencia Articial. He pensado que, como en el cajón de los CD no tiene utilidad alguna y me parece un programa interesante, sería buena idea dejarlo publicado por aquí. Podéis encontrar en Internet cientos de applets similares y mucho más sofisticados, pero este es el que programé yo.

Diagrama de Voronoi

Y ya que estoy, de forma muy breve explico que una red de triángulos es una triangulación de Delaunay si todas las circunferencias circunscritas de todos los triángulos de la red son vacías, es decir, cada una de las circunferencias no contiene otros vértices aparte de los tres que la definen. El diagrama de Voronoi se obtiene conectando los centros de las circunferencias circunscritas.

El applet, que utiliza la librería JavaRG, permite construir la triangulación de forma dinámica, esto es, se va construyendo la triangulación de Delaunay a medida que se insertan puntos en el plano. También se pueden generar puntos aleatoriamente y obtener la triangulación para ese conjunto de puntos. Parece que con el tiempo han ido sustituyendo en la asignatura la librería JavaRG por el paquete java.awt.geom.

La asignatura de Razonamiento Geométrico (de la que tengo muy buen recuerdo) se llama ahora Computación Geométrica, desde la entrada en vigor del plan 2001 en Ingeniería Informática en la Universidad de Alicante y la sigue impartiendo el profesor Domingo Gallardo (que fue además tutor de mi proyecto de fin de carrera).

Si alguien siente curiosidad por la computación geométrica, un buen libro es Computational Geometry: Algorithms and Applications de Mark de Berg et al.

A medida que vaya encontrando material de la carrera que merezca la pena compartir, intentaré ir publicándolo -con alguna licencia libre si es posible- en una wiki precisamente para este tipo de contenidos que uno no sabe muy bien dónde meter. ¡Qué buena forma de organizar y hacer limpieza…!

2 Comments

  1. Hola:

    Soy estudiante de computacion y me dejaron como practica final las triangulaciones de Delaunay, ojala pudieras pproporcionarme tu codigo para irme dando una idea, muchas gracias

    1. Miriam: te recomiendo que eches un vistazo a la web de Computación Geométrica del Dpto. de Ciencias de la Computación de la Universidad de Alicante: http://www.dccia.ua.es/dccia/inf/asignaturas/RG.
      Allí encontrarás las presentaciones utilizadas en clase y probablemente algunos recursos y bibliografía (el libro que comento en el post te será de gran ayuda). El código fuente no sé si será muy útil (http://code.ebenimeli.org). Aunque ya sabes que en estos casos de prácticas en la carrera siempre es mejor programar desde cero 😉

Leave a Comment