Radial Tree layout algorithm

Question

I have implemented a tree data structure in which every node holds (recursivly) a list of pointers to it's children.

I am trying to calculate the (x,y) coordinates for visualizing the tree. I went through this article:

http://gbook.org/projects/RadialTreeGraph.pdf

Cut I can't figure out how to gest past the first level, i.e This is what I have written so far:

for (int i = 0; i < GetDepth()+1; i++)
{
    if (i == 0)
    {
        GetNodesInDepth(i).at(0)->SetXRadial(MIDDLE(m_nWidth));
        GetNodesInDepth(i).at(0)->SetYRadial(MIDDLE(m_nHeight));
        continue;
    }

    double dNodesInDepth = GetNodesInDepth(i).size();
    double dAngleSpace = 2 * PI / dNodesInDepth;

    for (int j = 0; j < dNodesInDepth; j++)
    {
        Node * pCurrentNode = GetNodesInDepth(i).at(j);

        pCurrentNode->SetXRadial((SPACING * i) * qCos(j * dAngleSpace) + MIDDLE(m_nWidth));
        pCurrentNode->SetYRadial((SPACING * i) * qSin(j * dAngleSpace) + MIDDLE(m_nHeight));
        pCurrentNode->m_dAngle = dAngleSpace * j;

        if (pCurrentNode->IsParent())
        {
         //..(I'm stuck here)..//  
        }
    }
}

I am not sure how to calculate the limits, bisectors etc. this is what my drawer did so far:

which is obviously not what i'm looking for since the second (0 based) level.

I have access to every info that I need in order to obtain what I'm looking for.

Answer 1

Probably by now you figured it out yourself. If not, here

double dNodesInDepth = GetNodesInDepth(i).size();
double dAngleSpace = 2 * PI / dNodesInDepth;

you're setting the angle space to PI (180 degreees) at your second level, as there are only two nodes at that level, dNodesInDepth = 2. That's why after drawing the node 20, the node 30 is 180 degrees away. That method would be fine for very dense trees because that angle will be small. But in your case you want to keep the angle as close as possible to the angle of the parent. So I suggest you get the angle of the parent for nodes at level 2 and higher, and spread the children so they have an angle space of sibilingAngle = min(dAngleSpace, PI/10). So the first child will have the exact angle of the parent, and the remaining children are sibilingAngle away from one another. You get the idea and probably come with a better method. I'm using min in case you have got too many nodes at that level you want to squeeze the nodes closer to each other.

The article you've linked to, uses a solution that is illustrated in Figure 2 – Tangent and bisector limits for directories. I don't like that method much because if you determine the absolute angle of the children rather than relative to the parent you can have a simpler/cleaner solution that does exactly what that method tries to do with so many operations.

Update:

The following code produces this image:

I think you can easily figure out how to center the child nodes and etc.

#include <cairo/cairo.h>
#include <math.h>
#include <vector>

using namespace std;

class Node {
public:
    Node() {
        parent = 0;
        angle = 0;
        angleRange = 2*M_PI;
        depth = 0;
    }
    void addChildren(int n) {
        for (int i=0; i<n; i++) {
            Node* c = new Node;
            c->parent = this;
            c->depth = depth+1;
            children.push_back(c);
        }
    }
    vector<Node*> children;
    float angle;
    float angleRange;
    Node* parent;
    int depth;
    int x, y;
};

void rotate(float x, float y, float angle, float& nx, float& ny) {
    nx = x * cos(angle) - y * sin(angle);
    ny = x * sin(angle) + y * cos(angle);
}
void draw(Node* root, cairo_t *cr) {
    if (root->parent == 0) {
        root->x = root->y = 300;
        cairo_arc(cr, root->x, root->y, 3, 0, 2 * M_PI);
    }

    int n = root->children.size();
    for (int i=0; i<root->children.size(); i++) {
        root->children[i]->angle = root->angle + root->angleRange/n * i;
        root->children[i]->angleRange = root->angleRange/n;

        float x, y;
        rotate(40 * root->children[i]->depth, 0, root->children[i]->angle, x, y);
        root->children[i]->x = 300+x;
        root->children[i]->y = 300+y;

        cairo_move_to(cr, root->x, root->y);
        cairo_line_to(cr, root->children[i]->x, root->children[i]->y);
        cairo_set_source_rgb(cr, 0, 0, 0);
        cairo_stroke(cr);

        cairo_arc(cr, 300+x, 300+y, 3, 0, 2 * M_PI);
        cairo_set_source_rgb(cr, 1, 1, 1);
        cairo_stroke_preserve(cr);
        cairo_set_source_rgb(cr, 0, 0, 0);
        cairo_fill(cr);

        draw(root->children[i], cr);
    }
}

int main(void) {
    Node root;
    root.addChildren(4);
    root.children[0]->addChildren(3);
    root.children[0]->children[0]->addChildren(2);
    root.children[1]->addChildren(5);
    root.children[2]->addChildren(5);
    root.children[2]->children[1]->addChildren(2);
    root.children[2]->children[1]->children[1]->addChildren(2);

    cairo_surface_t *surface;
    cairo_t *cr;

    surface = cairo_image_surface_create(CAIRO_FORMAT_ARGB32, 600, 600);
    cr = cairo_create(surface);

    cairo_rectangle(cr, 0.0, 0.0, 600, 600);
    cairo_set_source_rgb(cr, 1, 1, 1);
    cairo_fill(cr);

    cairo_set_line_width(cr, 2);

    for (int i=0; i<6; i++) {
        cairo_arc(cr, 300, 300, 40*i, 0, 2 * M_PI);
        cairo_set_source_rgb(cr, .5, .5, .5);
        cairo_stroke(cr);
    }

    draw(&root, cr);

    cairo_surface_write_to_png(surface, "image.png");

    cairo_destroy(cr);
    cairo_surface_destroy(surface);

    return 0;
}

Update 2: Just to make it easier for you, here is how to center the nodes:

for (int i=0; i<root->children.size(); i++) {
    float centerAdjust = 0;
    if (root->parent != 0) {
        centerAdjust = (-root->angleRange + root->angleRange / n) / 2;
    }
    root->children[i]->angle = root->angle + root->angleRange/n * i + centerAdjust;
    root->children[i]->angleRange = root->angleRange/n;

Showing a more populated tree:

Answer 2

Here is an implementation of the algorithm from the article that should work (note: I didn't compile it since I don't have other parts of your program):

void Tree::CalculateAngles()
{
    // IsEmpty() returns true if the tree is empty, false otherwise
    if (!IsEmpty())
    {
        Node* pRoot = GetNodesInDepth(0).at(0);
        pRoot->SetAngle(0);
        // Relative to the current angle
        pRoot->SetTangentLimit(PI);
        // Absolute limit
        pRoot->SetLowerBisector(-PI);
        pRoot->SetHigherBisector(PI);
    }
    for (int depth = 1; depth < GetDepth() + 1; depth++)
    {
        double dDepth = (double)depth;
        // The last non-leaf node in of the current depth (i.e. node with children)
        Node* pPreviousNonleafNode = NULL;
        // The first non-leaf node
        Node* pFirstNonleafNode = NULL;
        // The parent of the previous node
        Node* pPreviousParent = NULL;
        int indexInCurrentParent = 0;
        double dTangentLimt = acos( dDepth / (dDepth + 1.0) );
        for (int i = 0; i < GetNodesInDepth(depth).size(); i++)
        {
            Node* pCurrentNode = GetNodesInDepth(depth).at(i);
            Node* pParent = pCurrentNode->GetParent();
            if (pParent != pPreviousParent)
            {
                pPreviousParent = pParent;
                indexInCurrentParent = 0;
            }
            // (GetMaxChildAngle() - GetMinChildAngle()) / GetChildCount()
            double angleSpace = pParent->GetAngleSpace();
            pCurrentNode->SetAngle(angleSpace * (indexInCurrentParent + 0.5));
            pCurrentNode->SetTangentLimit(dTangentLimt);
            if (pCurrentNode->IsParent())
            {
                if (!pPreviousNonleafNode)
                {
                    pFirstNonleafNode = pCurrentNode;
                }
                else
                {
                    double dBisector = (pPreviousNonleafNode->GetAngle() + pCurrentNode->GetAngle()) / 2.0;
                    pPreviousNonleafNode->SetHigherBisector(dBisector);
                    pCurrentNode->SetLowerBisector(dBisector);
                }
                pPreviousNonleafNode = pCurrentNode;
            }
            indexInCurrentParent++;
        }
        if (pPreviousNonleafNode && pFirstNonleafNode)
        {
            if (pPreviousNonleafNode == pFirstNonleafNode)
            {
                double dAngle = pFirstNonleafNode->GetAngle();
                pFirstNonleafNode->SetLowerBisector(dAngle - PI);
                pFirstNonleafNode->SetHigherBisector(dAngle + PI);
            }
            else
            {
                double dBisector = PI + (pPreviousNonleafNode->GetAngle() + pFirstNonleafNode->GetAngle()) / 2.0;
                pFirstNonleafNode->SetLowerBisector(dBisector);
                pPreviousNonleafNode->SetHigherBisector(dBisector);
            }
        }
    }
}

void Tree::CalculatePositions()
{
    for (int depth = 0; depth < GetDepth() + 1; depth++)
    {
        double redius = SPACING * depth;
        for (int i = 0; i < GetNodesInDepth(depth).size(); i++)
        {
            Node* pCurrentNode = GetNodesInDepth(depth).at(i);
            double angle = pCurrentNode->GetAngle();
            pCurrentNode->SetXRadial(redius * qCos(angle) + MIDDLE(m_nWidth));
            pCurrentNode->SetYRadial(redius * qSin(angle) + MIDDLE(m_nHeight));
        }
    }
}

void Tree::CalculateLayout ()
{
    CalculateAngles();
    CalculatePositions();
}

double Node::GetAngleSpace()
{
    return (GetMaxChildAngle() - GetMinChildAngle()) / GetChildCount();
}

Note: I tried to mimic your code style so you won't have to refactor it to match other parts of your program.

P.S. If you spot any bugs, please notify me in the comments - I'll edit my answer.