Русская Википедия:Гиперболическое дерево
Гиперболическое дерево (часто сокращается до гипердерево) — это метод визуализации информации и графов на основе геометрии Лобачевского.
Представление иерархических данных в виде дерева страдает от роста визуального беспорядка, так как число узлов по уровням может расти экспоненциально. Для простого бинарного дерева максимальное число узлов на уровне n равно 2n, а для бо́льших деревьев число узлов растёт быстрее. Представление дерева как диаграммы связи узлов тогда требует экспоненциональное пространство для рисунка.
Один из подходов — использование гиперболического дерева, впервые предложенного Ламперингом, Рао и ПироллиШаблон:Sfn. Гиперболические деревья используют гиперболическое пространство, которое от природы имеет «больше пространства», чем евклидово пространство. Например, линейное увеличение радиуса окружности в евклидовом пространстве увеличивает его длину окружности линейно, в то время как длина той же окружности в гиперболическом пространстве будет расти экспоненциально. Использование этого свойства позволяет расположить дерево в гиперболическом пространстве в лаконичной манере — размещение узла достаточно далеко от его родителя даёт узлу почти то же количество пространства для расположения собственных детей, что и у его родителя.
Рисование гиперболического дерева обычно использует дисковую модель Пуанкаре гиперболической геометрии, хотя может быть использована также модель Кляйна — Белтрами. Обе модели располагают всю гиперболическую плоскость в единичном диске, что делает дерево видимым всё сразу. Единичный диск даёт образ плоскости как в линзе «рыбий глаз», выделяя узлы, находящиеся в фокусе, и показывая узлы вне фокуса ближе к краю диска. Обход гиперболического дерева требует преобразования Мёбиуса пространства, которые переносят новые узлы в фокус и переносят более высокие уровни иерархии из поля зрения.
Гиперболические деревья были запатентованы в США компанией XeroxШаблон:R.
См. также
- Геометрия Лобачевского
- Шаблон:Не переведено 5
- Визуализация информации
- Радиальное дерево — is also circular, but uses linear geometry.
- Дерево (структура данных)
- Дерево (теория графов)
Примечания
Литература
Ссылки
- 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.
