# pouët.net

## trees

category: code [glöplog]
anyone know a good algorithm to draw trees? not the nature kind, the graph kind.
added on the 2012-02-20 21:01:19 by sigflup
http://paulbourke.net/fractals/ifs_tree_b/
what about "not the nature kind" wasn't clear maali :)
added on the 2012-02-20 22:13:35 by superplek
if you spots IFS trees in nature, please gimme a call!
IFS often if not always uses chaos/random. What he wants is most probably (something like) this:

Which should be easy enough. Anyway, curb your attitude :)
added on the 2012-02-20 23:19:54 by superplek
b-trees!
Align depth along one axis, width along another. Boom, you have drawn a tree-structure.
added on the 2012-02-20 23:40:58 by kusma
I was thinking the depth would shove over other nodes of the same parent
added on the 2012-02-20 23:45:11 by sigflup
A graph can be formally defined as a set of nodes. linking with a set of edges:

G = {N, E}

theres many graph-types too choose from, for whatever purpose those graph may have.

see graph listing here: http://en.wikipedia.org/wiki/Graph_%28mathematics%29
added on the 2012-02-20 23:50:39 by rudi
first make a graphnode-baseclass with index to the node which you can build from. then make a graphedge-class with offsets connections too and from the nodes, and a cost-variable (or calculate cost on the fly your platform is slow). then building a sparse graph-class and you're set to go experimenting with the different graph-types.
added on the 2012-02-20 23:59:25 by rudi
sigflup: i just remember some time ago you where in hospital. how are you now?
added on the 2012-02-21 00:03:27 by rudi
I'm well, I was in there for about a month over two stays. medication helps a lot. they said I'm schizoaffective and I am learning what this means to other people. I'll take a look at the links when I get home (on the bus)
added on the 2012-02-21 00:39:06 by sigflup
Quote:
if you spots IFS trees in nature, please gimme a call!
added on the 2012-02-21 09:10:15 by skrebbel
oh absolutely, after all he was wrong, and then wrong again

for self-similarity in nature, go and buy a fucking romanesco broccoli.
added on the 2012-02-21 12:06:21 by superplek
You can use particle linked with springs, with 1/r^2 repulsing force between particles. It's simple but will make nice trees. Works also for graphs. You might look for further inspiration here http://www.graphviz.org/
plek, damn you!
added on the 2012-02-21 12:20:07 by skrebbel
in my defense, it was early in the morning.
added on the 2012-02-21 12:20:23 by skrebbel
added on the 2012-02-21 12:34:05 by aegis
marmakoide, that sounds correct. A slight weight downward as well
added on the 2012-02-21 12:35:24 by sigflup
Yes, you have to throw some additional tricks to make it work. A downward force, yes. Also some small viscosity force (f = -kv, v being the velocity, k something close to 0) will help to dampen eventual oddities, like 2 particles coming very close. You also use springs across internal node to shape the tree to your convenience. It's rather flexible and tinkering-friendly.

For the particle motions, I recommend verlet integrator, it's cheap, unconditionally stable, we don't care much about accuracy and you get the viscosity force for free.
I like kusma's approach better to be honest, i.e. find the "widest" level or "widest" sibling group and then align accordingly.
added on the 2012-02-21 14:00:00 by Gargaj
If you ever need to store treestructure, consider implementing "nested set model"

I'm not sure how relevant to this discussion it is, but I've found it highly useful (and vastly time-saving) whenever I've had the chance to implement it. Not sure it applies directly to your need, though.
added on the 2012-02-21 14:31:21 by Punqtured
punqtured: that is nice!
i'd also use kusma's method. i usually do :)
added on the 2012-02-21 15:52:22 by superplek
Ok, I walked the tree downward and stored where the nodes are, for each parent I walk up parents shoving over the size that children take up.
added on the 2012-02-22 22:28:32 by sigflup
For quickly toying around I can also recommend GUESS Graph Exploration System.
added on the 2012-02-22 23:02:00 by noname