Flächenzerlegung mittels 2d-Baum



  • Hallo!

    Ich bin bei meinem Projekt nun an meine bescheidenen Grenzen angelangt und weiß nun nicht mehr weiter. Um so mehr erhoffe ich hier die Lösung meines Problems zu finden 😉

    Der Oberbegriff nennt sich eigentlich "Bereichssuche", nur das ich mit meinem Programm keine Punkte in einem gewissen Bereich in einer Ebene suchen möchte, sondern einfach nur die Ebene in der Weise zerteilen möchte, das die Linien der Rechtecke auf die Punkte fallen. Am Ende soll es in etwa so aussehen:

    zerlegte Fläche

    Ich habe einen Zufallsgenerator implementiert, der mir n zufällige Punkte generiert, welche dann aufsteigend sortiert in meinem Baum eingetragen werden. So weit bin ich nun und stehe vor der grafischen Ausgabe. Die Punkte sind dann bezogen auf das obige Bild folgendermaßen im Baum angelegt:

    Punkte im Baum

    Zur Visualisierung nutze ich die "graphics.h", welche ein Rechteck mit "rectangle(x1,y1,x2,y2)" zeichnet.

    Hat jemand eine Idee, wie ich das am besten hinbekomme? Falls es hilft, gebe ich einfach mal die verwendeten Strukturen an:

    struct point 
    {
        int  x, y;
        int info;
    };
    
    struct node
    { 
        struct point p;
        struct node *next; 
        struct node *l;
        struct node *r;
    };
    

    Ich würde mich wirklich sehr freuen, wenn jemand eine Lösung finden würde.

    mfg MrLINK



  • Dein Problem ist die grafische Ausgabe, oder?

    Was verwendest du für eine Bibliothek (woher hast du den Header "graphics.h" )? Denn Standard-C++ bietet keine grafische Ausgabe.



  • Ich weiß nicht, ob es sich bei dieser Version der graphics.h um meinige handelt, jedoch sollte sie definitiv die rectangle-Funktion (bzw. viele andere einfache geometrische Funktionen) unterstützen.

    Aus dem Archiv wird die graphics.h sowie die Bibliothek libbgi.a benötigt. Bei Dev Cpp musste ich außerdem "-lbgi -lgdi32 -lcomdlg32 -luuid -loleaut32 -lole32" bei der Linker-Kommandozole bei den Compiler-Optionen hinzufügen.

    mfg MrLINK



  • Man da habe ich den Link selbst komplett vergessen 😉

    Hier ist die Seite und unter dem Punkt:

    "How do I use Borland Graphics Interface (graphics.h)?"

    findet man den Header und die Bibliothek.

    mfg MrLINK



  • Und wo genau ist dein Problem? - Da hat es ja ein einfaches Beispiel und verlinkt sind auch mehr Sachen. Und über google findest du sicher noch mehr Beispielcode, wie man das benutzt.



  • Ich möchte anhand der "rectangle(x1,y1,x2,y2)"-Funktion aus der "graphics.h" mit Hilfe meines 2d-Baums und dessen Punkte eine ebene wie folgt zerteilen:

    nämlich so

    Wie gesagt, ich habe eine Baumstruktur und die Punkte wurden aufsteigend sortiert (alternierend zwischen x und y) in den Baum eingetragen. Nun geht es darum, die Ebene korrekt in möglichst große Rechtecke zu zerteilen.

    Es liegen außerdem Fragen auf der Hand wie (relativ platt): Das Rechteck benötigt 4 Koordinaten, ein Punkt hat jedoch nur 2, wie zeichne ich das Rechteck?

    Oder: Die Rechtecke dürfen sich ja nicht überschneiden. Angenommen ich beginne damit, die ebene horizontal in der Mitte zu zerteilen. Dann gehe ich in die untere Hälfte und teile sie dort Vertikal, jedoch liegen die Grenzen der daraus entstehenden Rechtecke bei der (1.) Horizontalen. Jedoch werden auch die Rechtecke nach der 1. Vertikalen wieder horizontal, dann vertikal (usw.) geteilt und müssen ihre jeweiligen Grenzen haben, da die Rechtecke sich ja nicht über die gesamte Ebene, sondern über ihren Bereich erstrecken sollen.

    Ich habe nun keine Ahnung, wie ich das nun implementieren soll.

    mfg MrLINK



  • überlege dir ein geschicktes Kriterium nach dem du die Fläche in Rechtecke aufteilen willst. "Punkte liegen auf den Kanten" ist keines, sodnern maximal eine Nebenbedigung.

    Zum Beispiel könnntest du das so machen: zuerst berechnest du die benötigte Größe des äußeren Rechtecks. Dann nimmst du den ersten Punkt und teilst das Rechteck in 2 kleinere mit dem Punkt auf der Schnittlinie. dann nimmst du den nächsten Punkt, und schaust in welchem Rechteck er liegt. Den Punkt packste dann in das Rechteck und zerteilt es wieder. usw bis du alle Punkte durch sind. Dann schauste am Ende, welche Rechtecke du mit dem Algorithmus erzeugt hast, und zeichnest diese dann.



  • otze schrieb:

    überlege dir ein geschicktes Kriterium nach dem du die Fläche in Rechtecke aufteilen willst. "Punkte liegen auf den Kanten" ist keines, sodnern maximal eine Nebenbedigung.

    Zum Beispiel könnntest du das so machen: zuerst berechnest du die benötigte Größe des äußeren Rechtecks. Dann nimmst du den ersten Punkt und teilst das Rechteck in 2 kleinere mit dem Punkt auf der Schnittlinie. dann nimmst du den nächsten Punkt, und schaust in welchem Rechteck er liegt. Den Punkt packste dann in das Rechteck und zerteilt es wieder. usw bis du alle Punkte durch sind. Dann schauste am Ende, welche Rechtecke du mit dem Algorithmus erzeugt hast, und zeichnest diese dann.

    So ähnlich wird das ja auch gemacht und das Gedankenspielchen habe ich auch schon oft durchexerziert, nur wie implementiere ich sowas? Wie lege ich denn die Grenzen der Rechtecke fest? Mal beginnt ein Rechteck bei (0|0), mal muss es ja bei einer beliebigen Koordinate starten.

    Ich bräuchte einfach mal ein Beispiel. Zur Hilfe steuere ich einfach mal meinen Algorithmus bei, mit dem ich meine Punkte in den Baum eintrage:

    void tree2Dinsert(struct point p)
    {
        struct node *f, *t;
        int d, td;
    
        for (d = 0, t = head; t != z; d != d) 
        {
             td = d ? (p.x < t->p.x) : (p.y < t->p.y);
    
             f = t; 
             t = td ? t->l : t->r;
        }
    
        t = (struct node*)malloc(sizeof *z);
    
        t->p = p; t->l = z; t->r = z;
    
        if (td) 
        {
             f->l = t; 
        }
        else 
        {
             f->r = t;
        }   
    }
    

    d - Tiefe des Baums
    l - linker Knoten
    r - rechter Knoten
    head - Wurzel mit Punkt (0|0).

    mfg MrLINK



  • Ich bin nun etwas weiter gekommen und würde den Baum nun gern Preorder traversieren, jedoch stürzt das Programm beim preorder-Aufruf ab:

    struct point 
    {
        int  x, y;
        int info;
    };
    
    struct node
    {
        struct point p;
        struct node *next; // zeigt auf das nächste Element
        struct node *l; // linker Abstieg in den Baum
        struct node *r; // rechter Abstieg in den Baum
    };
    
    struct node *z, *head; // head -> Wurzel
    struct point *p;
    
    void preorder(struct node *n);
    
    [...]
    main()
    {
    [...]
    preorder(head);
    }
    
    void preorder(struct node *n)
    { 
        if(n)
        {
             printf("%i %i\n\n", p->x, p->y);
             preorder (n->l);
             preorder (n->r);
        }
    }
    

    Ich möchte einfach nur die gespeicherten x- und y-Werte der Punkte ausgeben.

    Was habe ich denn falsch gemacht?

    mfg MrLINK



  • Bitte schreib C++ Code!

    struct point
    {
        int  x, y;
        int info;
    };
    
    struct node
    {
        node (): next(0), l(0), r(0) {} // Konstruktor mit Initialisierungsliste
        point p;
        node *next;
        node *l; 
        node *r;
    };
    
    node *z, *head; // head -> Wurzel
    point *p;
    
    void preorder(node *n);
    
    [...]
    main()
    {
    [...]
    preorder(head);
    }
    
    void preorder(node *n)
    {
        if(n)
        {
             printf("%i %i\n\n", p->x, p->y);
             preorder (n->l);
             preorder (n->r);
        }
    }
    

    Ich würd mal sagen, dass du x und y nicht initialisiert hast, was jetzt im Defaultkonstruktor gemacht wird.

    //Update:
    Das ist jetzt natürlich auch kein C++ Code, wie man ihn schreiben würde,aber das struct überall nervt einfach.



  • X und Y habe ich hier vorher initialisiert:

    void preprocess(struct point p[], int n) 
    {
        int i;
    
        p[0].x = 0; 
        p[0].y = 0; 
        p[0].info = 0;
    
        z = (struct node*)malloc(sizeof *z);
    
        z->l = z; 
        z->r = z; 
        z->p = p[0];
    
        head = (struct node*)malloc(sizeof head);
    
        head->r = z; 
    
        head->p = p[0];
    
        initwindow(max_width, max_height);
    
        for (i = 1; i <= n; i ++)
        { 
             tree2Dinsert(p[i]);
        }
    }
    

    Was meinst du denn mit dem struct überall nervt? Spielst du da auf typedef an?

    mfg MrLINK



  • Aber nur den ersten.

    Und das Code Stück zeigt mir umso mehr, dass du C programmierst.

    Wenn du die Initialisierungsliste rein machst, dann sollte es so, wie ich das bis jetzt sehe gehen.

    Allerdings empfehle ich dir dringend ein gutes C++ Buch zu lesen und dann das ganze nochmal neu zu schreiben. Da gibt es so viel zu bemängeln, dass es sich kaum lohnt das aufzulisten. 😉 (Klingt hart ich weiss, aber du schaust den Tatsachen besser ins Auge)



  • Ja ok 😉

    Das mit C und C++ hat seinen Grund: Ich habe einen Header "graphics.h" der nur unter C++ funktioniert (nicht aber unter C). Da ich aber spätestens in den Klausuren mit C arbeiten muss, habe ich also ein C++ - Projekt erstellt und aber mit der C-Syntax programmiert.

    Kannst du mir vielleicht einfach mal ein Bespiel schreiben, wo ich einen 2d-Baum initialisiere und die Wurzel an eine (meine) preorder Funktion übergebe?

    mfg MrLINK

    PS: Bin ich hier mit C komplett falsch oder gibt es irgendwo ein C-Subforum?



  • So, wie ich das mit meinen müden Augen sehe liegt es wirklich daran, dass die Zeiger nicht initialisiert sind dann greifst du nämlich auf nicht definierte Werte zu und erhälst genau solche Fehler.

    Ja es gibt ein C Unterforum (gleich eins ob diesem hier; Es heist Ansi C).


Log in to reply