La representación tradicional de un grafo consiste en un conjunto de puntos que representan los nodos unidos por unas líneas que unen aquellos nodos relacionados. No obstante, cuando el número de nodos se empieza a hacer elevado (por encima de unos 20 nodos y 20-30 enlaces para algunos autores), los problemas de oclusión entre enlaces e incluso entre los propios nodos comienzan a prevalecer y hacen muy difícil la comprensión y la interacción con la representación.
Una representación alternativa que, pese a su relativo desconocimiento, resulta muy útil es la matricial.
Para nuestros efectos la representación matricial es una disposición en filas y columnas en las que cada fila y cada columna representa un nodo y en las intersecciones entre ellas se coloca un 0 o un 1 (o un cuadrado de color o su ausencia) para denotar que hay un enlace entre los nodos correspondientes.
Así pues lo que pintamos es una matriz booleana de conectividad, también llamada matriz de adyacencia. Fijémonos que ello nos permite visualizar enlaces uno a uno, uno a muchos y muchos a uno de manera muy sencilla.
Obviamente el paradigma matricial se puede extender más allá de la matriz de adyacencia asignando una variable visual como por ejemplo el color a cada celda en función del valor de una variable como por ejemplo el tráfico de un enlace web o el número de publicaciones de las que dos nodos son co-autores.
Representación matricial de un grafo: Cada dimensión se representa en un eje paralelo a los de las demás dimensiones. En este caso en cada fila y columna se hallan miembros del Xerorx PARC y se puede ver quien colabora con quien
La disposición matricial garantiza que no hay oclusión ni entre enlaces ni entre nodos. Por otro lado el estudio de los patrones visuales que surgen permite identificar agrupaciones y "comunidades" permutando el orden de filas y columnas de manera que los nodos más enlazados mutuamente se encuentren cercanos.
Ventajas
- Ausencia de oclusión entre los nodos, lo que permite siempre leer su etiqueta.
- No hay cruzamiento entre enlaces , lo que permite identificar fácilmente el origen y el destino del enlace.
- Fácil identificación de la ausencia de conexiones.
- Supera sistemáticamente a los grafos en diferentes tareas como contar nodos, encontrar enlaces etc cuando el número de nodos supera los 20.
- Para un mismo nivel de detalle se requiere un espacio mayor que en el grafo tradicional.
- Para redes pequeñas (<20 nodos, 20-30 enlaces) el grafo es más efectivo.
- Mayor dificultad para seguir caminos (por ejemplo del nodo A al B pasando por el C)
- Falta de familiaridad, constituyen un paradigma mucho menos conocido e intuitivo.
Se pueden volver a formular las representaciones de la matriz de modo que se pueden procesar de manera eficiente esas secuencias de transformación. Es posible expresar cada una de las transformaciones básicas en la forma de matriz general con las posiciones de coordenadas P y P’ representadas como columnas de vector.
P' = M1·P + M2
La matriz M1 es una matriz de 2 por 2 que contiene factores de multiplicación y M2 es una matriz de columnas de dos elementos que contiene términos de traslación. Para la traslación, M1 es la matriz de identidad. Para la rotación o la escalación M2 contiene los términos de traslación asociados con el punto pivote o el punto fijo de escalación.
Un planteamiento más eficiente combinaría las transformaciones de manera que se obtengan las coordenadas finales directamente a partir de las coordenadas iniciales para eliminar el cálculo de coordenadas intermedias. De esta manera, se debe de formular nuevamente la ecuación para eliminar la adición de la matriz asociada con los términos de la traslación M2.
Para expresar cualquier transformación bidimensional como una multiplicación de matriz, representamos cada posición de coordenadas cartesianas (x, y) con las tres coordenadas homogéneas (xh, yh, h), donde
x = xh / h, y = yh / h
Por tanto, una representación general de coordenadas homogéneas se puede expresar también como (h·x, h·y, h). Para transformaciones geométricas bidimensionales, seleccionamos el parámetro homogéneo h como cualquier valor no cero. Así, existe un número finito de representaciones homogéneas equivalentes para cada punto de coordenadas (x, y).
Una opción conveniente consiste en sólo establecer h = 1. Entonces, se representa cada posición bidimensional con las coordenadas homogéneas (x, y, 1). Se requieren otros valores para el parámetro h, por ejemplo, en las formulaciones de matriz de transformaciones de vista tridimensionales.
Conclusion:
Una representación matricial es la manera en que los pixeles se distribuyen en una maya, esto aplica en las imágenes y figuras geométricas y es un principio básico del software para la manipulación de los mismos , esto nos permite tambien aplicar colores, este tipo de representación facilita el uso de formulas para poder aplicar las transformaciones geométricas, las cuales son dependientes de formulas para poder actuar y modificar nuestros gráficos, es importante saber esto para poder comprender el comportamiento de las imágenes.
No hay comentarios:
Publicar un comentario