Гиперболическое дерево

Гиперболическое дерево (часто сокращается до гипердерева ) — это метод визуализации информации и рисования графов, вдохновленный гиперболической геометрией .

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

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

Отображение иерархических данных в виде дерева страдает от визуального беспорядка, поскольку количество узлов на уровне может расти экспоненциально. Для простого двоичного дерева максимальное количество узлов на уровне n равно 2. ^н , тогда как число узлов для деревьев с большей ветвью растет гораздо быстрее. Таким образом, для рисования дерева в виде диаграммы узлов-связей требуется экспоненциальное количество пространства для отображения.

Один из подходов — использовать гиперболическое дерево , впервые предложенное Лампингом и др. Гиперболические деревья используют гиперболическое пространство , которое по сути имеет «больше места», чем евклидово пространство. Например, линейное увеличение радиуса круга в евклидовом пространстве увеличивает его длину линейно, в то время как длина того же круга в гиперболическом пространстве будет увеличиваться экспоненциально. Использование этого свойства позволяет размещать дерево в гиперболическом пространстве лаконично: размещение узла достаточно далеко от его родителя дает узлу почти такое же пространство, что и его родительский элемент, для размещения собственных дочерних элементов.

Для отображения гиперболического дерева обычно используется диска Пуанкаре модель гиперболической геометрии Клейна-Бельтрами , хотя также можно использовать модель . Оба отображают всю гиперболическую плоскость внутри единичного диска, делая видимым сразу все дерево. Единичный диск дает вид плоскости с помощью объектива «рыбий глаз», уделяя больше внимания узлам, которые находятся в фокусе, и отображая узлы, находящиеся вне фокуса ближе к границе диска. Обход гиперболического дерева требует преобразований Мёбиуса пространства, выделения новых узлов и перемещения более высоких уровней иерархии из поля зрения.

Гиперболические деревья были запатентованы в США компанией Xerox в 1996 году, но срок действия патента с тех пор истек.

См. также

• Гиперболическая геометрия
• Бинарная мозаика
• Визуализация информации
• Радиальное дерево – тоже круговое, но использует линейную геометрию.
• Дерево (структура данных)
• Дерево (теория графов)

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

• d3-hypertree — реализация гиперболического дерева HTML5, лицензия MIT
• Гиперболическое древо жизни – визуализация дерева жизни с открытым исходным кодом с использованием набора данных Open Tree of Life.
• Зеленое Древо Жизни – Древо Жизни – Калифорнийский университет в Беркли и Гербарии Джепсона.
• Древо жизни Аналогично предыдущему, но с картинками.
• RogueViz поддерживает гиперболические деревья.