Древовидная карта - Treemapping

Древовидная карта экспорта Сингапура по категориям продуктов, 2012 г. Древовидные карты экспорта товаров - одно из самых последних приложений такого рода визуализаций, разработанное Обсерваторией экономической сложности Гарварда и Массачусетского технологического института .

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

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

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

Алгоритмы тайлинга

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

  1. Небольшое соотношение сторон - в идеале близкое к единице. Области с малым соотношением сторон (например, толстые объекты ) легче воспринимаются.
  2. Сохраните некоторый смысл порядка во входных данных.
  3. Измените, чтобы отразить изменения в базовых данных.

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

Прямоугольные карты деревьев

На сегодняшний день разработано шесть основных алгоритмов прямоугольных древовидных карт:

Алгоритмы древовидной карты
Алгоритм Заказ Соотношения сторон Стабильность
BinaryTree частично заказанный высокая стабильный
Смешанные карты деревьев неупорядоченный самый низкий стабильный
Упорядоченный и квантовый частично заказанный средний средняя устойчивость
Нарезать и нарезать приказал очень высоко стабильный
В квадрате неупорядоченный самый низкий средняя устойчивость
Полоска приказал средний средняя устойчивость

Выпуклые карты деревьев

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

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

  1. Онак и Сидиропулос доказали верхнюю границу .
  2. Де-Берг, Онак и Сидиропулос улучшают верхнюю оценку и доказывают нижнюю оценку .
  3. Де-Берг, Спекманн и Ван-дер-Виле улучшают верхнюю границу до , совпадающую с теоретической нижней границей. (Для особого случая, когда глубина равна 1, они представляют алгоритм, который использует только четыре класса 45-градусных многоугольников (прямоугольники, прямоугольные треугольники, прямоугольные трапеции и 45-градусные пятиугольники) и гарантирует соотношение сторон из не более 34/7.)

Последние два алгоритма работают в два этапа (сильно упрощены для ясности):

  1. Исходное дерево преобразуется в двоичное дерево: каждый узел с более чем двумя дочерними элементами заменяется поддеревом, в котором каждый узел имеет ровно два дочерних элемента.
  2. Каждая область, представляющая узел (начиная с корня), делится на две части с помощью линии, которая сохраняет углы между краями как можно большими. Можно доказать, что если все ребра выпуклого многоугольника разделены углом не менее , то его соотношение сторон равно . Можно гарантировать, что в дереве глубины угол делится не более чем на коэффициент , следовательно, соотношение сторон гарантировано.

Ортовыпуклые карты деревьев

В выпуклых древовидных картах соотношение сторон не может быть постоянным - оно растет вместе с глубиной дерева. Для достижения постоянного соотношения сторон можно использовать ортовыпуклые карты дерева . Здесь все области представляют собой ортовыпуклые прямолинейные многоугольники с соотношением сторон не более 64; а листья представляют собой либо прямоугольники с соотношением сторон не более 8, либо L-образные или S-образные формы с соотношением сторон не более 32.

Для особого случая, когда глубина равна 1, они представляют алгоритм, который использует только прямоугольники и L-образные формы, а соотношение сторон - не выше ; внутренние узлы используют только прямоугольники с соотношением сторон не выше .

Другие карты деревьев

Карты деревьев Вороного
на основе расчетов диаграммы Вороного . Алгоритм является итеративным и не дает верхней границы соотношения сторон.
Пазлы с деревьями
на основе геометрии кривых заполнения пространства. Они предполагают, что веса являются целыми числами, а их сумма - квадратным числом. Области карты представляют собой прямолинейные многоугольники и сильно неорто-выпуклые. Их соотношение сторон гарантированно не превышает 4.
ГосперКарты
на основе геометрии кривых Госпера . Он упорядочен и стабилен, но имеет очень высокое соотношение сторон.

История

Визуализация использования места на жестком диске в программе TreeSize , впервые выпущенной в 1996 г.

Визуализации по областям существуют десятилетиями. Например, мозаичные графики (также известные как диаграммы Маримекко) используют прямоугольные мозаики для отображения совместных распределений (т. Е. Чаще всего они представляют собой по существу составленные столбцы графиков, где столбцы имеют разную ширину). Однако главной отличительной особенностью древовидной карты является рекурсивная конструкция, которая позволяет расширить ее до иерархических данных с любым количеством уровней. Эта идея была изобретена профессором Бен Шнейдерман в Университете штата Мэриленд человека - Computer Interaction Lab в начале 1990 - х годов. Затем Шнейдерман и его сотрудники углубили идею, представив различные интерактивные методы фильтрации и настройки древовидной карты.

Во всех этих ранних древовидных картах использовался простой алгоритм мозаики «срезы и кости». Несмотря на многие желательные свойства (он стабилен, сохраняет порядок и прост в реализации), метод нарезки и кости часто создает мозаику с множеством длинных тонких прямоугольников. В 1994 году Маунтаз Хаскоет и Мишель Бодуэн-Лафон изобрели алгоритм «квадратификации», впоследствии популяризированный Ярком ван Вейком , который создавал мозаики, прямоугольники которых были ближе к квадрату. В 1999 году Мартин Ваттенберг использовал вариант алгоритма «разбиения на квадраты», который он назвал «поворот и срез», чтобы создать первую древовидную карту на базе Интернета, SmartMoney Map of the Market, которая отображала данные о сотнях компаний на фондовом рынке США. После запуска карты деревьев вызвали всплеск интереса, особенно в финансовом контексте.

Третья волна инноваций в виде древовидной карты возникла примерно в 2004 году, после того как Маркос Вескэмп создал карту новостей - древовидную карту , на которой отображались заголовки новостей. Этот пример неаналитической древовидной карты вдохновил многих подражателей и представил древовидные карты новой широкой аудитории. В последние годы древовидные карты стали использоваться в основных средствах массовой информации, в том числе в New York Times. В рамках проекта Treemap Art Project было подготовлено 12 изображений в рамке для национальных академий (США) , была показана выставка Every AlgoRiThm имеет искусство в ней в Вашингтоне, округ Колумбия, и еще один набор для коллекции Музея современного искусства в Нью-Йорке.

Смотрите также

использованная литература

внешние ссылки