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

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

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

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

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

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

См. также

править

Примечания

править
  1. Lamping, Rao, Pirolli, 1995, с. 401–408.
  2. Lamping; John O. & Rao; Ramana B., "Layout of node-link structures in space with negative curvature", US patent 5590250

Литература

править
  • Lamping, John; Rao, Ramana; Pirolli, Peter (1995). A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI 1995). Архивная копия от 10 мая 2017 на Wayback Machine

Ссылки

править