Hyperbolický strom - Hyperbolic tree

Hyperbolický strom (často se zkrátil jako hypertree ) je informace o vizualizaci a graf výkresu metoda inspirovaný hyperbolické geometrii .

Základní hyperbolický strom. Uzly v ohnisku jsou umístěny ve středu a mají větší prostor, zatímco uzly mimo ohnisko jsou komprimovány poblíž hranic.

Zaměření na jiný uzel jej přivede a jeho podřízené do středu disku, zatímco nezajímavé části stromu jsou komprimovány.

Zobrazení hierarchických dat jako stromu trpí vizuálním nepořádkem, protože počet uzlů na úrovni může exponenciálně růst. U jednoduchého binárního stromu je maximální počet uzlů na úrovni n 2 ⁿ , zatímco počet uzlů u stromů s větším větvením roste mnohem rychleji. Kreslení stromu jako diagramu uzel-spoj vyžaduje tedy exponenciální množství prostoru, který má být zobrazen.

Jedním z přístupů je použití hyperbolického stromu , který poprvé představili Lamping et al. Hyperbolické stromy využívají hyperbolický prostor , který má ve své podstatě „více prostoru“ než euklidovský prostor. Například lineární zvětšení poloměru kruhu v euklidovském prostoru lineárně zvětší jeho obvod, zatímco stejný kruh v hyperbolickém prostoru by měl jeho obvod exponenciálně zvětšit. Využití této vlastnosti umožňuje rozložení stromu v hyperbolickém prostoru přehledným způsobem: umístění uzlu dostatečně daleko od jeho rodiče dává uzlu téměř stejné množství prostoru jako jeho rodič pro rozložení jeho vlastních podřízených.

Zobrazení hyperbolického stromu běžně využívá Poincarého diskový model hyperbolické geometrie, ačkoli lze použít i Klein-Beltramiho model. Oba zobrazují celou hyperbolickou rovinu na jednotkovém disku, takže je celý strom viditelný najednou. Jednotkový disk poskytuje pohled na rovinu rybího oka, přičemž klade větší důraz na uzly, které jsou zaostřeny, a zobrazuje uzly dále od zaostření blíže k hranici disku. Procházení hyperbolického stromu vyžaduje Möbiove transformace prostoru, uvedení nových uzlů do ohniska a přesunutí vyšších úrovní hierarchie z dohledu.

Hyperbolické stromy byly patentovány v USA společností Xerox v roce 1996, ale patent mezitím vypršel.

Viz také

• Hyperbolická geometrie
• Binární obklady
• Informační vizualizace
• Radiální strom - je také kruhový, ale používá lineární geometrii.
• Strom (datová struktura)
• Strom (teorie grafů)

Reference

externí odkazy

• d3-hypertree - implementace hyperbolického stromu HTML5, licence MIT
• Hyperbolický strom života - vizualizace stromu života s otevřeným zdrojovým kódem pomocí datové sady Open Tree of Life
• Zelený strom života - Strom života - Kalifornská univerzita v Berkeley a Jepson Herbaria
• Strom života Podobně jako výše, ale s obrázky
• RougeViz podporuje hyperbolické stromy.