Sign in to follow this  
bpoint

rendering a tree (not the plant kind :) )

Recommended Posts

bpoint    464
Hello all, I've been stuck on this problem for about two weeks now, and have tried various things to make it work, but none of them are ideal... How can I present a tree, where each node can have multiple inputs and outputs, visually to a user, such that any given node will have a unique position in 2D space and never overlap another node? The logic for the tree is implemented and works fine, but I want to be able to display this to the user to give visual feedback on how nodes are linked. I can already determine the 2D size of node (a box is fine), and this size can be used for all nodes, so that should make rendering of the tree easier. I've tried using a bounding box to ensure nodes don't overlap, but this introduces problems when trying to place children nodes. For example (warning: ASCII art follows, the '*' marks denote the bounding box vertices):
*       *
 +-+
 |A|
 +-+
  |
 +-+ +-+
 |B|-|C|
 +-+ +-+
*       *
Then if I add a child to B, this works fine:
*       *
 +-+
 |A|
 +-+
  |
 +-+ +-+
 |B|-|C|
 +-+ +-+
  |
 +-+
 |D|
 +-+
*       *
But when I add another child to B, it shifts E too far to the right because of the bounding box (ideally it would be positioned next to D, assuming D didn't have any siblings):
*           *
 +-+
 |A|
 +-+
  |
 +-+ +-+
 |B|-|C|
 +-+ +-+
  | \___
 +-+    \+-+
 |D|     |E|
 +-+     +-+
*           *
So I'm guessing a bounding box isn't the proper way to do this. :( I've tried searching Google, but I'm not really sure what to search for, seeing as how "rendering a tree" turns up nothing of what I'm interested in. Are there any algorithms which describe how to do something like this? Any help would be greatly appreciated!

Share this post


Link to post
Share on other sites
kvp    196
As long as it's a tree and not a graph, you can display it in the same format used by directory trees. That is, each level has a horizontal position and children appear below their parent.

-main
--child1
---childa_of_child1
---childb_of_child1
--child2
---childa_of_child2

and so on...

Share this post


Link to post
Share on other sites
Excors    715
Does Graphviz do what you want? If so, the easiest approach is to generate a .dot file (which just defines the nodes and edges in a text-based format) and then run Graphviz to generate the image for you, since they've already done the hard work.

Share this post


Link to post
Share on other sites
bpoint    464
ajones: Thanks! That's a rough idea of what I need, so I'll start to research it a bit.

kvp: Sorry, I probably shouldn't have used the word "tree", because it can't be visually described like that. Each node can have multiple inputs (parents) and multiple outputs (children), as well as siblings. However, the nodes are guaranteed to not be recursive upon each other. So a simple tree-view won't cut it here.

Excors: Yes! Now that's more of what I was looking for. The first image on left in the header at the top of the page is perfect. Unfortunately (for me), my application is written in Flash ActionScript, so I'll have to poke through Graphviz's source code for dot and see how they do it...

Thanks for the suggestions! I'm still open to any other ideas should anyone else have any. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this