我已经实现了一个树数据结构,其中每个节点都(递归地)持有指向其子节点的指针列表。
我正在尝试计算 (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 级)以来,这显然不是我要找的。p>
为了获得我正在寻找的东西,我可以访问我需要的所有信息。
最佳答案
可能现在您已经自己弄清楚了。如果没有,这里
double dNodesInDepth = GetNodesInDepth(i).size();
double dAngleSpace = 2 * PI / dNodesInDepth;
您在第二层将角度空间设置为 PI(180 度),因为该层只有两个节点,dNodesInDepth = 2
。这就是为什么画完节点20之后,节点30就180度了。该方法适用于非常茂密的树木,因为该角度很小。但是在您的情况下,您希望使角度尽可能接近 parent 的角度。因此,我建议您获取 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;
关于c++ - 径向树布局算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33328245/