Из Википедии, бесплатной энциклопедии
  (Перенаправлено с древовидной карты )
Перейти к навигации Перейти к поиску

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

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

Основная идея [ править ]

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

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

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

Алгоритмы тайлинга [ править ]

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

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

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

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

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

Алгоритмы древовидной карты [3]
АлгоритмЗаказСоотношения сторонСтабильность
BinaryTreeчастично заказанныйвысокостабильный
Смешанные карты деревьев [4]неупорядоченныйсамый низкийстабильный
Упорядоченный и квантовый [5]частично заказанныйсреднийсредняя устойчивость
Нарезать и нарезать [6]упорядоченныйочень высокостабильный
В квадрате [7]неупорядоченный [ требуется дальнейшее объяснение ]самый низкийсредняя устойчивость
Стриптиз [8]упорядоченныйсреднийсредняя устойчивость

Выпуклые древовидные карты [ править ]

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

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

1. Онак и Сидиропулос [9] доказали верхнюю оценку .

2. Де-Берг, Онак и Сидиропулос [10] улучшают верхнюю оценку и доказывают нижнюю оценку .

3. Де-Берг, Спекманн и Ван-дер-Виле [11] улучшают верхнюю границу до , совпадающую с теоретической нижней границей.

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

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

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

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

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

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

Другие древовидные карты [ править ]

Карты дерева Вороного [12] - основаны на расчетах диаграммы Вороного . Алгоритм является итеративным и не дает верхней границы соотношения сторон.

Jigsaw Treemaps [13] - основан на геометрии кривых заполнения пространства. Они предполагают, что веса являются целыми числами, а их сумма - квадратным числом. Области карты представляют собой прямолинейные многоугольники и сильно неорто-выпуклые. Их соотношение сторон гарантированно не превышает 4.

GosperMaps [14] - основан на геометрии кривых Госпера . Он упорядочен и стабилен, но имеет очень высокое соотношение сторон.

История [ править ]

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

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

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

См. Также [ править ]

  • Анализатор дискового пространства
  • Визуализация информации
  • Список стран по экономической сложности , который включает в себя древовидные карты экспорта товаров.
  • Диаграмма Маримекко , аналогичная концепция с одним уровнем явной иерархии.

Ссылки [ править ]

  1. ^ Ли, Рита Йи Ман; Чау, крыло Квонг; Цзэн, Фрэнки Фаньцзе (2019). «Рейтинг рисков для существующих и новых строительных работ» . Устойчивое развитие . 11 (10): 2863. DOI : 10,3390 / su11102863 .
  2. ^ Kong, N; Хеер, Дж; Агравала, М. (2010). «Рекомендации по созданию прямоугольных древовидных карт». IEEE Transactions по визуализации и компьютерной графике . 16 (6): 990–8. CiteSeerX 10.1.1.688.4140 . DOI : 10.1109 / TVCG.2010.186 . PMID 20975136 . S2CID 11597084 .   
  3. ^ а б Бен Шнейдерман ; Екатерина Плезан (25 июня 2009 г.). «Древовидные карты для визуализации иерархий в ограниченном пространстве ~ Включая историю исследований древовидных карт в Университете Мэриленда» . Проверено 23 февраля 2010 года .
  4. ^ Рул Vliegen; Эрик-Ян ван дер Линден; Ярке Й. ван Вейк . «Визуализация бизнес-данных с помощью обобщенных древовидных карт» (PDF) . Архивировано из оригинального (PDF) 24 июля 2011 года . Проверено 24 февраля 2010 года .
  5. ^ Бедерсон, Бенджамин Б.; Шнейдерман, Бен; Ваттенберг, Мартин (2002). «Упорядоченные и квантовые древовидные карты: эффективное использование двумерного пространства для отображения иерархий». Транзакции ACM на графике . 21 (4): 833. CiteSeerX 10.1.1.145.2634 . DOI : 10.1145 / 571647.571649 . S2CID 7253456 .  
  6. ^ Шнейдерман, Бен (2001). «Упорядоченные макеты древовидной карты» (PDF) . Инфовис : 73.
  7. ^ Брюлс, Марк; Хейзинг, Кес; ван Вейк, Джарк Дж. (2000). "Квадратные карты деревьев". In de Leeuw, W .; ван Лиере, Р. (ред.). Визуализация данных 2000: Учеб. Совместное издание Eurographics и IEEE TCVG Symp. по визуализации (PDF) . Springer-Verlag. стр. 33–42 {{несогласованные цитаты}} .
  8. ^ Бенджамин, Бедерсон; Шнейдерман, Бен; Ваттенберг, Мартин (2002). «Упорядоченные и квантовые древовидные карты: эффективное использование двумерного пространства для отображения иерархий» (PDF) . Транзакции ACM на графике . 21 (4): 833–854. CiteSeerX 10.1.1.145.2634 . DOI : 10.1145 / 571647.571649 . S2CID 7253456 .   
  9. ^ Кшиштоф Онак; Анастасиос Сидиропулос. «Круговые перегородки с приложениями к визуализации и вложениям» . Проверено 26 июня 2011 года .
  10. ^ Марк де Берг; Онак, Кшиштоф; Сидиропулос, Анастасиос (2010). «Жирные многоугольные перегородки с приложениями для визуализации и встраивания». arXiv : 1009.1866 [ cs.CG ].
  11. ^ а б Де Берг, Марк; Спекманн, Беттина ; Ван дер Виле, Винсент (2014). «Древовидные карты с ограниченным соотношением сторон». Вычислительная геометрия . 47 (6): 683. arXiv : 1012.1749 . DOI : 10.1016 / j.comgeo.2013.12.008 . S2CID 12973376 . . Версия конференции: Выпуклые древовидные карты с ограниченным соотношением сторон (PDF) . EuroCG. 2011 г.
  12. ^ Бальзер, Майкл; Деуссен, Оливер (2005). "Карты деревьев Вороного". В Стаско, Джон Т .; Уорд, Мэтью О. (ред.). Симпозиум IEEE по визуализации информации (InfoVis 2005), 23-25 ​​октября 2005 г., Миннеаполис, Миннесота, США (PDF) . Компьютерное общество IEEE. п. 7. .
  13. ^ Ваттенберг, Мартин (2005). «Заметка о визуализациях заполнения пространства и кривых заполнения пространства». В Стаско, Джон Т .; Уорд, Мэтью О. (ред.). Симпозиум IEEE по визуализации информации (InfoVis 2005), 23-25 ​​октября 2005 г., Миннеаполис, Миннесота, США (PDF) . Компьютерное общество IEEE. п. 24. .
  14. ^ Обер, Дэвид; Huet, Чарльз; Ламберт, Антуан; Ренуст, Бенджамин; Саллаберри, Арно; Сольнье, Агнес (2013). « Карта Госпера : Использование кривой Госпера для построения иерархических данных» . IEEE Transactions по визуализации и компьютерной графике . 19 (11): 1820–1832. DOI : 10.1109 / TVCG.2013.91 . PMID 24029903 . S2CID 15050386 .  .
  15. ^ Шнейдерман, Бен (1992). «Визуализация дерева с помощью древовидных карт: подход к заполнению двухмерного пространства». Транзакции ACM на графике . 11 : 92–99. DOI : 10.1145 / 102377.115768 . hdl : 1903/367 . S2CID 1369287 . 
  16. ^ Кокс, Аманда; Фэрфилд, Ханна (25 февраля 2007 г.). «Здоровье рынка автомобилей, фургонов, внедорожников и грузовиков» . Нью-Йорк Таймс . Проверено 12 марта 2010 года .
  17. ^ Картер, Шан; Кокс, Аманда (14 февраля 2011 г.). «Бюджетное предложение Обамы на 2012 год: как потрачено 3,7 триллиона долларов» . Нью-Йорк Таймс . Проверено 15 февраля 2011 года .

Внешние ссылки [ править ]

  • Treemap Art Project подготовил выставку для национальных академий в Вашингтоне, округ Колумбия.
  • Статья Бена Шнейдермана об использовании карт деревьев (в качестве гостя на www.perceptualedge.com [1] )
  • Всесторонний обзор и библиография методов визуализации деревьев
  • Обобщенные древовидные карты
  • История древовидных карт Бена Шнейдермана.
  • Исследование гипермедиа с помощью интерактивных динамических карт. Бумага Зизи и Бодуэна-Лафона, представляющая алгоритм построения квадратной карты дерева (в то время называемый «улучшенная разметка карты дерева»).
  • Описание университета Индианы
  • Интерактивная древовидная карта в реальном времени, основанная на краудсорсинговых скидках от Flytail Group
  • Образец древовидной карты на английском языке от The Hive Group
  • Несколько примеров древовидной карты, созданных с помощью Macrofocus TreeMap
  • Визуализации с использованием динамических древовидных карт и программного обеспечения для создания древовидных карт от drasticdata
  • Древовидные карты экспорта продуктов, разработанные Обсерваторией экономической сложности Гарвардского технологического института (Массачусетского технологического института)
  • newsmap.jp - это древовидная карта новостей Google.