Crear grafo conexo con CANVAS y EaselJS

Una de las mejoras con la aparición de HTML5 es la inclusión de Canvas, una nueva etiqueta que permite incorporar de forma nativa el renderizado 2d y 3d dentro de paginas html de forma nativa.

Para no extender mucho este post, dejo en el siguiente enlace a la documentación de la W3C School. En este articulo, además para simplificar mucho el proceso de generar un grafo conexo, emplearemos una librería para el uso de Canvas llamada EaselJS.

El caso de uso de este ejemplo se basa en crear un nodo donde el usuario realiza un click. A medida, que el usuario realiza más clicks sobre la pantalla se incorporan nuevos nodos y sus respectivas aristas conexas entre todos lo nodos, evitando generar múltiples conexiones entre nodos ya conectados.

Primero debemos descargarnos la librería del sitio oficial de EaselJS : Librería , el siguiente paso creamos un fichero html o un proyecto html en nuestro editor favorito. Procedemos a incluir la librería como indico en el siguiente ejemplo.

<!DOCTYPE html>
<html>
    <head>
        <script src="lib/easeljs-0.8.2.min.js"></script>
    </head>
    <body >
        
    </body>
</html>

A continuación, agregamos la etiqueta “canvas” que será el lienzo donde renderizamos las aristas y nodos correspondientes de cada click del usuario. Debemos indicar un identificador único que  permitirá a la librería EaselJS acceder al lienzo,”grafo”. Por último, dentro de la etiqueta body llamamos a la función “init()” en el método onload que se encargara de inicializar cada una de las funciones que necesitaremos.

<!DOCTYPE html>
<html>
    <head>
        <script src="lib/easeljs-0.8.2.min.js"></script>
    </head>
    <body onload="init();">
        <canvas id="grafo" width="600" height="600" >
            alternate content
        </canvas>
    </body>
</html>

Ahora estableceremos algunos estilos css básicos para mejorar la visibilidad del contenedor.

html,body{
         width: 100%;
         padding: 0;
         margin: 0;
}

canvas{
      margin: 0 auto;
      vertical-align: middle;
      border: 1px solid red;
      padding-left: 0;
      padding-right: 0;
      margin-left: auto;
      margin-right: auto;
      display: block;
}

Quedando el fichero html de la siguiente forma:

<!DOCTYPE html>
<html>
    <head>
        <script src="lib/easeljs-0.8.2.min.js"></script>
        <style>
            html,body{
                width: 100%;
                padding: 0;
                margin: 0;
            }
            canvas{
                margin: 0 auto;
                vertical-align: middle;
                border: 1px solid red;
                padding-left: 0;
                padding-right: 0;
                margin-left: auto;
                margin-right: auto;
                display: block;
            }

        </style>
    </head>
    <body onload="init();">
        <canvas id="grafo" width="600" height="600" >
            alternate content
        </canvas>
    </body>
</html>

Una vez definido el fichero base, vamos a comenzar a programar las diferentes funciones. Para ello debemos entender una serie de fundamentes de canvas y de la librería EaselJS. Debemos pensar en canvas como en un lienzo que mediante la librería EaselJS iremos llenando de figuras y eventos. Por lo que el primer paso es conectar el lienzo con la librería.

var stage = new createjs.Stage('grafo');

En la variable/objeto “stage” podremos realizar diferentes algoritmos y llamadas a métodos que permitirán el renderizado de los objetos. Como vamos necesitar la interacción del usuario debemos indicar como primer paso que el “stage” declarado tiene habilitados los eventos.

var stage = new createjs.Stage('grafo');
stage.enableDOMEvents(true);

Ya podemos detectar aquellos eventos que haga el usuario sobre el lienzo, en nuestro caso nos interesa capturar el evento click realizado sobre el “stage”, para ello debemos activar un listener que será el encargado de lanzar el código que creamos conveniente. De momento lo dejaremos vació.

stage.addEventListener("stagemousedown", function (evt) {
    
});

Para dibujar un grafo conexo necesitamos nodos y aristas, representados por círculos y lineas pues vamos a comenzar por los nodos. Para crear un nodo emplearemos la figura del circulo en cuyo centro aparecerá el número de nodo y su posición en el eje de coordenadas.

Para facilitar todo el código he decidido usar objectos en javascript, estos pueden ser definidos como funciones:

function Nodo(id, lat, long) {
    this.id = id;
    this.lat = lat;
    this.long = long;
}

Una vez definido nuestro objeto nodo, con los atributos id, lat y long. Pasamos a definir la función que renderiza el nodo dentro del lienzo. EaselJS permite generar de forma sencilla todo tipo de gráficos, para comenzar necesitamos un contenedor que guarde el gráfico y posteriormente ir agregando los elemento que conforman la figura.

Como siguiente paso debemos definir la función que se iniciará con la carga de la página html.

function init() {

}

Para gestionar de forma más sencilla cada uno de los nodos, vamos a usar como estructura de almacenamiento un vector de objectos de tipo nodo.

function init() {
                var nodos = [];
                var i = 0;
                var x = 0;
                var y = 0;

                function Nodo(id, lat, long) {
                    this.id = id;
                    this.lat = lat;
                    this.long = long;
                }
}

Ahora pasamos a definir la función que se encargara de dibujar un nodo dentro del lienzo, esta función será llamada desde el evento click sobre el lienzo.

function createNode(nodo, stage) {
                    var circle = new createjs.Container();
                    circle.mouseChildren = false;
                    circle.name = nodo.id + 1;
                    circle.x = nodo.lat;
                    circle.y = nodo.long;

                    var color = '#' + Math.floor(Math.random() * 16777215).toString(16);

                    var shape = new createjs.Shape();
                    shape.graphics.beginFill(color).drawCircle(0, 0, 30);

                    var text = new createjs.Text("#" + circle.name + " " + circle.x + "," + circle.y, "Helvetica", "#fff");
                    text.textAlign = "center";
                    text.textBaseline = "middle";

                    circle.addChild(shape, text);

                    stage.addChild(circle);


                }

La función recibe un nodo y el lienzo,  en la linea 2 declaramos un variable de tipo contenedor con el nombre circle, le anulamos los eventos de ratón y le ponemos como nombre el id del nodo con un autoincremento, le asignamos la posición en el eje de coordenadas del lienzo del nodo pasado como parámetro.  En la linea 8 solo generamos un color aleatorio.

var color = '#' + Math.floor(Math.random() * 16777215).toString(16);

Hasta este momento solo tenemos una entidad ficticia “contenedor”, tenemos que pintar la forma que deseamos, empleamos para ello la función “shape”, donde le asignamos el color generado y el tamaño, todo esto lo hacemos en la linea 11.

var shape = new createjs.Shape();
shape.graphics.beginFill(color).drawCircle(0, 0, 30);

El siguiente paso es decorar esta figura con los datos deseados en este caso el nombre del nodo, su posición el eje de coordenadas.

var text = new createjs.Text("#" + circle.name + " " + circle.x + "," + circle.y, "Helvetica", "#fff");
text.textAlign = "center";
text.textBaseline = "middle";

Por último, agregamos la figura al contenedor y el contenedor al lienzo.

circle.addChild(shape, text);
stage.addChild(circle);

Con esto resolvemos una parte del problema ahora tenemos que pintar una linea de cada nodo a todos los nodos,  donde reflejaremos la distancia euclidea.

 function createLine(ox, oy, dx, dy, stage) {

}

La función recibe los ejes de coordenada del punto de origen , el eje de coordenadas del punto de destino y el lienzo.

function createLine(ox, oy, dx, dy, stage) {
                    var line = new createjs.Shape();
                    line.graphics.setStrokeStyle(1).beginStroke("#000000");
                    line.graphics.moveTo(ox, oy);
                    line.graphics.lineTo(dx, dy);
                    line.graphics.endStroke();

                    var txtX = (ox + dx) / 2;
                    var txtY = (oy + dy) / 2;
                    var euclidean = (Math.sqrt(Math.pow((ox - dx),2) + Math.pow((oy - dy),2)));
                    var text = new createjs.Text(euclidean.toFixed(2) + "", "8pt Arial").set({x: txtX + 15, y: txtY});
                    text.textBaseline = "alphabetic";
                    stage.addChild(text, line);
               
}

Otra forma de agregar elementos es crearlos y agregarlos directamente al lienzo, esto es conveniente si el objecto a insertar no va tener propiedades o eventos del DOM de javascript esto simplifica la codificación y el coste computacional al no agregar un elemento de tipo contenedor. En este caso necesitamos pintar tantas lineas como nodos necesitemos interrelacionar, por lo que es interesante no generarle un contenedor a cada linea.

El primer paso, generamos la forma de la linea con la función shape. Asignamos el ancho de la linea así como su origen y destino.

var line = new createjs.Shape();
line.graphics.setStrokeStyle(1).beginStroke("#000000");
line.graphics.moveTo(ox, oy);
line.graphics.lineTo(dx, dy);
line.graphics.endStroke();

Para poder pintar la distancia entre los nodos justo en el medio de la linea necesitamos calcular la mediatriz del segmento.  Que es el resultado de obtener las coordenadas resultantes de dividir la  latitudes de origen y destino entre 2, la longitudes de origen y destino entre 2.

var txtX = (ox + dx) / 2;
var txtY = (oy + dy) / 2;

Ahora obtenemos la distancia euclidea entre los dos nodos con la formula y la asignamos a un elemento de tipo texto. Por último, agregamos todo el conjunto al lienzo.

var euclidean = (Math.sqrt(Math.pow((ox - dx),2) + Math.pow((oy - dy),2)));
var text = new createjs.Text(euclidean.toFixed(2) + "", "8pt Arial").set({x: txtX + 15, y: txtY});
text.textBaseline = "alphabetic";
stage.addChild(text, line);

Con esto hemos definido las dos funciones básicas para renderizar un circulo y una linea dentro del lienzo. El siguiente paso es aunar estas funciones para que cuando el usuario realice un click dentro del lienzo pinte un nodo y genere todos los vectores hacia el resto de nodos.

function createGrafo(nodos, stage) {

                    stage.clear();
                    stage.removeAllChildren();
                    stage.update();
                    for (var f = 0; f < nodos.length; f++) {

                        if (nodos.length > 0) {
                            for (var j = f; j < nodos.length; j++) {
                                if (j !== f) {
                                    createLine(nodos[f].lat, nodos[f].long, nodos[j].lat, nodos[j].long, stage);
                                }

                            }
                        }
                        createNode(nodos[f], stage);

                    }
}

Esta función recibe el vector de nodos y el liezo, será llamada cada vez que se produzca un evento click en el lienzo, capturando el eje de coordenadas donde se produjo el click para renderizar en ese punto un nodo y pintar los respectivos vectores al resto de nodos en caso de existir.

Primero eliminamos todos los elementos previos del lienzo para poder renderizar los elementos.

stage.clear();
stage.removeAllChildren();
stage.update();

A continuación,  tenemos que recorrer los posibles nodos y generar los vectores y aristas, 😉 (truco si generas primero los vectores al generar las aristas estas quedarán por encima).

for (var f = 0; f < nodos.length; f++) {

                        if (nodos.length > 0) {
                            for (var j = f; j < nodos.length; j++) {
                                if (j !== f) {
                                    createLine(nodos[f].lat, nodos[f].long, nodos[j].lat, nodos[j].long, stage);
                                }

                            }
                        }
                        createNode(nodos[f], stage);

                    }

A medida que creamos los vectores la ultima arista ya estará casi o completamente interconectada por lo que no es necesario recorrer toda la matriz de interrelación, es suficiente con recorrer la diagonal superior.

N/N A B C D
A *
B * *
C * * *
D * * * *

 Si quisiéramos un grafo doblemente enlazado solo deberíamos recorrerla matriz de forma completa. Llegados a este punto solo nos queda implementar el evento que invocará a nuestra función.

var stage = new createjs.Stage('grafo');
               stage.enableDOMEvents(true);
               stage.addEventListener("stagemousedown", function (evt) {
                   var n = new Nodo(i, evt.stageX, evt.stageY);
                   nodos[i++] = n;
                   stage.removeAllChildren();
                   createGrafo(nodos, stage);
                   stage.update();
               });

El primer paso es crear nuestro lienzo referenciando al identificador de la etiqueta canvas del cuerpo de nuestro html.

var stage = new createjs.Stage('grafo');

Activamos los eventos de DOM.

stage.enableDOMEvents(true);

Y definimos que queremos que ocurra cuando se realice un click de ratón sobre el lienzo.

stage.addEventListener("stagemousedown", function (evt) {
                    var n = new Nodo(i, evt.stageX, evt.stageY);
                    nodos[i++] = n;
                    stage.removeAllChildren();
                    createGrafo(nodos, stage);
                    stage.update();
 });

La “stagemousedown”  indica que capture la información del click del usuario, ya dentro de la función,(esta forma de programar le sonara a los avezados de Jquery),  creamos una variable del tipo objeto “nodo”, donde le pasamos por argumento el numero de nodo,  la posicion x y la posición y de donde se produjo el evento click y agregamos el nodo al vector de nodos.

var n = new Nodo(i, evt.stageX, evt.stageY);
nodos[i++] = n;

Limpiamos el lienzo de contenido.

stage.removeAllChildren();

Llamamos a nuestra función de renderizado de grafos.

createGrafo(nodos, stage);
stage.update();

Con esto hemos finalizado de codificar todo nuestro código. El código es muy simple y es solo una demostración de la potencia de esta librería a la hora de codificar con canvas.

Tenéis todo el código disponible en GitHub, donde podéis aportar y recomendar lo que creáis oportuno.

https://github.com/aruetre/grafoCanvas

 

 

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *