径向树布局算法 [英] Radial Tree layout algorithm
问题描述
我已经实现了一个树形数据结构，其中每个节点（递归地）拥有一个指向其子节点的指针列表。
我正在尝试计算（x，y）坐标以可视化树。
我浏览了这篇文章：
这显然不是我从第二级（从0开始）所要的。
我可以访问所有的信息我需要得到我想要的东西。
大概到现在您已经自己弄清楚了。如果不是，则
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>
使用命名空间std;
类Node {
public：
Node（）{
parent = 0;
角度= 0;
angleRange = 2 * M_PI;
深度= 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 *>孩子们
浮角；
float angleRange;
节点*父级；
int深度；
int x，y;
};
void rotation（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;
浮点数x，y;
rotation（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）;
开奖（root-> children [i]，cr）;
}
}
int main（void）{
节点根；
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 *表面；
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）;
}
开奖（&root，cr）;
cairo_surface_write_to_png（surface， image.png）;
cairo_destroy（cr）;
cairo_surface_destroy（surface）;
返回0;
}
更新2：
使您更轻松，这是将节点居中的方法：
for（int i = 0; i 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;
显示更多的树：
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.
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:
这篇关于径向树布局算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
