?
Ok
Also das ganze Thema basiert ja auf der orthogonalen Bereichssuche, nur das ich nicht wirklich suchen, sondern nur die Bereiche zeichnen möchte.
Ich habe folgende Baumstruktur erstellt und die Punkte wie in diesem Beispiel eingetragen:
http://www-lehre.informatik.uni-osnabrueck.de/~dbs/2001/skript/Images/Ps/abb-5-3.gif
Mein Ziel ist nun, folgende grafische Ausgabe zu programmieren, wobei die Linien völlig ausreichend sind (also keine Achsen- bzw. Punktebezeichnungen):
http://www-lehre.informatik.uni-osnabrueck.de/~dbs/2001/skript/Images/Ps/abb-5-2.gif
A ist hier die Wurzel. Wenn wir uns alle Punkte außer A wegdenken, teilt A die vorhandene Fläche (16 x 10) in zwei Teilrechtecke. Alle Punkte mit y <= y von A befinden sich nun in dem unteren Rechteck (bzw. im linken Teilast von A), aller Punkte mit y > y von A im oberen Rechteck (bzw. im rechten Teilast von A).
Ich habe vor, den Baum preorder zu traversieren, so dass als nächtstes Punkt B "ausgegeben" würde. Wir befinden uns also nun im unteren Rechteck bei Punkt B, wobei B nun selbiges tut und das untere Rechteck in 2 Teilrechtecke teilt, wobei hier nun alle Punkte mit x <= x von B im linken Teilast, alle Punkte mit x > x von B im rechten Teilast (bzw. im Rechteck, hier: 0 Punkte) liegen.
Der Baum wird nun also traversiert und es sollen immer fleißig Rechtecke gezeichnet werden. Ich tue mich aber gerade sehr schwer beim Ermitteln der Rechtecke bzw. bei deren Grenzen, da sie ja nicht überlappen dürfen bzw. nicht außerhalb des Rechtecks des Vaterknotens liegen dürfen.
Die "nackte" Preorder-Funktion habe ich ja oben bereits gezeigt, hier nochmal die Deklaration der Baumstruktur:
typedef struct node_
{
point p;
node_ *l, *r; // l = linker, r = rechter Sohn
}node;
node *z, *head, *n; // head -> Wurzel
Wenn noch etwas unklar ist, bitte bescheid sagen. Ich wollte nicht mein ganzes Programm posten, da sonst bestimmt Verwirrung auftritt :p