KO Baum zeichnen

Bluescreen · 07.05.2009, 19:08

Hallo,

ich möchte für eine kleine Turnierverwaltung mit php einen KO Baum (Elimination Tree) zeichnen. Wie gehe ich dabei am besten vor? Der Baum läuft von beiden Seiten bis zum Finale wie in dem Beispiel in dem angehängten Bild.

Wie kann ich so etwas realisieren? Die gängigen Graphbibliotheken wie jpgraph scheiden dabei aus. Es bleibt wohl nur ein zeichnen mit der GDlib.
Welchen Algorithmus würdet ihr hier verwenden um den Baum einigermaßen effektiv und schnell zu zeichnen. Vieleicht kennt auch jemand einige gute Literaturquellen zum Zeichnen von Bäumen. (nicht Google)

Gruß
Bluescreen

Chriz · 07.05.2009, 19:40

Das ganze schön in HTML zu generieren halte ich da für die einfachere Version.

Bluescreen · 07.05.2009, 19:45

Klar ist das die einfachere Version, aber ich würde gerne wissen wie ich es richtig zeichnen kann.

Chriz · 07.05.2009, 21:04

Ich hab mir gerade nochmal Gedanken gemacht und es ist im Prinzip nicht schwer, da es mathematisch gesehen ja einfache symmetrische Linien sind.

Folgende Werte brauchst du initial:
- Tiefe des Tunierbaumes ($max_depth)
- Größe der Karte ($map_width, $map_height)
- Die Länge der horizontalen Linie (entweder fix, oder abhängig von der Breite und maximalen Tiefe): $length_horizontal

Weiterhin brauchst du alle möglichen Kombinationen von $dir_x (bool), $dir_y (bool), Flags die festlegen, in welche Richtung gezeichnet wird, sowie eine rekursive Funktion, die nach $max_depth abbricht.

Zunächst würde ich eine for-Schleife basteln, die verantwortlich dafür ist, dass alle 4 Linien ausgehend vom Finale gezeichnet werden. Du hast also einen Startpunkt, der Initial auf den Mittelpunkt der Karte festgelegt ist.

Ich lege fest, dass der Zeichner, der nach oben zeichnet, die Zeichnung der horizontalen Linie übernimmt (andernfalls würde sie doppelt gezeichnet), $y_dir = true.

Abhängig von deinem Punkt an dem du dich befindest, wie lang du $horizontal_length festgelegt hast und auf welchem Flag $x_dir festgelegt ist (links/rechts, also true/false) zeichnest du die erste Linie (oder auch nicht, falls $y_dir = false).

Ich gehe davon aus, dass du den Endpunkt des neuen Striches jeweils als neuen Startpunkt verwendest.

Das ganze wird dank der for-Schleife 4x ausgeführt, tatsächlich wurden zwei horizontale Linien gezeichnet, die aber in einander übergehen (Treffpunkt Mittelpunkt). Du schickst die Endpunkte in deine rekursive Funktion, zusammen mit $depth (initial = 1), $x_dir und $y_dir. Abhängig von $y_dir und dem neuen Punkt, werden nun 4 Linien der Höhe $map_height / ($depth * 4) in der Vertikalen gezeichnet. Sprich du hast die horizontale(n) Linie(n) des "Finales" um 4 vertikale Linien zu den 4 Halbfinalteams erweitert und zwar im ersten Schritt um die Länge von einem Viertel der gesamten Kartenhöhe. Die Endpunkte der Linien ergeben wieder $point. So und jetzt beginnt die Rekursion, mit $depth + 1 und dem neuen Startpunkt. Du schickst alle wieder los und lässt sie horizontale Linie zeichnen (wenn $y_dir = true, wie vorher) und danach wieder den vertikalen Strich mit der $map_height / ($depth * 4), also nurnoch einem Achtel der Höhe der Karte, da $depth ja jetzt = 2 ist. Und so weiter, bis $max_depth, die Abbruchbedingung getroffen ist.

Du hast dir alle Positionen der horizontalen Striche gemerkt und kannst jetzt mit der Beschriftung anfangen (daher auch die fixe Breite der horizontalen Linien).

Der Rest (auf deiner Zeichnung die linken und rechten Boxen sowie die Texte oben und unten sind dann ja noch ein Klaks, abhängig von $map_height und $map_width).

Hoffe das war soweit verständlich.

Bluescreen · 08.05.2009, 03:59

Ok Danke das ist schonmal ein guter Ansatz zum zeichnen. Ich musste allerdings festellen das meine Datenstruktur die ich über einige verschaltete Arrays realisiieren wollte nur sehr bedingt für diesen Ansatz taugt.
Was wäre eine bessere Möglichkeit? Eventuell über eine klassischen Binärbaum ? Ein kleines Code Beispiel würde mir da eventuell sehr weiterhelfen.

Gruß
Bluescreen

Chriz · 08.05.2009, 08:46

Das glaube ich, ich hab aber keines

Aber was hat die Datenbank damit zu tun?

Bluescreen · 14.05.2009, 08:24

Ok, ich bin mittlerweile schon weiter. Du hast schon recht mit der Aussage das die Datenbank rein gar nichts zu tun hat. Die habe ich jetzt mit Nested Sets realisiert was ganz gut klappt.

Zum Zeichnen habe ich mir eine Hilfsklasse "Turtle" geschrieben mit der ich sehr einfach hintereinander Striche zeichnen kann.
Ich fange in der Mitte und zeichne nach links rekursiv aneinandergehängte "T"s bis zur benötigten Tiefe und am Ende die Striche auf denen die Namen stehen. Dann setze ich die Turtle zurück zum Ausgangspunkt und zeichne dasselbe in die andere Richtung. Ist auf jeden Fall so wesentlich einfacher. Hätte ich eigentlich direkt drauf kommen müssen, da wir damals in der Schule viel mit LOGO herumgespielt haben. Trotzdem auch nochmal danke für deinen Vorschlag.

Gruß
Bluescreen

Chriz · 14.05.2009, 22:40

Wenn du magst poste doch auch etwas Code, es gibt sicher noch mehr, die in Zukunft über den Thread stolpern und denen etwas Code helfen könnte.

Bluescreen · 14.05.2009, 23:02

Ok, hier ist die rekursive Funktion zum zeichnen des Baumes. Ich hab mir dann alle Knotenpunkte in Arrays gemerkt auf denen ich dann später die äußeren Striche den Name und die Punktzahl eintragen kann. In der angehängten Datei habe ich diese in verschiedenen Farben (Blätter oben grün,Blätter unten rot, Knotenpunkte blau)markiert.

Edit:
Äußere Äste und Namen habe ich jetzt auch hinbekommen (siehe Anhang). Ich bin jetzt noch mit den Größen am experiementieren. 32 Teilnehmer bekomme ich gerade so noch drauf, aber bei 64 oder mehr funktioniert das nicht mehr ganz so gut mit der rekursion wie ich die jetzt habe. Vieleicht hat da einer eine Idee?

PHP-Code:

  function drawTree($depth,$l){     
        $t = $this->Turtle;
        if ($depth > 0){ 
            $t->forward(-$l); 
            $t->right(90); $t->forward($l); $t->left(90);
            if($depth == 1) { $this->leafNodes[] = $t->getPos(); } 
            
            $this->drawTree($depth-1,$l/2); 
            $t->right(90); $t->forward(-2*$l); $t->left(90); 
            if($depth == 1) {$this->leafNodes[] = $t->getPos(); } 
            
            $this->drawTree($depth-1,$l/2); 
            $t->right(90); $t->forward($l); $t->left(90); $t->forward($l);
            $this->middleNodes[] = $t->getPos(); 
        }
    }

Ausschnitt mit den wichtigsten Funktionen der Turtle Klasse.

PHP-Code:

  class Turtle {
[...]
    function forward($length){
        $newX = (float)$this->posX + round(cos(deg2rad($this->angle)),6) * $length;
        $newY = (float)$this->posY + round(sin(deg2rad($this->angle)),6) * $length;
        $this->move($newX,$newY);
    }

    function move($newX,$newY){
        if($this->pen) {
            imageline ($this->g,$this->sx($this->posX),$this->sy($this->posY),$this->sx($newX),$this->sy($newY),$this->color);
        }

        $this->posX = $newX;
        $this->posY = $newY;
        $this->log("Move $newX,$newY");
    }    
    function left($degree){
        $this->angle += $degree;
        $this->log("Left $degree");
    }

    function right($degree){
        $this->angle -= $degree;
        $this->log("Right $degree");
    }
[...]
}

Gruß
Bluescreen

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Thema bewerten
Thema bewerten:

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
pdflib / Rechteck zeichnen	sean	PHP Tipps 2009	0	07.05.2009 10:15
Kreis mit imagearc zeichnen	hawkeye78	PHP-Fortgeschrittene	2	21.02.2009 14:11
[Erledigt] DOM Struktur in Baum einfügen	nikosch	PHP Tipps 2008	8	30.10.2008 19:50
PNG Bild auf vorher geladenes Bild zeichnen	blay09	PHP Tipps 2008	1	22.10.2008 21:04
Großer Baum -> Große Datei -> Hohe Ladezeit :(	PsychoEagle	PHP Tipps 2008	7	22.09.2007 12:44
Linie zeichnen	anno	PHP Tipps 2007	12	23.03.2007 09:04
JavaScript Baum bring Probleme	FireFIghter	HTML, Usability und Barrierefreiheit	1	06.10.2006 10:59
Zeichnen mit PHP	<Daniel>	PHP Tipps 2006	5	24.08.2006 16:54
diagramme zeichnen	flflfl	PHP Tipps 2006	1	13.04.2006 21:20
xml baum erstellen		PHP Tipps 2005-2	1	11.08.2005 10:32
kreis zeichnen ???	kid01	HTML, Usability und Barrierefreiheit	3	27.07.2005 17:37
Komme nicht sorecht weiter / Kategorie Baum erstellen.		PHP Tipps 2005	11	05.05.2005 13:20
[JS] Zeichnen	konsti	HTML, Usability und Barrierefreiheit	2	15.04.2005 16:34
Graphen Zeichnen		PHP Tipps 2004	4	29.09.2004 20:57
Problem bei Script Formular Daten und Baum		PHP Tipps 2004	1	27.09.2004 23:19

07.05.2009, 19:08
Bluescreen Neuer Benutzer Registriert seit: 07.05.2009 Beiträge: 9	KO Baum zeichnen Hallo, ich möchte für eine kleine Turnierverwaltung mit php einen KO Baum (Elimination Tree) zeichnen. Wie gehe ich dabei am besten vor? Der Baum läuft von beiden Seiten bis zum Finale wie in dem Beispiel in dem angehängten Bild. Wie kann ich so etwas realisieren? Die gängigen Graphbibliotheken wie jpgraph scheiden dabei aus. Es bleibt wohl nur ein zeichnen mit der GDlib. Welchen Algorithmus würdet ihr hier verwenden um den Baum einigermaßen effektiv und schnell zu zeichnen. Vieleicht kennt auch jemand einige gute Literaturquellen zum Zeichnen von Bäumen. (nicht Google) Gruß Bluescreen Miniaturansicht angehängter Grafiken


Mister Ad PHP Code Flüsterer Registriert seit: 21.08.2005 Beiträge: 4682 PHP-Kenntnisse: Fortgeschritten

07.05.2009, 19:40
Chriz Moderator Registriert seit: 11.05.2008 Beiträge: 6.268	Das ganze schön in HTML zu generieren halte ich da für die einfachere Version. __________________ "Nuschel ich?" - "Was?"

07.05.2009, 19:45
Bluescreen Neuer Benutzer Registriert seit: 07.05.2009 Beiträge: 9	Klar ist das die einfachere Version, aber ich würde gerne wissen wie ich es richtig zeichnen kann.

07.05.2009, 21:04
Chriz Moderator Registriert seit: 11.05.2008 Beiträge: 6.268	Ich hab mir gerade nochmal Gedanken gemacht und es ist im Prinzip nicht schwer, da es mathematisch gesehen ja einfache symmetrische Linien sind. Folgende Werte brauchst du initial: - Tiefe des Tunierbaumes ($max_depth) - Größe der Karte ($map_width, $map_height) - Die Länge der horizontalen Linie (entweder fix, oder abhängig von der Breite und maximalen Tiefe): $length_horizontal Weiterhin brauchst du alle möglichen Kombinationen von $dir_x (bool), $dir_y (bool), Flags die festlegen, in welche Richtung gezeichnet wird, sowie eine rekursive Funktion, die nach $max_depth abbricht. Zunächst würde ich eine for-Schleife basteln, die verantwortlich dafür ist, dass alle 4 Linien ausgehend vom Finale gezeichnet werden. Du hast also einen Startpunkt, der Initial auf den Mittelpunkt der Karte festgelegt ist. Ich lege fest, dass der Zeichner, der nach oben zeichnet, die Zeichnung der horizontalen Linie übernimmt (andernfalls würde sie doppelt gezeichnet), $y_dir = true. Abhängig von deinem Punkt an dem du dich befindest, wie lang du $horizontal_length festgelegt hast und auf welchem Flag $x_dir festgelegt ist (links/rechts, also true/false) zeichnest du die erste Linie (oder auch nicht, falls $y_dir = false). Ich gehe davon aus, dass du den Endpunkt des neuen Striches jeweils als neuen Startpunkt verwendest. Das ganze wird dank der for-Schleife 4x ausgeführt, tatsächlich wurden zwei horizontale Linien gezeichnet, die aber in einander übergehen (Treffpunkt Mittelpunkt). Du schickst die Endpunkte in deine rekursive Funktion, zusammen mit $depth (initial = 1), $x_dir und $y_dir. Abhängig von $y_dir und dem neuen Punkt, werden nun 4 Linien der Höhe $map_height / ($depth * 4) in der Vertikalen gezeichnet. Sprich du hast die horizontale(n) Linie(n) des "Finales" um 4 vertikale Linien zu den 4 Halbfinalteams erweitert und zwar im ersten Schritt um die Länge von einem Viertel der gesamten Kartenhöhe. Die Endpunkte der Linien ergeben wieder $point. So und jetzt beginnt die Rekursion, mit $depth + 1 und dem neuen Startpunkt. Du schickst alle wieder los und lässt sie horizontale Linie zeichnen (wenn $y_dir = true, wie vorher) und danach wieder den vertikalen Strich mit der $map_height / ($depth * 4), also nurnoch einem Achtel der Höhe der Karte, da $depth ja jetzt = 2 ist. Und so weiter, bis $max_depth, die Abbruchbedingung getroffen ist. Du hast dir alle Positionen der horizontalen Striche gemerkt und kannst jetzt mit der Beschriftung anfangen (daher auch die fixe Breite der horizontalen Linien). Der Rest (auf deiner Zeichnung die linken und rechten Boxen sowie die Texte oben und unten sind dann ja noch ein Klaks, abhängig von $map_height und $map_width). Hoffe das war soweit verständlich. __________________ "Nuschel ich?" - "Was?" Geändert von Chriz (07.05.2009 um 21:07 Uhr).

08.05.2009, 03:59
Bluescreen Neuer Benutzer Registriert seit: 07.05.2009 Beiträge: 9	Ok Danke das ist schonmal ein guter Ansatz zum zeichnen. Ich musste allerdings festellen das meine Datenstruktur die ich über einige verschaltete Arrays realisiieren wollte nur sehr bedingt für diesen Ansatz taugt. Was wäre eine bessere Möglichkeit? Eventuell über eine klassischen Binärbaum ? Ein kleines Code Beispiel würde mir da eventuell sehr weiterhelfen. Gruß Bluescreen

08.05.2009, 08:46
Chriz Moderator Registriert seit: 11.05.2008 Beiträge: 6.268	Das glaube ich, ich hab aber keines Aber was hat die Datenbank damit zu tun? __________________ "Nuschel ich?" - "Was?"

14.05.2009, 08:24
Bluescreen Neuer Benutzer Registriert seit: 07.05.2009 Beiträge: 9	Ok, ich bin mittlerweile schon weiter. Du hast schon recht mit der Aussage das die Datenbank rein gar nichts zu tun hat. Die habe ich jetzt mit Nested Sets realisiert was ganz gut klappt. Zum Zeichnen habe ich mir eine Hilfsklasse "Turtle" geschrieben mit der ich sehr einfach hintereinander Striche zeichnen kann. Ich fange in der Mitte und zeichne nach links rekursiv aneinandergehängte "T"s bis zur benötigten Tiefe und am Ende die Striche auf denen die Namen stehen. Dann setze ich die Turtle zurück zum Ausgangspunkt und zeichne dasselbe in die andere Richtung. Ist auf jeden Fall so wesentlich einfacher. Hätte ich eigentlich direkt drauf kommen müssen, da wir damals in der Schule viel mit LOGO herumgespielt haben. Trotzdem auch nochmal danke für deinen Vorschlag. Gruß Bluescreen Geändert von Bluescreen (14.05.2009 um 08:30 Uhr).

14.05.2009, 22:40
Chriz Moderator Registriert seit: 11.05.2008 Beiträge: 6.268	Wenn du magst poste doch auch etwas Code, es gibt sicher noch mehr, die in Zukunft über den Thread stolpern und denen etwas Code helfen könnte. __________________ "Nuschel ich?" - "Was?"

14.05.2009, 23:02
Bluescreen Neuer Benutzer Registriert seit: 07.05.2009 Beiträge: 9	Ok, hier ist die rekursive Funktion zum zeichnen des Baumes. Ich hab mir dann alle Knotenpunkte in Arrays gemerkt auf denen ich dann später die äußeren Striche den Name und die Punktzahl eintragen kann. In der angehängten Datei habe ich diese in verschiedenen Farben (Blätter oben grün,Blätter unten rot, Knotenpunkte blau)markiert. Edit: Äußere Äste und Namen habe ich jetzt auch hinbekommen (siehe Anhang). Ich bin jetzt noch mit den Größen am experiementieren. 32 Teilnehmer bekomme ich gerade so noch drauf, aber bei 64 oder mehr funktioniert das nicht mehr ganz so gut mit der rekursion wie ich die jetzt habe. Vieleicht hat da einer eine Idee? PHP-Code: function drawTree($depth,$l){ $t = $this->Turtle; if ($depth > 0){ $t->forward(-$l); $t->right(90); $t->forward($l); $t->left(90); if($depth == 1) { $this->leafNodes[] = $t->getPos(); } $this->drawTree($depth-1,$l/2); $t->right(90); $t->forward(-2$l); $t->left(90); if($depth == 1) {$this->leafNodes[] = $t->getPos(); } $this->drawTree($depth-1,$l/2); $t->right(90); $t->forward($l); $t->left(90); $t->forward($l); $this->middleNodes[] = $t->getPos(); } } Ausschnitt mit den wichtigsten Funktionen der Turtle Klasse. PHP-Code: class Turtle { [...] function forward($length){ $newX = (float)$this->posX + round(cos(deg2rad($this->angle)),6) $length; $newY = (float)$this->posY + round(sin(deg2rad($this->angle)),6) * $length; $this->move($newX,$newY); } function move($newX,$newY){ if($this->pen) { imageline ($this->g,$this->sx($this->posX),$this->sy($this->posY),$this->sx($newX),$this->sy($newY),$this->color); } $this->posX = $newX; $this->posY = $newY; $this->log("Move $newX,$newY"); } function left($degree){ $this->angle += $degree; $this->log("Left $degree"); } function right($degree){ $this->angle -= $degree; $this->log("Right $degree"); } [...] } Gruß Bluescreen Miniaturansicht angehängter Grafiken Geändert von Bluescreen (15.05.2009 um 01:20 Uhr).