Древовидное отображение
В информации и вычислениях визуализации древовидное отображение — это метод отображения иерархических данных с использованием вложенных фигур, обычно прямоугольников.
Древовидные карты отображают иерархические ( деревовидные ) данные в виде набора вложенных прямоугольников. Каждой ветви дерева дается прямоугольник, который затем закрывается прямоугольниками меньшего размера, представляющими подветви. Прямоугольник листового узла имеет площадь, пропорциональную указанному размеру данных . [1] Часто листовые узлы окрашиваются, чтобы показать отдельное измерение данных.
Когда размеры цвета и размера каким-то образом коррелируют с древовидной структурой, часто можно легко увидеть закономерности, которые было бы трудно обнаружить другими способами, например, является ли определенный цвет особенно актуальным. Второе преимущество древовидных карт заключается в том, что по своей конструкции они эффективно используют пространство. В результате они могут одновременно четко отображать на экране тысячи элементов.
Алгоритмы тайлинга
[ редактировать ]Чтобы создать древовидную карту, необходимо определить мозаики алгоритм , то есть способ разделения региона на подрегионы указанных областей. В идеале алгоритм древовидной карты должен создавать регионы, удовлетворяющие следующим критериям:
- Небольшое соотношение сторон — в идеале близкое к единице. Области с небольшим соотношением сторон (т. е. толстые объекты ) воспринимаются легче. [2]
- Сохранять некоторый смысл порядка во входных данных (упорядочено).
- Изменение для отражения изменений в базовых данных (высокая стабильность).
Эти свойства имеют обратную зависимость. Поскольку соотношение сторон оптимизировано, порядок размещения становится менее предсказуемым. По мере того, как порядок становится более стабильным, соотношение сторон ухудшается. [ нужен пример ]
Прямоугольные древовидные карты
[ редактировать ]На сегодняшний день разработано пятнадцать основных алгоритмов прямоугольных древовидных карт:
Алгоритм | Заказ | Соотношения сторон | Стабильность |
---|---|---|---|
ДвоичноеДерево | частично заказан | высокий | стабильный |
Нарезать и нарезать кубиками [4] | заказал | очень высокий | стабильный |
Полоска [5] | заказал | середина | средняя стабильность |
Поворот по середине [6] | заказал | середина | средняя стабильность |
Разворот по разделению [6] | заказал | середина | низкая стабильность |
Разворот по размеру [6] | заказал | середина | средняя стабильность |
Расколоть [7] | заказал | середина | средняя стабильность |
Спираль [8] | заказал | середина | средняя стабильность |
Гильберт [9] | заказал | середина | средняя стабильность |
Мур [9] | заказал | середина | средняя стабильность |
Квадратный [10] | заказал | низкий | низкая стабильность |
Смешанные древовидные карты [11] | неупорядоченный | низкий | средняя стабильность |
Приближение [12] | неупорядоченный | низкий | средняя стабильность |
Гит [13] | неупорядоченный | середина | стабильный |
Местные перемещения [14] | неупорядоченный | середина | стабильный |
Выпуклые древовидные карты
[ редактировать ]Прямоугольные древовидные карты имеют тот недостаток, что в худшем случае их соотношение сторон может быть сколь угодно высоким. В качестве простого примера: если у корня дерева только два потомка, один из которых имеет вес и один с весом , то соотношение сторон меньшего дочернего элемента будет , который может быть сколь угодно большим. Чтобы справиться с этой проблемой, было предложено несколько алгоритмов, использующих области, которые представляют собой обычные выпуклые многоугольники , а не обязательно прямоугольные.
Выпуклые древовидные карты разрабатывались в несколько этапов, каждый шаг улучшал верхнюю границу соотношения сторон. Границы даны как функция от - общее количество узлов в дереве, и - общая глубина дерева.
- Онак и Сидиропулос [15] доказал верхнюю границу .
- Де-Берг, Онак и Сидиропулос [16] улучшить верхнюю границу до и докажем нижнюю оценку .
- Де-Берг, Шпекманн и ван-дер-Виле [17] улучшить верхнюю границу до , что соответствует теоретической нижней границе. (Для особого случая, когда глубина равна 1, они представляют алгоритм, который использует только четыре класса многоугольников с углом 45 градусов (прямоугольники, прямоугольные треугольники, прямоугольные трапеции и пятиугольники с углом 45 градусов) и гарантирует соотношение сторон максимум 34/7.)
Последние два алгоритма работают в два этапа (значительно упрощенные для ясности):
- Исходное дерево преобразуется в двоичное дерево: каждый узел, имеющий более двух дочерних элементов, заменяется поддеревом, в котором каждый узел имеет ровно два дочерних элемента.
- Каждая область, представляющая узел (начиная с корня), делится на две с помощью линии, которая сохраняет углы между краями как можно большими. Можно доказать, что если все ребра выпуклого многоугольника разделены углом не менее , то его соотношение сторон равно . Можно добиться того, чтобы в дереве глубины , угол делится не более чем на коэффициент , отсюда и гарантия соотношения сторон.
Ортовыпуклые древовидные карты
[ редактировать ]В выпуклых древовидных картах соотношение сторон не может быть постоянным — оно растет с глубиной дерева. Чтобы добиться постоянного соотношения сторон, используются ортовыпуклые древовидные карты. [17] можно использовать. Здесь все регионы представляют собой орто-выпуклые прямолинейные многоугольники с соотношением сторон не более 64; а листья представляют собой либо прямоугольники с соотношением сторон не более 8, либо L-образные или S-образные формы с соотношением сторон не более 32.
Для особого случая, когда глубина равна 1, они представляют алгоритм, который использует только прямоугольники и L-образные формы, а соотношение сторон не превышает ; внутренние узлы используют только прямоугольники с максимальным соотношением сторон .
Другие древовидные карты
[ редактировать ]- Древовидные карты Вороного
- [18] на основе расчетов диаграммы Вороного . Алгоритм является итеративным и не дает верхней границы соотношения сторон.
- Древовидные карты-головоломки [19]
- на основе геометрии кривых, заполняющих пространство. Они предполагают, что веса являются целыми числами, а их сумма — квадратным числом. Области карты представляют собой прямолинейные многоугольники и сильно неортовыпуклые. Их соотношение сторон гарантированно не превышает 4.
- ГосперКарты
- [20] на основе геометрии кривых Госпера . Он упорядочен и стабилен, но имеет очень высокое соотношение сторон.
История
[ редактировать ]Зональные визуализации существуют уже несколько десятилетий. Например, мозаичные графики (также известные как диаграммы Маримекко) используют прямоугольные мозаики для отображения совместного распределения (т. е. чаще всего они представляют собой по сути столбчатые графики, где столбцы имеют разную ширину). Однако главной отличительной особенностью древовидной карты является рекурсивная конструкция, которая позволяет расширять ее до иерархических данных с любым количеством уровней. Эту идею придумал профессор Бен Шнейдерман в из Лаборатории взаимодействия человека и компьютера Университета Мэриленда начале 1990-х годов. [21] [22] Затем Шнейдерман и его коллеги углубили эту идею, представив различные интерактивные методы фильтрации и настройки древовидных карт.
Все эти ранние древовидные карты использовали простой алгоритм разбиения на части. Несмотря на множество желательных свойств (стабильность, сохранение порядка и простоту реализации), метод срезов и кубиков часто дает мозаику со множеством длинных и тонких прямоугольников. В 1994 году Маунтаз Хаскоэ и Мишель Бодуэн-Лафон изобрели алгоритм «квадратирования», позже популяризированный Ярком ван Вейком , который создавал мозаику, прямоугольники которой были ближе к квадрату. В 1999 году Мартин Ваттенберг использовал вариант алгоритма «квадратизации», который он назвал «поворот и срез», для создания первой сетевой древовидной карты — карты рынка SmartMoney, которая отображала данные о сотнях компаний на фондовом рынке США. После запуска древовидные карты вызвали всплеск интереса, особенно в финансовом контексте. [ нужна ссылка ]
Третья волна инноваций в виде древовидных карт пришла примерно в 2004 году, после того как Маркос Вескамп создал Newsmap — древовидную карту, на которой отображались заголовки новостей. Этот пример неаналитической древовидной карты вдохновил многих подражателей и представил древовидные карты новой, широкой аудитории. [ нужна ссылка ] В последние годы древовидные карты стали популярны в средствах массовой информации, в том числе в газете New York Times. [23] [24] Художественный проект «Древовидная карта» [25] подготовил 12 изображений в рамках для Национальных академий (США) , представленных на выставке «В каждом алгоритме есть ИСКУССТВО». [26] в Вашингтоне и еще один набор для коллекции Музея современного искусства в Нью-Йорке.
См. также
[ редактировать ]- Анализатор дискового пространства
- Визуализация данных и информации
- Диаграмма Маримекко — аналогичная концепция с одним уровнем явной иерархии.
Ссылки
[ редактировать ]- ^ Ли, Рита Йи Ман; Чау, Квонг Винг; Цзэн, Фрэнки Фанджи (2019). «Рейтинг рисков для существующих и новых строительных работ» . Устойчивость . 11 (10): 2863. дои : 10.3390/su11102863 .
- ^ Конг, Н.; Хир, Дж; Агравала, М. (2010). «Перцептивные рекомендации по созданию прямоугольных древовидных карт». Транзакции IEEE по визуализации и компьютерной графике . 16 (6): 990–8. CiteSeerX 10.1.1.688.4140 . дои : 10.1109/TVCG.2010.186 . ПМИД 20975136 . S2CID 11597084 .
- ^ Вернье, Э.; Сондаг, М.; Комба, Дж.; Шпекманн, Б.; Телея, А.; Вербек, К. (2020). «Количественное сравнение зависящих от времени древовидных карт». Форум компьютерной графики . 39 (3): 393–404. arXiv : 1906.06014 . дои : 10.1111/cgf.13989 . S2CID 189898065 .
- ^ Шнейдерман, Бен (2001). «Упорядоченные макеты древовидных карт» (PDF) . Инфовис : 73.
- ^ Бенджамин, Бедерсон; Шнейдерман, Бен; Ваттенберг, Мартин (2002). «Упорядоченные и квантовые древовидные карты: эффективное использование двумерного пространства для отображения иерархий» (PDF) . Транзакции ACM с графикой . 21 (4): 833–854. CiteSeerX 10.1.1.145.2634 . дои : 10.1145/571647.571649 . S2CID 7253456 .
- ^ Перейти обратно: а б с Шнейдерман, Бен; Ваттенберг, Мартин (2001). «Упорядоченные макеты древовидных карт». Симпозиум IEEE по визуализации информации : 73–78.
- ^ Энгдаль, Бьёрн. Упорядоченные и квантовые древовидные карты: эффективное использование двумерного пространства для отображения иерархий .
- ^ Ту, Ю.; Шен, Х. (2007). «Визуализация изменений иерархических данных с помощью древовидных карт» (PDF) . Транзакции IEEE по визуализации и компьютерной графике . 13 (6): 1286–1293. дои : 10.1109/TVCG.2007.70529 . ПМИД 17968076 . S2CID 14206074 . Архивировано (PDF) из оригинала 8 августа 2022 г.
- ^ Перейти обратно: а б Так, С.; Кокберн, А. (2013). «Повышенная пространственная стабильность с помощью древовидных карт Гильберта и Мура» (PDF) . Транзакции IEEE по визуализации и компьютерной графике . 19 (1): 141–148. дои : 10.1109/TVCG.2012.108 . ПМИД 22508907 . S2CID 6099935 .
- ^ Брюльс, Марк; Хейзинг, Кес; ван Вейк, Ярке Дж. (2000). «Квадратные карты деревьев». Ин де Леу, В.; ван Лиер, Р. (ред.). Визуализация данных 2000: Учеб. Совместный симпозиум Eurographics и IEEE TCVG. по визуализации (PDF) . Спрингер-Верлаг. стр. 33–42. .
- ^ Роэль Влиген; Эрик-Ян ван дер Линден; Ярке Дж. ван Вейк . «Визуализация бизнес-данных с помощью обобщенных древовидных карт» (PDF) . Архивировано из оригинала (PDF) 24 июля 2011 года . Проверено 24 февраля 2010 г.
- ^ Нагамоти, Х.; Абэ, Ю.; Ваттенберг, Мартин (2007). «Аппроксимационный алгоритм разделения прямоугольника на прямоугольники с заданными площадями» . Дискретная прикладная математика . 155 (4): 523–537. дои : 10.1016/j.dam.2006.08.005 .
- ^ Вернье, Э.; Комба, Дж.; Телеа, А. (2018). «Количественное сравнение динамических древовидных карт для визуализации эволюции программного обеспечения». Конференция по визуализации программного обеспечения : 99–106.
- ^ Сондаг, М.; Шпекманн, Б.; Вербек, К. (2018). «Стабильные древовидные карты посредством локальных перемещений» . Транзакции IEEE по визуализации и компьютерной графике . 24 (1): 729–738. дои : 10.1109/TVCG.2017.2745140 . ПМИД 28866573 . S2CID 27739774 .
- ^ Кшиштоф Онак; Анастасиос Сидиропулос. «Круговые разделы с приложениями к визуализации и встраиваниям» . Проверено 26 июня 2011 г.
- ^ Марк де Берг; Онак, Кшиштоф; Сидиропулос, Анастасиос (2013). «Толстые многоугольные разбиения с применением к визуализации и встраиваниям» . Журнал вычислительной геометрии . 4 (1): 212–239. arXiv : 1009.1866 .
- ^ Перейти обратно: а б Де Берг, Марк; Шпекманн, Беттина ; Ван дер Вил, Винсент (2014). «Древовидные карты с ограниченным соотношением сторон» . Вычислительная геометрия . 47 (6): 683. arXiv : 1012.1749 . дои : 10.1016/j.comgeo.2013.12.008 . S2CID 12973376 . . Версия конференции: Выпуклые древовидные карты с ограниченным соотношением сторон (PDF) . ЕвроКГ. 2011.
- ^ Бальцер, Майкл; Дойссен, Оливер (2005). «Древовидные карты Вороного». В Стаско, Джон Т.; Уорд, Мэтью О. (ред.). Симпозиум IEEE по визуализации информации (InfoVis 2005), 23–25 октября 2005 г., Миннеаполис, Миннесота, США (PDF) . Компьютерное общество IEEE. п. 7. .
- ^ Ваттенберг, Мартин (2005). «Заметка о визуализациях, заполняющих пространство, и кривых заполнения пространства». В Стаско, Джон Т.; Уорд, Мэтью О. (ред.). Симпозиум IEEE по визуализации информации (InfoVis 2005), 23–25 октября 2005 г., Миннеаполис, Миннесота, США (PDF) . Компьютерное общество IEEE. п. 24. .
- ^ Обер, Дэвид; Юэ, Чарльз; Ламберт, Антуан; Реноу, Бенджамин; Саллаберри, Арно; Солнье, Агнес (2013). « Карта Госпера : использование кривой Госпера для размещения иерархических данных» . Транзакции IEEE по визуализации и компьютерной графике . 19 (11): 1820–1832. дои : 10.1109/TVCG.2013.91 . ПМИД 24029903 . S2CID 15050386 . .
- ^ Шнейдерман, Бен (1992). «Визуализация дерева с помощью древовидных карт: подход к двухмерному заполнению пространства». Транзакции ACM с графикой . 11 : 92–99. дои : 10.1145/102377.115768 . HDL : 1903/367 . S2CID 1369287 .
- ^ Бен Шнейдерман ; Кэтрин Плезант (25 июня 2009 г.). «Древовидные карты для визуализации иерархий в ограниченном пространстве ~ включая историю исследований древовидных карт в Университете Мэриленда» . Проверено 23 февраля 2010 г.
- ^ Кокс, Аманда; Фэрфилд, Ханна (25 февраля 2007 г.). «Здоровье рынка легковых автомобилей, фургонов, внедорожников и грузовиков» . Нью-Йорк Таймс . Проверено 12 марта 2010 г.
- ^ Картер, Шан; Кокс, Аманда (14 февраля 2011 г.). «Бюджетное предложение Обамы на 2012 год: как потрачено 3,7 триллиона долларов» . Нью-Йорк Таймс . Проверено 15 февраля 2011 г.
- ^ «Искусство древовидной карты» . Архивировано из оригинала 5 декабря 2023 г.
- ^ «В каждом алгоритме есть ИСКУССТВО: Art Project Treemap» . КПНАС . Архивировано из оригинала 8 октября 2023 года.
Внешние ссылки
[ редактировать ]- Treemap Art Project подготовил выставку для Национальных академий в Вашингтоне, округ Колумбия.
- «Обнаружение бизнес-аналитики с помощью визуализации древовидных карт» , Бен Шнейдерман , 11 апреля 2006 г.
- Комплексный обзор и библиография методов визуализации дерева.
- Влиген, Роэль; ван Вейк, Ярке Дж.; ван дер Линден, Эрик-Ян (сентябрь – октябрь 2006 г.). «Визуализация бизнес-данных с помощью обобщенных древовидных карт» (PDF) . Транзакции IEEE по визуализации и компьютерной графике . 12 (5): 789–796. дои : 10.1109/TVCG.2006.200 . ПМИД 17080801 . S2CID 18891326 . Архивировано из оригинала (PDF) 24 июля 2011 года.
- История древовидных карт Бена Шнейдермана.
- Исследование гипермедиа с помощью интерактивных динамических карт. Статья Зизи и Бодуэн-Лафона, представляющая алгоритм компоновки квадратной древовидной карты (в то время называвшийся «улучшенной компоновкой древовидной карты»).
- Университета Индианы Описание
- Живая интерактивная древовидная карта, основанная на краудсорсинговых скидках от Flytail Group.
- Образец древовидной карты на английском языке от The Hive Group
- Несколько примеров древовидных карт, созданных с помощью Macrofocus TreeMap.
- Визуализация с использованием динамических древовидных карт и онлайн-программы для создания древовидных карт от Drasticdata.