径向树布局算法

Question

我已经实现了一个树数据结构,其中每个节点都保存(recursivly)一个指向它的子节点的指针列表.

我正在尝试计算用于可视化树的(x,y)坐标.我浏览了这篇文章:

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

剪切我无法弄清楚如何超越第一级,即这是我到目前为止所写的:

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)..//  
        }
    }
}

我不知道如何计算限制,平分等.这是我的抽屉到目前为止所做的:

从第二个(0基础)水平以来,这显然不是我正在寻找的.

我可以访问我需要的所有信息,以获得我正在寻找的东西.

Answer 1

可能现在你自己想出来了.如果没有,在这里

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

你在第二级将角度空间设置为PI(180度),因为在那个级别只有两个节点,dNodesInDepth = 2.这就是为什么在绘制节点20之后,节点30离开180度.对于非常密集的树木,这种方法很好,因为这个角度很小.但在您的情况下,您希望保持角度尽可能接近父级的角度.因此,我建议你获得2级及更高级别节点的父级角度,并传播子级,使它们的角度空间为sibilingAngle = min(dAngleSpace, PI/10).因此,第一个孩子将具有父母的确切角度,其余孩子彼此sibilingAngle远离.你明白了,可能会有更好的方法.我正在使用min,以防你在那个级别有太多节点,你想挤压节点彼此更近.

您链接到的文章使用了图示的解决方案Figure 2 – Tangent and bisector limits for directories.我不太喜欢这种方法,因为如果你确定孩子的绝对角度而不是相对于父亲的角度,你可以有一个更简单/更清晰的解决方案,它完全符合该方法试图对这么多操作做的事情.

更新:

以下代码生成此图像:

我想你可以很容易地弄清楚如何将子节点等中心化.

#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;
}

更新2: 为了让您更轻松,以下是如何使节点居中:

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;

显示更加人口稠密的树: