Гиперболическое дерево
Гиперболическое дерево (часто сокращается до гипердерева ) — это метод визуализации информации и рисования графов, вдохновленный гиперболической геометрией .
Отображение иерархических данных в виде дерева страдает от визуального беспорядка, поскольку количество узлов на уровне может расти экспоненциально. Для простого двоичного дерева максимальное количество узлов на уровне n равно 2. н , тогда как число узлов для деревьев с большей ветвью растет гораздо быстрее. Таким образом, для отображения дерева в виде диаграммы узлов и связей требуется экспоненциально большое пространство для отображения.
Один из подходов — использовать гиперболическое дерево , впервые предложенное Лампингом и др. [1] Гиперболические деревья используют гиперболическое пространство , которое по сути имеет «больше места», чем евклидово пространство. Например, линейное увеличение радиуса круга в евклидовом пространстве увеличивает его длину линейно, в то время как длина того же круга в гиперболическом пространстве будет увеличиваться экспоненциально. Использование этого свойства позволяет размещать дерево в гиперболическом пространстве лаконично: размещение узла достаточно далеко от его родителя дает узлу почти такое же пространство, что и его родительский элемент, для размещения собственных дочерних элементов.
Для отображения гиперболического дерева обычно используется диска Пуанкаре модель гиперболической геометрии Клейна-Бельтрами , хотя также можно использовать модель . Оба отображают всю гиперболическую плоскость внутри единичного диска, делая видимым сразу все дерево. Единичный диск дает вид плоскости через линзу «рыбий глаз», уделяя больше внимания узлам, которые находятся в фокусе, и отображая узлы, находящиеся вне фокуса ближе к границе диска. Обход гиперболического дерева требует преобразований Мёбиуса пространства, выделения новых узлов и перемещения более высоких уровней иерархии из поля зрения.
Гиперболические деревья были запатентованы в США компанией Xerox в 1996 году, но срок действия патента с тех пор истек. [2]
См. также [ править ]
- Гиперболическая геометрия
- Бинарная мозаика
- Визуализация информации
- Радиальное дерево – тоже круговое, но использует линейную геометрию.
- Дерево (структура данных)
- Дерево (теория графов)
Ссылки [ править ]
- ^ Лэмпинг, Джон Огден; Рао, Рамана; Пиролли, Питер (май 1995 г.). Техника фокус+контекст, основанная на гиперболической геометрии, для визуализации больших иерархий . Материалы конференции ACM по человеческому фактору в вычислительных системах (CHI 1995). стр. 401–408. CiteSeerX 10.1.1.20.1530 . дои : 10.1145/223904.223956 . Архивировано из оригинала 10 мая 2017 г. Проверено 13 апреля 2021 г.
- ^ Патент США 5590250 , Лампа; Джон О. и Рао; Рамана Б., «Размещение узлово-связывающих структур в пространстве отрицательной кривизны», поручено корпорации Xerox.
Внешние ссылки [ править ]
- d3-hypertree — реализация гиперболического дерева HTML5, лицензия MIT
- Гиперболическое древо жизни – визуализация дерева жизни с открытым исходным кодом с использованием набора данных Open Tree of Life.
- Зеленое Древо Жизни – Древо Жизни – Калифорнийский университет в Беркли и гербарий Джепсона.
- Древо жизни Аналогично предыдущему, но с картинками.
- RogueViz поддерживает гиперболические деревья.