Antimatroid, The

thoughts on computer science, electronics, mathematics

Tree Drawing: The radial tree

leave a comment »

Although not as interesting as a sunburst diagram, the radial tree view can hold its color against a number of more primitive information visualizations. A radial tree view places the root at the center of the screen then fans out each child node. Each child node then fans out its children within a restricted span and continues on until each leaf is reached. The strengths of the technique allow for any easy to digest depiction of the structure behind the data in a compact space. A common application is visualizing computer networks. It is worthwhile to examine the algorithm behind the technique because it is an exercise in identifying simplicity.

While in college, I would have approached this problem by trying to identify the location of nodes in terms of (r, \theta) after all, I want a radial tree view- makes sense to sprint out the gate with a polar system right? While possible, this is a bad path to head down, as you end up drowning in a sea of extraneous details. Rather, it is better to think in terms of (x,y) and then map to (r, \theta). To clarify that position, let’s think about how we’d go about drawing the run of the mill tree view as in the figure below:

radialtree_normal

First some observations:

  • Every node at a given depth lies on the same line.
  • Every child at a given depth is given an equal share of horizontal space independent of necessity relative to the space owned by its parent.

We can construct a simple recursive definition for drawing the tree if we think about these two facts. Given a node, we want to center the node at the top of a region then carve up a region into the number of child nodes where each sub region is equally wide and the same height as the parent minus a layering distance, then draw a line from the parent node to the child node. Continue doing so until all of the nodes have been drawn. All that remains is mapping this tree to the radial tree view below:

radialtree1

To achieve this last step, we want to map each node at (x,y) to a point \hat{C} + r \cdot(cos(\theta), sin(\theta)) Where \hat{C} is the center of the display area. The radius is simply the node’s present y coordinate. \theta can be determined as the ratio between the node’s present x coordinate and the display width times 2 \pi. And thus, the mapping is complete.

Advertisements

Written by lewellen

2008-08-31 at 6:05 pm

Posted in Computer Graphics

Tagged with

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: