Kreisförmige Darstellung einer Baumstruktur

Question

Ich habe einige Daten in einer Baumstruktur und möchte sie auf graphische Weise darstellen, wobei der Wurzelknoten in der Mitte der Bühne, seine Kinder in einem Kreis um ihn herum und so weiter für jedes Kind angeordnet sind, um ihren Eltern herum. Ich möchte keine überlappenden Knoten, also lautet die Frage, wie man den Platz optimal anordnen kann. Etwas weniger oder mehr wie (gefunden über Google)

Welche Algorithmen muss ich suchen, um so etwas zu realisieren?

Answer 1

Sie können dies auf eine emergente Weise tun, indem Sie ein System einrichten, in dem jeder Baumknoten versucht, so viel Abstand zu allen anderen Knoten (außer dem Elternknoten) wie möglich zu halten, aber so kurz wie möglich vom Elternknoten entfernt (bis zu einem Mindestabstand, den er einhalten muss). Führen Sie diesen Algorithmus für jeden Knoten wiederholt aus, bis er stabilisiert ist, und Sie werden eine Anordnung haben, wie Sie sie beschreiben. Ich bin sicher, es gibt viele Optimierungen, die Sie vornehmen können, aber ich bin ziemlich sicher, dass dies der einfachste Ansatz ist. Der Versuch, das gesamte Layout im Voraus zu berechnen, wäre sehr komplex...

Answer 2

Wenn es Ihnen egal ist, wie es gemacht wird, sondern nur dass Sie die Daten visualisieren, dann werfen Sie einen Blick auf graphviz's radiale Anordnung. Obwohl das Beispiel nicht genau aussieht, wie Sie es möchten, ist es die Anordnung, die Sie benötigen. Es wird Ihnen auch einige Ideen geben, wie es gemacht wird, mit den ganzen Forschungsarbeiten darin. Viel Glück!

Sie könnten auch sehen, wie einfach es ist, diese Arbeit in eine kreisförmige Struktur zu erweitern.

Answer 3

Sie versuchen, eine planare Darstellung eines Graphen zu zeichnen. Finden Sie hier einige Schlagworte und vielleicht eine Ressource Und auf Wikipedia

Ah und ich habe vergessen: Sie können dies auf newtonische Weise mit Kräften tun. Geben Sie einfach allen Knoten ein abstoßendes Potenzial, machen Sie sie alle zu Protonen, die sich gegenseitig abstossen. Geben Sie den Kanten die Eigenschaften von newtonschen Federn, die Kräfte ausüben, die sie zusammenziehen, und schon sind Sie bereit. Könnten sogar schöne Animationen auf diese Weise erstellen. Dies ist auch eine offizielle Methode des Graphenzeichnens, aber ich kenne den Namen nicht.

Answer 4

Wenn Sie den Baum mit minimalem Platzverschwendung und kurzen Verbindungen zeichnen möchten, dann steht Ihnen eine rechnerisch aufwendige Lösung bevor. Es wird schwierig sein, dies in Echtzeit bei einem Baum von anständiger Größe zu erreichen, ganz zu schweigen davon, dass kleine Änderungen am Baum zu einem radikal anderen Gleichgewicht führen können.

Ein anderer Ansatz wäre, die physikalische Simulation aufzugeben und sie einfach iterativ aufzubauen. Ich habe letzte Woche etwas Ähnliches gemacht, aber meine Bäume sind wahrscheinlich bei weitem nicht so kompliziert wie Ihre.

Für dieses Baumlayout muss jedes Knotenobjekt einen Winkel und einen Offset speichern. Diese beiden Zahlen steuern, wo sie auf der Grafikfläche landen.

Hier ist mein Grundalgorithmus:

1) Gehen Sie über Ihre gesamten Baumdaten und finden Sie alle Blattknoten. 2) Während Sie dies tun, messen Sie die Länge jeder Verzweigung, damit Sie wissen, welche die längste ist. 3) Sobald Sie alle Blattknoten haben, verteilen Sie sie gleichmäßig über einen konzentrischen Kreis. Sie können entweder den gesamten Kreis verwenden oder nur einen Teil des Winkelbereichs. 4) Sobald alle Blattknoten gelöst sind, gehen Sie erneut über den Baum und gehen von außen nach innen vor. Jeder Knoten, auf den Sie treffen, der kein Blattknoten ist, benötigt ein Layout. Im Grunde genommen hat von hier an jeder Knoten einen Winkel, der der Durchschnitt aller seiner Kindknoten ist, und der Offset beträgt der graph_radius * (depth_of_node / maximum_depth)

Ich fand heraus, dass dies mir eine sehr ordentliche und menschenlesbare Verteilung bietet, wenn auch nicht sehr effizient in Bezug auf die Bildschirmnutzung. Ich habe eine Animation meiner Baumdarstellung hier hochgeladen: GIF-Animation