Radial Tree Layout-Algorithmus

Question

Ich habe eine Baumstruktur implementiert, in der jeder Knoten (rekursiv) eine Liste von Zeigern zu seinen Kindern enthält.

Ich versuche, die (x, y) Koordinaten für die Visualisierung des Baumes zu berechnen. Ich ging durch diesen Artikel:

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

Cut ich nicht herausfinden kann, wie man gest Vergangenheit der ersten Ebene, dh Dies ist, was ich bisher geschrieben haben:

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

Ich bin nicht sicher, wie die Grenzen zu berechnen, Bisektoren usw. das ist, was meine Schublade bisher tat:

das ist offensichtlich nicht, was ich seit dem zweiten (0 basierten) Level suche.

Ich habe Zugriff auf alle Informationen, die ich brauche, um zu erhalten, wonach ich suche.

Answer 1

Wahrscheinlich haben Sie es jetzt selbst herausgefunden. Wenn nicht, hier

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

Sie die Einstellung der Winkelraum auf PI (180 degreees) auf Ihrer zweiten Ebene, da es nur zwei Knoten auf dieser Ebene sind, dNodesInDepth = 2. Deshalb ist der Knoten 30 nach dem Zeichnen des Knotens 20 um 180 Grad entfernt. Diese Methode wäre für sehr dichte Bäume gut, weil dieser Winkel klein ist. Aber in Ihrem Fall möchten Sie den Winkel so nahe wie möglich am Winkel des Elternteils halten. Also schlage ich vor, dass Sie den Winkel des Elterns für Knoten auf Ebene 2 und höher erhalten und die Kinder so verteilen, dass sie einen Winkelraum von sibilingAngle = min(dAngleSpace, PI/10) haben. So wird das erste Kind den genauen Winkel des Elternteils haben, und die übrigen Kinder sind sibilingAngle voneinander entfernt. Sie bekommen die Idee und kommen wahrscheinlich mit einer besseren Methode. Ich benutze min für den Fall, dass Sie zu viele Knoten auf dieser Ebene haben Sie die Knoten näher aneinander drücken möchten.

Der Artikel, mit dem Sie verknüpft sind, verwendet eine Lösung, die in Figure 2 – Tangent and bisector limits for directories veranschaulicht wird. Ich mag diese Methode nicht sehr, denn wenn Sie den absoluten Winkel der Kinder und nicht relativ zum Elternteil bestimmen, können Sie eine einfachere/sauberere Lösung haben, die genau das tut, was diese Methode mit so vielen Operationen versucht.

Update:

Der folgende Code erzeugt dieses Bild:

Ich glaube, du leicht herausfinden, wie die untergeordneten Knoten zum Zentrum und 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: Nur um es einfacher für Sie, hier ist, wie die Knoten zum Zentrum:

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; 

ein dichter besiedelten Baum Angezeigt:

Answer 2

Hier ist eine Implementierung des Algorithmus von t er Artikel, die funktionieren sollte (Anmerkung: Ich habe es nicht kompilieren, da ich nicht auf andere Teile des Programms haben):

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

Hinweis: Ich habe versucht, den Code Stil zu imitieren, so dass Sie nicht haben Refactor es um andere Teile Ihres Programms zu entsprechen.

P.S. Wenn Sie irgendwelche Fehler entdecken, benachrichtigen Sie mich bitte in den Kommentaren - ich werde meine Antwort bearbeiten.