径向树布局算法

Question

径向树布局算法

10

我已经实现了一种树形数据结构，其中每个节点（递归地）保存指向其子节点的指针列表。

我正在尝试计算可视化树的 (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开始）级别。我可以获取所有需要的信息以获得我想要的东西。

- wannabe programmer

2

所以（澄清一下）在你的图中，唯一错位的是30节点？ - o_weisman

1

你给的链接里面差不多有你想要实现的代码。虽然有点乱，但是它包含了在不同层级上计算限制和平分线的部分。你是不是对他们的代码有些困惑？ - o_weisman

我已经尝试过了，但它没有起作用。 - wannabe programmer

你正在使用系统匈牙利命名法。许多人认为这是一种反模式：https://isocpp.org/wiki/faq/style-and-techniques#hungarian - Андрей Беньковский

MIDDLEтњїSPACINGТў»т«ЈтљЌ№╝Ъ - Андрей Беньковский

显示剩余6条评论

2个回答

1

这是一篇实现该文章算法的代码，应该可以使用（注意：我没有编译它，因为我没有你程序的其他部分）：

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();
}

注意：我试图模仿您的代码风格，以便您不必重构它以匹配程序的其他部分。

附言：如果您发现任何错误，请在评论中通知我-我会编辑我的答案。

- Андрей Беньковский

我很感谢你的努力。明天我会尝试并及时向你报告任何问题。 - wannabe programmer

实际上，这一行存在问题：double angleSpace = pParent->GetAngleSpace(); 我觉得很奇怪的是，这个成员变量（angleSpace）似乎没有在任何地方被修改，只是被访问了。此外 - 这些行：double mid_x = MIDDLE(m_nWidth) 等等， m_nWidth 是屏幕的布局，它是常量（在树声明中定义）。你想在那里实现什么？ - wannabe programmer

谁说getter必须有对应的字段和setter了？这个函数应该根据角度范围和子节点数量来计算角度空间（见注释）。关于mid_x：它并没有真正改进任何东西，但也不会使情况变得更糟。 - Андрей Беньковский

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - wannabe programmer

@wannabeprogrammer 是的。我编辑了我的答案以更好地说明这一点。请注意，GetMinChildAngle() 和 GetMaxChildAngle() 也是没有设置器的获取器（当我有时间时，我会将其添加到答案中）。 - Андрей Беньковский

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fireant · Accepted Answer

可能现在你已经自己想出来了。如果没有，在这里

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以防万一您在该级别上有太多节点，您想将节点挤得更靠近一些。

您提供的文章使用的解决方案在图2-目录的切线和平分线限制中有所说明。我不太喜欢那种方法，因为如果您确定子级的绝对角度而不是相对于父级，则可以拥有一个更简单/更清洁的解决方案，该解决方案可以执行与该方法尝试执行的相同操作。

更新：

以下代码会生成此图像：

我认为你可以轻松地找出如何将子节点居中等内容。

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

显示更多节点的树形结构：