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

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

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

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

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

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

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

Смотрите также

Рекомендации

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

внешняя ссылка