Гиперболическое дерево
Гиперболическое дерево (часто сокращается до гипердерево) — это метод визуализации информации и графов на основе геометрии Лобачевского.
Представление иерархических данных в виде дерева страдает от роста визуального беспорядка, так как число узлов по уровням может расти экспоненциально. Для простого бинарного дерева максимальное число узлов на уровне n равно 2n, а для бо́льших деревьев число узлов растёт быстрее. Представление дерева как диаграммы связи узлов тогда требует экспоненциональное пространство для рисунка.
Один из подходов — использование гиперболического дерева, впервые предложенного Ламперингом, Рао и Пиролли[1]. Гиперболические деревья используют гиперболическое пространство, которое от природы имеет «больше пространства», чем евклидово пространство. Например, линейное увеличение радиуса окружности в евклидовом пространстве увеличивает его длину окружности линейно, в то время как длина той же окружности в гиперболическом пространстве будет расти экспоненциально. Использование этого свойства позволяет расположить дерево в гиперболическом пространстве в лаконичной манере — размещение узла достаточно далеко от его родителя даёт узлу почти то же количество пространства для расположения собственных детей, что и у его родителя.
Рисование гиперболического дерева обычно использует дисковую модель Пуанкаре гиперболической геометрии, хотя может быть использована также модель Кляйна — Белтрами. Обе модели располагают всю гиперболическую плоскость в единичном диске, что делает дерево видимым всё сразу. Единичный диск даёт образ плоскости как в линзе «рыбий глаз», выделяя узлы, находящиеся в фокусе, и показывая узлы вне фокуса ближе к краю диска. Обход гиперболического дерева требует преобразования Мёбиуса пространства, которые переносят новые узлы в фокус и переносят более высокие уровни иерархии из поля зрения.
Гиперболические деревья были запатентованы в США компанией Xerox[2].
См. также
править- Геометрия Лобачевского
- Двоичное замощение[англ.]
- Визуализация информации
- Радиальное дерево — is also circular, but uses linear geometry.
- Дерево (структура данных)
- Дерево (теория графов)
Примечания
править- ↑ Lamping, Rao, Pirolli, 1995, с. 401–408.
- ↑ 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
Ссылки
править- d3-hypertree — HTML5 Hyperbolic tree implementation, MIT licensed
- Hyperbolic Tree of life — Open source tree of life visualisation using Open Tree of Life data set
- The Green Tree of Life — Tree of life — University of California at Berkeley and Jepson Herbaria
- Tree of life Similar to the above, but with pictures
- RougeViz supports hyperbolic trees.
Для улучшения этой статьи желательно:
|