Gráfico de rectángulos

En visualización de información y computación, un Gráfico de rectángulos o mapeo de árboles es un método para mostrar datos jerárquicos utilizando figuras anidadas, generalmente rectángulos.

Los diagramas de árbol muestran datos jerárquicos (estructurados en árbol) como un conjunto de rectángulos anidados. A cada rama del árbol se le da un rectángulo, que luego se teja con rectángulos más pequeños que representan sub-ramas. El rectángulo de un nodo de hoja tiene un área proporcional a una dimensión específica de los datos. A menudo, los nodos de hoja se colorean para mostrar una dimensión separada de los datos.

Cuando las dimensiones de color y tamaño se correlacionan de alguna manera con la estructura del árbol, a menudo se pueden ver fácilmente patrones que serían difíciles de detectar de otra manera, como si un determinado color es particularmente relevante. Una segunda ventaja de los diagramas de árbol es que, por construcción, hacen un uso eficiente del espacio. Como resultado, pueden mostrar de manera legible miles de elementos en la pantalla simultáneamente.

Algoritmos de mosaico

Para crear un mapa de árbol, se debe definir un algoritmo de mosaico, es decir, una forma de dividir una región en subregiones de áreas específicas. Idealmente, un algoritmo de diagrama de árbol crearía regiones que satisfagan los siguientes criterios:

1. Una relación de aspecto pequeña, idealmente cercana a uno. Las regiones con una relación de aspecto pequeña (es decir, objetos gordos) son más fáciles de percibir.
2. Conservar cierto sentido del orden en los datos de entrada (ordenados).
3. Cambie para reflejar los cambios en los datos subyacentes (alta estabilidad).

Desafortunadamente, estas propiedades tienen una relación inversa. A medida que se optimiza la relación de aspecto, el orden de ubicación se vuelve menos predecible. A medida que el orden se vuelve más estable, la relación de aspecto se degrada.

Diagramas de árbol rectangulares

Hasta la fecha, se han desarrollado quince algoritmos primarios de mapas de árboles rectangulares:

Mapas de árbol convexos

Los mapas de árbol rectangulares tienen la desventaja de que su relación de aspecto puede ser arbitrariamente alta en el peor de los casos. Como ejemplo simple, si la raíz del árbol tiene solo dos hijos, uno con peso y otro con peso , entonces la relación de aspecto del hijo más pequeño será , que puede ser arbitrariamente alta. Para hacer frente a este problema, se han propuesto varios algoritmos que utilizan regiones que generalmente son polígonos convexos, no necesariamente rectangulares.

Los mapas de árbol convexos se desarrollaron en varios pasos, cada paso mejoró el límite superior de la relación de aspecto. Los límites se dan en función de - el número total de nodos en el árbol, y - la profundidad total del árbol.

1. Onak y Sidiropoulos demostraron un límite superior de .
2. De-Berg y Onak y Sidiropoulos mejoran el límite superior a , y prueban un límite inferior de .
3. De-Berg, Speckmann y van-der-Weele mejoran el límite superior a , igualando el límite inferior teórico. (Para el caso especial donde la profundidad es 1, presentan un algoritmo que usa solo cuatro clases de polígonos de 45 grados (rectángulos, triángulos rectángulos, trapecios de ángulo recto y pentágonos de 45 grados), y garantiza una relación de aspecto de como máximo 34/7.)

Los dos últimos algoritmos operan en dos pasos (muy simplificados para mayor claridad):

1. El árbol original se convierte en un árbol binario: cada nodo con más de dos hijos se reemplaza por un subárbol en el que cada nodo tiene exactamente dos hijos.
2. Cada región que representa un nodo (a partir de la raíz) se divide en dos, utilizando una línea que mantiene los ángulos entre los bordes lo más grandes posible. Es posible probar que, si todos los bordes de un polígono convexo están separados por un ángulo de al menos , entonces su relación de aspecto es . Es posible asegurar que, en un árbol de profundidad , el ángulo se divida por un factor de como máximo , de ahí la garantía de relación de aspecto.

Treemaps ortoconvexos

En los mapas de árbol convexos, la relación de aspecto no puede ser constante: crece con la profundidad del árbol. Para lograr una relación de aspecto constante, se pueden utilizar mapas de árbol ortoconvexos. Allí, todas las regiones son polígonos rectilíneos ortoconvexos con una relación de aspecto de 64 como máximo; y las hojas son rectángulos con una relación de aspecto de 8 como máximo, o formas en L o en forma de S con una relación de aspecto de 32 como máximo.

Para el caso especial donde la profundidad es 1, presentan un algoritmo que usa solo rectángulos y formas de L, y la relación de aspecto es como máximo ; los nodos internos usan solo rectángulos con relación de aspecto como máximo .

Otros mapas de árbol

Diagramas de árbol de Voronoibasado en cálculos del diagrama de Voronoi. El algoritmo es iterativo y no da ningún límite superior en la relación de aspecto.Diagramas de árbol de rompecabezasbasado en la geometría de las curvas que llenan el espacio. Asumen que los pesos son números enteros y que su suma es un número cuadrado. Las regiones del mapa son polígonos rectilíneos y muy no ortoconvexos. Se garantiza que su relación de aspecto sea como máximo 4.GosperMapasbasado en la geometría de las curvas de Gosper. Es ordenado y estable, pero tiene una relación de aspecto muy alta.

Historia

Las visualizaciones basadas en áreas existen desde hace décadas. Por ejemplo, los diagramas de mosaico (también conocidos como diagramas de Marimekko) utilizan mosaicos rectangulares para mostrar distribuciones conjuntas (es decir, por lo general son esencialmente diagramas de columnas apiladas donde las columnas tienen diferentes anchos). Sin embargo, la principal característica distintiva de un diagrama de árbol es la construcción recursiva que permite extenderlo a datos jerárquicos con cualquier número de niveles. Esta idea fue inventada por el profesor Ben Shneiderman en el Laboratorio de Interacción Humano-Computadora de la Universidad de Maryland a principios de la década de 1990. Shneiderman y sus colaboradores luego profundizaron en la idea mediante la introducción de una variedad de técnicas interactivas para filtrar y ajustar los mapas de árbol.

Todos estos primeros mapas de árbol usaban el algoritmo de mosaico simple "cortar y cortar". A pesar de muchas propiedades deseables (es estable, conserva el orden y es fácil de implementar), el método de cortar y cortar a menudo produce mosaicos con muchos rectángulos largos y delgados. En 1994, Mountaz Hascoet y Michel Beaudouin-Lafon inventaron un algoritmo de "cuadratura", más tarde popularizado por Jarke van Wijk, que creaba mosaicos cuyos rectángulos estaban más cerca del cuadrado. En 1999, Martin Wattenberg utilizó una variación del algoritmo de "cuadratura" que denominó "pivotar y dividir" para crear el primer mapa de árbol basado en la web, el SmartMoney Map of the Market, que mostraba datos de cientos de empresas en el mercado de valores de EE. UU. Tras su lanzamiento, los mapas de árboles disfrutaron de un gran interés, especialmente en contextos financieros.

Una tercera ola de innovación de mapas de árbol se produjo alrededor de 2004, después de que Marcos Weskamp creara Newsmap, un mapa de árbol que mostraba titulares de noticias. Este ejemplo de un mapa de árbol no analítico inspiró a muchos imitadores e introdujo los mapas de árbol a una audiencia nueva y amplia. En los últimos años, los mapas de árboles se han abierto camino en los principales medios de comunicación, incluido el uso del New York Times. El Treemap Art Project produjo 12 imágenes enmarcadas para las Academias Nacionales (Estados Unidos), mostró la exhibición Every AlgoRiThm has ART in It en Washington, DC y otro conjunto para la colección del Museo de Arte Moderno de Nueva York.