Hyperbolic tree (original) (raw)
Árvore hiperbólica (em inglês: hyperbolic tree) é uma técnica foco+contexto baseada na geometria hiperbólica, usada na visualização de dados de grandes estruturas hierárquicas, como websites. O termo foi introduzido por Lamping et al em 1995.
| Property | Value |
|---|---|
| dbo:abstract | A hyperbolic tree (often shortened as hypertree) is an information visualization and graph drawing method inspired by hyperbolic geometry. Displaying hierarchical data as a tree suffers from visual clutter as the number of nodes per level can grow exponentially. For a simple binary tree, the maximum number of nodes at a level n is 2n, while the number of nodes for trees with more branching grows much more quickly. Drawing the tree as a node-link diagram thus requires exponential amounts of space to be displayed. One approach is to use a hyperbolic tree, first introduced by Lamping et al. Hyperbolic trees employ hyperbolic space, which intrinsically has "more room" than Euclidean space. For instance, linearly increasing the radius of a circle in Euclidean space increases its circumference linearly, while the same circle in hyperbolic space would have its circumference increase exponentially. Exploiting this property allows laying out the tree in hyperbolic space in an uncluttered manner: placing a node far enough from its parent gives the node almost the same amount of space as its parent for laying out its own children. Displaying a hyperbolic tree commonly utilizes the Poincaré disk model of hyperbolic geometry, though the Klein-Beltrami model can also be used. Both display the entire hyperbolic plane within a unit disk, making the entire tree visible at once. The unit disk gives a fish-eye lens view of the plane, giving more emphasis to nodes which are in focus and displaying nodes further out of focus closer to the boundary of the disk. Traversing the hyperbolic tree requires Möbius transformations of the space, bringing new nodes into focus and moving higher levels of the hierarchy out of view. Hyperbolic trees were patented in the U.S. by Xerox in 1996, but the patent has since expired. (en) Árvore hiperbólica (em inglês: hyperbolic tree) é uma técnica foco+contexto baseada na geometria hiperbólica, usada na visualização de dados de grandes estruturas hierárquicas, como websites. O termo foi introduzido por Lamping et al em 1995. (pt) 双曲树（英語：hyperbolic tree）是一种信息可视化和图形绘制方法，其灵感来自双曲几何。 将分层数据显示为一棵树，由于每层的节点数量会呈指数级增长，因此会出现视觉上的混乱。对于一棵简单的二叉树来说，第 n 层的最大节点数是 2n，而分支较多的树的节点数增长得更快。因此，把树画成一个节点-链接图需要指数级的空间来显示。 解决上述问题的其中一种方法是使用双曲树，首先由Lamping等人提出。 双曲树采用双曲空间，其本质上比欧氏空间的“空间更大”。例如，在欧几里得空间中线性增加一个圆的半径，其周长会线性增加，而在双曲空间中同样的圆，其周长会呈指数级增加。利用这一特性，可以在双曲空间中以整洁的方式给树布局：把一个节点放在离其父节点足够远的地方，可以让该节点几乎拥有与其父节点相同的空间来布局自己的子节点。 通常利用双曲几何的庞加莱圆盘模型来展示双曲树，尽管也可以使用凯莱-克莱因模型。两者都是在一个单位圆盘中显示整个双曲平面，使整个树一次性可见。单位圆盘提供了一个平面的鱼眼透镜视图，更加强调焦点内的节点，而在靠近圆盘边界处可以显示更加远离焦点的节点。遍历双曲树需要对空间进行莫比乌斯变换，使新的节点成为焦点，并将层次结构的更高层次移出视野。 双曲树于1996年由施乐公司在美国申请了专利，但该专利已经过期。 (zh) Гиперболическое дерево (часто сокращается до гипердерево) — это метод визуализации информации и графов на основе геометрии Лобачевского. Представление иерархических данных в виде дерева страдает от роста визуального беспорядка, так как число узлов по уровням может расти экспоненциально. Для простого бинарного дерева максимальное число узлов на уровне n равно 2n, а для бо́льших деревьев число узлов растёт быстрее. Представление дерева как диаграммы связи узлов тогда требует экспоненциональное пространство для рисунка. Один из подходов — использование гиперболического дерева, впервые предложенного Ламперингом, Рао и Пиролли. Гиперболические деревья используют гиперболическое пространство, которое от природы имеет «больше пространства», чем евклидово пространство. Например, линейное увеличение радиуса окружности в евклидовом пространстве увеличивает его длину окружности линейно, в то время как длина той же окружности в гиперболическом пространстве будет расти экспоненциально. Использование этого свойства позволяет расположить дерево в гиперболическом пространстве в лаконичной манере — размещение узла достаточно далеко от его родителя даёт узлу почти то же количество пространства для расположения собственных детей, что и у его родителя. Рисование гиперболического дерева обычно использует дисковую модель Пуанкаре гиперболической геометрии, хотя может быть использована также модель Кляйна — Белтрами. Обе модели располагают всю гиперболическую плоскость в единичном диске, что делает дерево видимым всё сразу. Единичный диск даёт образ плоскости как в линзе «рыбий глаз», выделяя узлы, находящиеся в фокусе, и показывая узлы вне фокуса ближе к краю диска. Обход гиперболического дерева требует преобразования Мёбиуса пространства, которые переносят новые узлы в фокус и переносят более высокие уровни иерархии из поля зрения. Гиперболические деревья были запатентованы в США компанией Xerox. (ru) Гіперболі́чне де́рево (гіпердерево) — це метод графічного представлення інформації, що використовується для візуалізації великих ієрархій. Даний метод базується на принципах гіперболічної геометрії і часто використовується у вебдодатках. При відображенні ієрархічних даних у вигляді дерев, часто виникає так званий візуальний безлад, оскільки кількість вузлів на кожному наступному рівні може зростати в геометричній прогресії. Саме тому, для великих ієрархій, використовуються гіперболічні дерева, як метод візуалізації інформації. Один з підходів використання гіперболічного дерева вперше запропонували Джон Лемпінг, Рамана Рао та Пітер Піроллі. У своїй праці вони визначали, що гіперболічні дерева використовують гіперболічний простір, який має значно більше місця, ніж Евклідів простір. Тобто, лінійне збільшення радіуса кола в Евклідовому просторі розширює його межі лінійно, в той час, як в гіперболічному просторі межі розширюються в геометричній прогресії, що дозволяє організовувати дерева в гіперболічному просторі більш лаконічно. Для зображення гіперболічних дерев зазвичай використовують модель Пуанкаре, або модель Клейна. Обидві моделі дають змогу відобразити всю гіперболічну площину на одному диску, таким чином, що ціле гіперболічне дерево зі всіма зв'язками можна побачити відразу. У центрі диску відображається центральна точка ієрархії. Далі від неї розташовані інші вузли, при цьому, чим далі вони знаходяться від центральної точки (ближче до кордонів диска), ти менше вони помітні. Для зміщення фокусу використовується перетворення Мебіуса, тобто, при зміні точки, що знаходиться в центрі уваги, дотичні до неї вузли переміщуються до центру диска, а інші, відходять на тло, ближче до краю диска. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/BasicTree.png?width=300 |
| dbo:wikiPageExternalLink | https://hyperbolic-tree-of-life.github.io/ http://www.roguetemple.com/z/hyper/rogueviz.php https://github.com/glouwa/d3-hypertree https://web.archive.org/web/20121109143915/http:/ocsigen.org/js_of_ocaml/files/hyperbolic/index.html http://ucjeps.berkeley.edu/map2.html |
| dbo:wikiPageID | 5566181 (xsd:integer) |
| dbo:wikiPageLength | 4351 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1114730719 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Information_visualization dbr:Radial_tree dbr:Möbius_transformation dbr:Tree_(data_structure) dbr:Tree_(graph_theory) dbc:Graph_drawing dbc:Hyperbolic_geometry dbr:Graph_drawing dbr:Hyperbolic_geometry dbc:Trees_(data_structures) dbr:Binary_tiling dbr:Tree_of_life dbr:Poincaré_disk_model dbr:Klein_model dbr:Visualization_(graphic) dbr:File:BasicTree.png dbr:File:BasicTreeFocused.png |
| dbp:wikiPageUsesTemplate | dbt:Commons_category dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Graph_drawing dbc:Hyperbolic_geometry dbc:Trees_(data_structures) |
| gold:hypernym | dbr:Visualization |
| rdf:type | dbo:Software |
| rdfs:comment | Árvore hiperbólica (em inglês: hyperbolic tree) é uma técnica foco+contexto baseada na geometria hiperbólica, usada na visualização de dados de grandes estruturas hierárquicas, como websites. O termo foi introduzido por Lamping et al em 1995. (pt) 双曲树（英語：hyperbolic tree）是一种信息可视化和图形绘制方法，其灵感来自双曲几何。 将分层数据显示为一棵树，由于每层的节点数量会呈指数级增长，因此会出现视觉上的混乱。对于一棵简单的二叉树来说，第 n 层的最大节点数是 2n，而分支较多的树的节点数增长得更快。因此，把树画成一个节点-链接图需要指数级的空间来显示。 解决上述问题的其中一种方法是使用双曲树，首先由Lamping等人提出。 双曲树采用双曲空间，其本质上比欧氏空间的“空间更大”。例如，在欧几里得空间中线性增加一个圆的半径，其周长会线性增加，而在双曲空间中同样的圆，其周长会呈指数级增加。利用这一特性，可以在双曲空间中以整洁的方式给树布局：把一个节点放在离其父节点足够远的地方，可以让该节点几乎拥有与其父节点相同的空间来布局自己的子节点。 通常利用双曲几何的庞加莱圆盘模型来展示双曲树，尽管也可以使用凯莱-克莱因模型。两者都是在一个单位圆盘中显示整个双曲平面，使整个树一次性可见。单位圆盘提供了一个平面的鱼眼透镜视图，更加强调焦点内的节点，而在靠近圆盘边界处可以显示更加远离焦点的节点。遍历双曲树需要对空间进行莫比乌斯变换，使新的节点成为焦点，并将层次结构的更高层次移出视野。 双曲树于1996年由施乐公司在美国申请了专利，但该专利已经过期。 (zh) A hyperbolic tree (often shortened as hypertree) is an information visualization and graph drawing method inspired by hyperbolic geometry. Displaying hierarchical data as a tree suffers from visual clutter as the number of nodes per level can grow exponentially. For a simple binary tree, the maximum number of nodes at a level n is 2n, while the number of nodes for trees with more branching grows much more quickly. Drawing the tree as a node-link diagram thus requires exponential amounts of space to be displayed. (en) Гиперболическое дерево (часто сокращается до гипердерево) — это метод визуализации информации и графов на основе геометрии Лобачевского. Представление иерархических данных в виде дерева страдает от роста визуального беспорядка, так как число узлов по уровням может расти экспоненциально. Для простого бинарного дерева максимальное число узлов на уровне n равно 2n, а для бо́льших деревьев число узлов растёт быстрее. Представление дерева как диаграммы связи узлов тогда требует экспоненциональное пространство для рисунка. Гиперболические деревья были запатентованы в США компанией Xerox. (ru) Гіперболі́чне де́рево (гіпердерево) — це метод графічного представлення інформації, що використовується для візуалізації великих ієрархій. Даний метод базується на принципах гіперболічної геометрії і часто використовується у вебдодатках. При відображенні ієрархічних даних у вигляді дерев, часто виникає так званий візуальний безлад, оскільки кількість вузлів на кожному наступному рівні може зростати в геометричній прогресії. Саме тому, для великих ієрархій, використовуються гіперболічні дерева, як метод візуалізації інформації. (uk) |
| rdfs:label | Hyperbolic tree (en) Árvore hiperbólica (pt) Гиперболическое дерево (ru) Гіперболічне дерево (uk) 双曲树 (zh) |
| owl:sameAs | freebase:Hyperbolic tree wikidata:Hyperbolic tree dbpedia-pt:Hyperbolic tree dbpedia-ru:Hyperbolic tree dbpedia-uk:Hyperbolic tree dbpedia-zh:Hyperbolic tree https://global.dbpedia.org/id/4m9wz |
| prov:wasDerivedFrom | wikipedia-en:Hyperbolic_tree?oldid=1114730719&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/BasicTree.png wiki-commons:Special:FilePath/BasicTreeFocused.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Hyperbolic_tree |
| is dbo:wikiPageRedirects of | dbr:Hyperbolic_Tree dbr:HyperbolicTree |
| is dbo:wikiPageWikiLink of | dbr:Radial_tree dbr:Simple_Knowledge_Organization_System dbr:Tree_of_life_(biology) dbr:JavaScript_InfoVis_Toolkit dbr:Hyperbolic_geometry dbr:Binary_tiling dbr:Hyperbolic_Tree dbr:Hypertree_(disambiguation) dbr:SpicyNodes dbr:HyperbolicTree |
| is foaf:primaryTopic of | wikipedia-en:Hyperbolic_tree |
