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