Дерево-карта

Дерево-карта (treemap) – метод визуализации древовидных структур, который показал себя крайне эффективным при изображении численных атрибутов (таких как, например, размер или стоимость) объектов, организованных в большие иерархии. Он использует соглашение включения при рисовании дерева. Базовая идея метода состоит в том, чтобы изобразить дерево, каждая вершина которого имеет имя и значение численного атрибута, равного сумме значений атрибута всех её сыновей, внутри прямоугольника (или другой выбранной геометрической фигуры) заданного размера. Для изображения поддеревьев используется рекурсивная процедура разбиения прямоугольника, соответствующего корню дерева, на соответствующие сыновьям корня прямоугольники меньшего размера, площади которых пропорциональны значениям атрибута сыновей. В качестве результата такого построения начальный прямоугольник, отведенный под изображение дерева, разбивается на все меньшие и меньшие прямоугольники, размеры которых соответствуют значениям атрибута изображаемых вершин. Структура дерева также отображается в данном изображении, и есть возможности для расширения визуальной информации о дереве, например, для предоставления дополнительной информации о листьях можно использовать цвет и аннотации.

Разновидность данного метода, при которой текущий прямоугольник разбивается на прямоугольники меньшей площади параллельными горизонтальными или вертикальными линиями, направление которых меняется при переходе от одного уровня вершины к следующему, получила название метода продольно-поперечных разрезов.

Во многих коммерческих приложениях, использующих такие представления, стараются сделать каждый прямоугольник как можно более квадратным. Это изображение, получившее название квадрируемое дерево-карта, является, как правило, визуально более привлекательным и простым для понимания, чем дерево-карта, получаемое продольно-поперечными разрезами. Еще более наглядным это изображение становится, если в нём используются специальные выделения поддеревьев, как это имеет место в таких вариантах дерева-карты, как квадрируемое подушечное дерево-карта или фреймовое квадрируемое дерево-карта.

Помимо деревьев-карт, построенных из прямоугольников, имеется большое количество модификаций этого подхода, использующих для изображения вершин графа различные другие геометрические формы, отличные от прямоугольников.

Деревья-карты Вороного используют сечения Вороного для вычисления размещения произвольных многоугольников, заполняющих пространство экрана. Этот подход ориентирован на улучшение выделения границ многоугольников, а также преодоление проблемы большого коэффициента формы.

Весьма популярны также круговые деревья-карты. Хотя эти методы могут приводить к неполному заполнению больших кругов кругами меньшего радиуса, они позволяют строить изображения, хорошо показывающие вложенность.

Литература

• Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей // Научная визуализация. – 2014. – Том. 6, N 1. – С. 31 – 50.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с.
• Shneiderman B. Treemaps for space-constrained visualization of hierar-chies. URL: http://www.cs.umd.edu/hcil/treemap-history/