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

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

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

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

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

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

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

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

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

  1. ^ Лэмпинг, Джон Огден; Рао, Рамана; Пиролли, Питер (май 1995 г.). Техника фокус + контекст, основанная на гиперболической геометрии для визуализации больших иерархий . Труды конференции ACM по человеческому фактору в вычислительных системах (CHI 1995). С. 401–408. DOI : 10.1145 / 223904.223956 . Архивировано 10 мая 2017 года . Проверено 13 апреля 2021 .
  2. ^ Патент США 5590250 , Лампа ; Джон О. и Рао; Рамана Б., «Расположение структур узловых звеньев в пространстве с отрицательной кривизной», поручено Xerox Corporation 

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