Diagramas de Voronoi
Hace tiempo me entró el interés por los Diagramas de Voronoi.
Bases
Estos diagramas te permiten encontrar el vecino más cercano a un punto, para cada punto principal en el diagrama. Con punto principal me refiero a los puntos sobre los cuales se creó el diagrama, el cual también forma puntos propios.
Este diagrama es utilizado en varias áreas, incluyendo el modelado geográfico, las telecomunicaciones, la informática gráfica, entre otras muchas.
Sin contar todos los lugares en donde se usa este tipo de diagramas, estos diagramas son muy bonitos :-)
Acerca del algoritmo y las implementaciones
Para crear estos diagramas, hay varios algoritmos, pero el más eficiente (comprobado) es el algoritmo de Fortune, que se describe muy bien en el libro “Computational Geometry: Algorithms and Applications”. Este algoritmo es descrito en una sola hoja, pasando por muchas de explicación y de comprobación de propiedades, sin embargo, su implementación no es nada fácil ni rápida.
Hay varias implementaciones del algoritmo de Fortune para crear los diagramas de voroni. Estas implementaciones son en C, como la del autor, en C++, como las de algunas librerías para computación gráfica, en Java, etc.
Como nota adicional, hay un mundo de applets que muestran como crear los diagramas de voronoi, pero para ser sincero, no encontré una sola descripción decente de como implementar el algoritmo de Fortune.
Dificultades del algoritmo
Lo que hace difícil la implementación de este algoritmo es que utiliza algunas estructuras de datos especializadas, impidiendo el uso de algunas estructuras genéricas que ya traen varios lenguajes. También utiliza muchos cálculos geométricos que uno tiene que averiguar por su cuenta, por ejemplo, la intersección entre 2 parábolas.
La verdad, la principal batalla para mí fue entender el algoritmo y los requerimientos que este tenía. Aunque no lo he implementado por falta de tiempo, me gustaría terminar la implementación que estaba en curso pero usando otras herramientas para hacerlo más accesible y rápido.
Requerimientos del algoritmo de Fortune
El algoritmo utiliza una técnica llamada sweep line, que requiere un árbol de búsqueda balanceado ( AvlTree ) y especializado para este algoritmo.
En general, el libro mencionado describe muy bien el algoritmo y sus bases, pero para entender mejor su funcionamiento tuve que bajar varias diapositivas, las cuales incluyo abajo en los links.
Otra estructura que se usa es la cola priorizada( Heap ), que debe permitir eliminar un elemento en cualquier parte de la cola. Esta heap se usa para manejar los eventos producidos por el algoritmo.
Algunas operaciones geométricas que se requieren son:
- Punto medio de un segmento
- Intersección entre 2 segmentos
- Circuncentro de 3 puntos
- Manejo de parábolas
Varios algoritmos geométricos estan descritos en el libro Computational Geometry in C, 2ed , de Joseph O’Rourke.
Partes desarrolladas
Actualmente llevo pocas partes desarrolladas de este algoritmo. Mi intención era hacer una implementación del algoritmo de Fortune en Javascript, usando el HtmlCanvas(solo Firefox, Safari y Opera) para mostrar el diagrama.
La verdad es que quiero hacer muchas cosas pero no creo que tenga tiempo para todas así que lo que salga es bueno :-)
A este momento tengo hechas algunas partes aisladas del algoritmo, ya que como dije anteriormente, me pricipal problema fue entender el algoritmo y saber que hacer para implementarlo. Si después actualizo la implementación, pues haré otro Post o actualizaré este.
Dividí las partes en 3 archivos(por el momento):
- Estructuras geométricas . Aquí se manejan los clases para manejar puntos y segmentos, en las cuales se implementan varios algoritmos geométricos como la intersección entre 2 segmentos y el punto medio de un segmento. También está implementada la mediatriz de un segmento, como la que se implementó el cálculo del circuncentro, el cual todavía no ha sido metído en la clase VSegment.
- Manejo de pintado . Aquí se maneja lo relativo al pintado en el Html Canvas. Se maneja el pintado de líneas, círculos y puntos. Esta archivo depende del core geométrico.
- Estructuras de datos . Aquí estarían implementados el árbol de búsqueda para la sweep line y la heap pero por ahora solo está la heap. Esta heap está implementada usando un arreglo como base, como viene descrito en el artículo enlazado.
En los siguientes links muestro los archivos de prueba de esas partes:
Links de interés:
Wiki dedicada a los Diagramas de Voronoi
Libro Computational Geometry: Algorithms and Applications
Capítulo del libro anterior dedicado a los Diagramas de Voronoi
