Long Story Short
I was searching for an algorithm for hierarchy node-link diagram, learned about other was to display the same data, choose the 'Sunburst' diagram as my new primary choice, and never found a hint or clue of algorithmic code for it. This is what it looks like (without words):
To The CODE!
So, first I create an object that would store the drawing data:
public class TreeNodeEx : TreeNode
{
public float Radius { get; set; }
public float Scale { get; set; }
public float StartAngle { get; set; }
public float SweepAngle { get; set; }
public TreeNodeEx(String text)
: base(text)
{
Radius = 0;
Scale = StartAngle = SweepAngle = 0;
}
}
Next, the actual sunburst generator!
// This is the entry point of the sunburst algorithm
private void GenerateStructures(TreeNodeEx rTNH)
{
rTNH.Radius = 1;
rTNH.SweepAngle = 360;
tree_depth = Round1(rTNH);
Round2(rTNH);
}
private int Round1(TreeNodeEx rootx)
{
// traverse to the bottom while setting depth and breadth
TreeNodeEx current;
if(rootx == null) return 0;
current = (TreeNodeEx)rootx.Nodes[0];
bool next_flag = false;
int depth = 2, max = 0;
while (current.Parent != null) // have we reached the root yet
{
if(current.Nodes.Count == 0 || next_flag)
{
if(!next_flag) current.Scale = 1; // count it's self
((TreeNodeEx)current.Parent).Scale += current.Scale;
next_flag = false; // reset
current.Radius = depth;
int idx = current.Parent.Nodes.IndexOf(current);
idx++; // get next sibling in line
if (current.Parent.Nodes.Count == idx)
{
// move to next parant
next_flag = true;
current = (TreeNodeEx)current.Parent;
current.Scale++; // count parent
depth--;
}
else
{
current = (TreeNodeEx)current.Parent.Nodes[idx];
}
}
else
{
// traverse to the bottom of the tree
current = (TreeNodeEx)current.Nodes[0];
depth++;
max = Math.Max(max, depth);
}
}
return max; // return max depth - used for precise rendering
}
private void Round2(TreeNodeEx rootx)
{
// traverse to the bottom while setting depth and breadth
TreeNodeEx current;
if (rootx == null) return;
current = (TreeNodeEx)rootx.Nodes[0];
bool next_flag = false;
while (current.Parent != null) // have we reached the root yet
{
if (current.Nodes.Count == 0 || next_flag)
{
if (current.PrevNode != null)
{
current.StartAngle =
((TreeNodeEx)current.PrevNode).StartAngle +
((TreeNodeEx)current.PrevNode).SweepAngle;
current.SweepAngle =
(current.Scale /
(((TreeNodeEx)current.Parent).Scale - 1F)) *
((TreeNodeEx)current.Parent).SweepAngle;
}
else
{
current.StartAngle =
((TreeNodeEx)current.Parent).StartAngle;
current.SweepAngle =
(current.Scale /
(((TreeNodeEx)current.Parent).Scale - 1F)) *
((TreeNodeEx)current.Parent).SweepAngle;
}
next_flag = false; // reset
int idx = current.Parent.Nodes.IndexOf(current);
idx++; // get next sibling in line
if (current.Parent.Nodes.Count == idx)
{
// move to next parant
next_flag = true;
current = (TreeNodeEx)current.Parent;
}
else
{
current = (TreeNodeEx)current.Parent.Nodes[idx];
}
}
else
{
if (current.PrevNode != null)
{
current.StartAngle =
((TreeNodeEx)current.PrevNode).StartAngle +
((TreeNodeEx)current.PrevNode).SweepAngle;
current.SweepAngle =
(current.Scale /
(((TreeNodeEx)current.Parent).Scale - 1F)) *
((TreeNodeEx)current.Parent).SweepAngle;
}
else
{
current.StartAngle =
((TreeNodeEx)current.Parent).StartAngle;
current.SweepAngle =
(current.Scale /
(((TreeNodeEx)current.Parent).Scale-1F)) *
((TreeNodeEx)current.Parent).SweepAngle;
}
// traverse to the bottom of the tree
current = (TreeNodeEx)current.Nodes[0];
}
}
}
I didn't include the drawing code portion because this is just an algorithmic post and not an application post. After all, shapes can be presented, colored, or drawn in many ways with many graphics libraries... and also I feel mine may be a little bit messy or too complex for such a simple task here. However, if you'd like to see how I did it, please leave a comment and I'll try to get back to you!
EDIT: Rewrote the above code without recursion as sometimes trees can grow very deep and there is only a limited amount of stack space available on a machine. Also made a few bug fixes along the way such as the 'overlapping rendering' - a result of a logic error in the variable generation. The above code can still be further improved, but compared to the previous this is an improvement!
Here Are MY Results:
I did it all in WinForms using custom control designs.
No comments:
Post a Comment