Radialer Baumlayoutalgorithmus
Ich habe eine Baumdatenstruktur implementiert, in der jeder Knoten (rekursiv) eine Liste von Zeigern zu seinen Kindern hält.
Ich versuche die (x, y) Koordinaten für die Visualisierung des Baumes zu berechnen. Ich ging durch diesen Artikel:
Schnitt Ich kann nicht herausfinden, wie ich über die erste Ebene gestoßen bin, d. h. Das habe ich bisher geschrieben:
%Vor%Ich bin mir nicht sicher, wie man die Grenzen, Winkelhalbierenden usw. berechnet. das hat meine Schublade bisher gemacht:
was offensichtlich nicht das ist, wonach ich seit dem zweiten (0 basierten) Level suche.
Ich habe Zugriff auf alle Informationen, die ich brauche, um das zu bekommen, wonach ich suche.
2 Antworten
Sie setzen den Winkelraum auf Ihrer zweiten Ebene auf PI (180 Grad), da es auf dieser Ebene nur zwei Knoten gibt, 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 Level 2 und höher erhalten und die Kinder so verteilen, dass sie einen Winkelraum von sibilingAngle = min(dAngleSpace, PI/10) haben. Das erste Kind hat also den genauen Winkel des Elternteils und die restlichen Kinder sind sibilingAngle voneinander entfernt. Sie bekommen die Idee und kommen wahrscheinlich mit einer besseren Methode. Ich verwende min für den Fall, dass Sie zu viele Knoten auf dieser Ebene haben, um die Knoten näher aneinander zu drücken.
Der Artikel, mit dem Sie verknüpft sind, verwendet eine Lösung, die in Figure 2 – Tangent and bisector limits for directories dargestellt wird. Ich mag diese Methode nicht sehr, denn wenn Sie den absoluten Winkel der Kinder bestimmen und nicht relativ zum Elternteil, können Sie eine einfachere / sauberere Lösung haben, die genau das tut, was diese Methode mit so vielen Operationen versucht.
Aktualisierung:
Der folgende Code erzeugt dieses Bild:
Ich denke, Sie können leicht herausfinden, wie Sie die Kindknoten usw. zentrieren.
%Vor%Update 2: Um es Ihnen einfacher zu machen, hier ist, wie Sie die Knoten zentrieren:
Einen bevölkerteren Baum anzeigen:
Hier ist eine Implementierung des Algorithmus aus dem Artikel, der funktionieren sollte (Hinweis: Ich habe es nicht kompiliert, da ich keine anderen Teile Ihres Programms habe):
%Vor%Hinweis: Ich habe versucht, Ihren Code-Stil nachzuahmen, damit Sie ihn nicht so umgestalten müssen, dass er mit anderen Teilen Ihres Programms übereinstimmt.
P.S. Wenn Sie irgendwelche Fehler entdecken, benachrichtigen Sie mich bitte in den Kommentaren - ich werde meine Antwort bearbeiten.
Tags und Links algorithm c++ tree graph-visualization