[HN Gopher] Algorithm to Draw a Tree ___________________________________________________________________ Algorithm to Draw a Tree Author : mfbx9da4 Score : 37 points Date : 2020-01-18 20:50 UTC (2 hours ago) (HTM) web link (rachel53461.wordpress.com) (TXT) w3m dump (rachel53461.wordpress.com) | tunesmith wrote: | There are the various graph layout algorithms I've heard of, | Sugiyama, KIELER, ELK - these can be used for trees of course, | although I'm not sure they have highly constrained vertical | levels like the article depicts. | winrid wrote: | Sebastian Lague did a video that includes some tree generation | that was fun to watch | | EDIT wrong kind of tree :D | | https://youtu.be/--GB9qyZJqg | sprt wrote: | This is interesting, I was asked this question in an interview | for a Microsoft internship, but for a binary tree. | tejtm wrote: | Was thinking was going to get some nice L-system eye candy [0] | https://en.wikipedia.org/wiki/L-system | michaeltoth wrote: | I was expecting a generative art algorithm for drawing trees | virtuous_signal wrote: | So the author mentions hearing about the Reingold-Tilford | Algorithm which wouldn't work for the example given since R-T is | meant for binary trees and a family tree might have more than 2 | nodes. | | Which led me to wonder why is there even an "algorithm" per se | for binary trees: wouldn't it be acceptable to just trace out a | complete binary tree with spaces reserved for each potential | node, and only fill in a space with a node if it is non-null? Or | does this not meet some criterion of "niceness" for drawings? | captncraig wrote: | If you do that, you quickly run into the feasible depth limit | for what you can show in a fixed space. Especially for sparse | trees. Consider something like family trees, where you | generally don't know anything about certain lines, but may have | 20 generations or more on selected lines. No way could you show | 2^20 nodes in a fixed format rendering, but you can make | something kinda pretty by eliminating the empty space and | organizing things to fill it intelligently. | taywrobel wrote: | I was _just_ writing a radial RT-like visualization for | displaying the branching structure of a binary tree and ran | into the issue of information density you describe. Still | pretty happy with the results, tho, in how it shows the | structure and clustering. | | And I colored it like a tree, just for fun - | https://giphy.com/gifs/TKFUkrWQtil60Ij2YJ/html5 ___________________________________________________________________ (page generated 2020-01-18 23:00 UTC)