c++ - 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: