kdbaum -> Zerlegung einer Ebene in Rechteckflächen

Ich habe eine Programmieraufgabe, in der ich mittels eines kd-Baums eine Fläche in Rechtecke zerlegen soll und bräuchte da etwas hilfe.

Zu Testzwecken habe ich einfach mal eine Baumstruktur wie hier:

http://www-lehre.informatik.uni-osnabrueck.de/~dbs/2001/skript/node34.html

angelegt. Ich weiß, dass ich den Baum traversieren muss, um die Fläche zu zerteilen, daher habe ich eine ganz einfache preorder-Funktion angelegt:

void preorder(node *n)
{
    printf("\n%i %i ", n->p.x, n->p.y);

    if (n->l !=z)
    {     
         preorder (n->l);
    }

    if (n->r !=z)
    {
         preorder (n->r);
    } 
}

Ich habe einer Header-Datei, mit deren Hilfe ich verschiedene Formen zeichnen kann (u.a. Rechtecke "rectangle(top_x, top_y, bottom_x, bottom_y)" oder Linien "lineto(x1,y1,x2,y2)".

Wie zeichne ich nun passend zur Baumstruktur und deren Punkte die Rechtecke? Der Vaterknoten repräsentiert ein Rechteck, wobei der linke Sohn das untere oder linke Rechteck einer Unterteilung bildet (der oben oder rechts). Wie müsste die preorder-Funktion verändert werden?

Vielen Dank im Voraus!

Niemand eine Idee?

unskilled

Der Vaterknoten repräsentiert ein Rechteck, wobei der linke Sohn das untere oder linke Rechteck einer Unterteilung bildet (der oben oder rechts). Wie müsste die preorder-Funktion verändert werden?

mach nen bsp. - vll mit code-tags und mit paar strichen was malen und dann beschreiben - so versteh ich das gerade nicht, vll gehts den anderen da ja auch so...

Er will, dass du seine Programmieraufgabe machst.

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

kdbaum -&gt; Zerlegung einer Ebene in Rechteckflächen

kdbaum -> Zerlegung einer Ebene in Rechteckflächen