Después de un mes con el proyecto dejado de lado, he aprovechado las navidades para trabajar en él un poco, y la verdad es que los resultados son satisfactorios, por ahora.
Los cambios son sencillos, he programado un algoritmo basado en fuerzas para imprimir el árbol, la cámara se mueve si se mantiene pulsado el ratón, y también hay programado un algoritmo de coloreado inventado por mí. Además, se ven los nombres de los clados que representan los nodos cuando se coloca el ratón encima.
He aquí un video de ejemplo:
Mas técnicamente, los dos algoritmos principales son los siguientes:
Algoritmo basado en resortes
Es el algoritmo usado para calcular la posición de los nodos del árbol. Es un algoritmo de la familia de los algoritmos basados en fuerzas, conocido popularmente como Spring Embedder (resortes embebidos). Este algoritmo consiste en lo siguiente: cada arista es, en realidad, un resorte, —es decir, un muelle— que tiene una longitud dada. Cada pareja de nodos no conectados, se unirán con una arista ficticia que también modelará a un resorte. Las aristas verdaderas serán resortes de atracción, y las aristas ficticias serán resortes de repulsión.
Las posiciones de los nodos se inicializan aleatoriamente, y se unirán con muelles de la forma indicada. Cada resorte intentará volver a su posición inicial, generándose un sistema de fuerzas que buscará una situación de equilibrio. Es como si forzaramos una serie de puntos unidos con muelles, algunos estirados y otros comprimidos, y luego tiraramos el conjunto al aire. El gráfico anterior ilustra bastante bien su comportamiento, dando finalmente una visualización elegante del árbol.
Algoritmo basado en intervalos de colores
Este algoritmo es invención mía, y funciona de la siguiente forma: a cada nodo se le asigna un intervalo de colores, y se colorea con el centro de dicho intervalo. Dicho intervalo se parte en tantos subintervalos como hijos tenga el nodo, y, análogamente, se colorea con su centro. Se procede recursivamente para todo el árbol, siendo el intervalo de la raíz del árbol el propio cubo RGB (y por tanto, la raíz del árbol será de color gris, pues es el centro del cubo).
La forma de partir cada intervalo es el siguiente. Partiendo del cubo RGB asignado a la raíz, primero se elige para particionar la dimensión R —es decir, la del color rojo—. Así, si la raíz tiene n hijos, el cubo se partirá en n rectángulos 3D, donde el ancho en la dimensión R de cada rectángulo 3D será el ancho del nodo raíz dividido entre 'n'. Para el siguiente nivel, cada cubo se partirá en la dimensión G, luego en la B, luego nuevamente en la R, y así sucesivamente.
La idea de éste algoritmo es que cada nodo sea dueño de una región, del cubo RGB de la que ninguno de sus hijos podrá escapar. Así, aunque en los primeros niveles haya saltos en la gama de colores —sobre todo si cada nodo tiene pocos hijos—, a medida que se incrementa la profundidad la gama de colores de nodos relacionados será mas homogénea, y el propio coloreado será un indicador gráfico de la cercanía entre nodos.
Aspectos por cambiar o mejorar
Hay todavía muchas cosas importantes por mejorar en la aplicación. El más importante por ahora es que la aplicación no cuenta con ninguna base de datos externa. El árbol está creado nodo a nodo en el fichero program.cpp, es decir, embebido en el propio código. Este es quizás el siguiente aspecto crucial de la aplicación, tener una base de datos externa, y crear la visualización del árbol leyendo los datos a partir de dicha base de datos. Seguramente usaré posgreeSQL.
Otros aspectos menores son referidos, por ejemplo, al peso de las aristas. Por ahora, cada arista tiene el mismo peso, que viene indicado en el propio algoritmo basado en resortes —en realidad, no existe aún ninguna clase arista que tenga un atributo peso, sencillamente es una pareja de nodos—. Habrá que asignar un peso a cada arista, usando algún criterio relacionado con el árbol filogenético —por ejemplo, proporcional al número de nietos que tenga un hijo—, y adaptar el algoritmo de resortes para que éste cambio no produzca efectos indeseables en la visualización.
Otro aspecto a cambiar es el posicionado del árbol. El árbol entero es movido según el sistema de fuerzas que provoquen los resortes, y habrá que cambiar el algoritmo para que, al menos la raíz, quede fija en un punto dado, porque a veces el árbol se mueve demasiado hacia un extremo y hay que mover la cámara para volver a centrarlo.
Hasta otra ...
