Aufbau einer Quadtree -
Ich bin versucht, einen quadtree (a 4-ary tree) halten die Informationen in einem bestimmten BMP.
Ich bin kämpfen, um herauszufinden, wie Sie zum Aufbau des Baumes gegeben, BMP.
Grundsätzlich die Struktur ist so, dass jedes Blatt repräsentiert ein pixel. Jeder Knoten 4 Zeiger, von denen jeder auf eine der vier verbleibenden Quadranten im Bild. Damit kann jeder Knoten teilt das aktuelle Bild in 4 Teile. Durch die Zeit, die Sie auf dem Blatt sind Sie an einem bestimmten pixel.
Ich bin mir nicht sicher wie Sie gehen über den Bau einen Baum, um die Karte mit einem bestimmten image. Unter der Annahme, dass das Bild hat die Abmessungen die eine Potenz von zwei, was soll ich tun. Ich verstehe, dass eine rekursive Funktion könnte wahrscheinlich machen das die meisten aus, aber ich bin kämpfen, um herauszufinden, wie zu verfolgen, wo in dem Bild, das ich dabei bin zu werden.
Dies ist in C++ und momentan mein quadtree.h-Datei enthält ein Node* root, wo ein Knoten ist definiert als eine Struktur mit einem pixel-element und 4 Zeiger auf andere Knoten. Jeder innere Knoten (nicht-Blatt-Knoten) halten sollte, der Durchschnittliche Wert aller 4 RGB-Werte führt.
Ich bin versucht, um einen Algorithmus, aber ich glaube, ich könnte brauchen, um eine Struktur oder zwei in der .h-Datei. Gibt es eine bessere/mehr sauber Weg, um dieses problem zu lösen?
Du musst angemeldet sein, um einen Kommentar abzugeben.
gut, je nachdem, wie Sie Ihre Bitmap-Daten gespeichert, die Sie machen könnten die Dinge anders. Sind Sie aus einer Datei zu Lesen und ablegen direkt in den Baum? Wenn dem so ist, .BMP-Dateien (wenn ich mich Recht erinnere) erzählen Sie Ihre Breite und Höhe rechts oben, so dass Sie könnte tatsächlich verwenden, um genau herauszufinden, wie viele Ebenen Sie haben, was könnte Ihnen helfen, etwas aufzubauen.
Auch, je nachdem, wie groß deine Bilder sind, könnten Sie speichern alle Pixel in einem 2D-array von Knoten und haben die Baum-Art "sit on top" das array so, dass Ihre Blätter in das array und alles andere ist woanders. Wenn Sie waren zu tun, dass Sie schreiben konnte, einige geschachtelte Schleifen, dass würde gehen durch und greifen Gruppen von vier Knoten, berechnen Sie Ihre Durchschnittliche und Klumpen 'em zusammen, und dann tun die gleiche Sache mit dem Knoten ist es gerade erstellt haben. Das wäre wahrscheinlich schneller als der Aufbau des Baumes von oben nach unten, weil Sie nie von durchschnittlich mehr als vier Pixeln, in der Erwägung, dass Gebäude von oben nach unten brauchen würde, um durchschnittlich mehr als vier Pixel jeder Schritt, außer dem letzten.
Wenn Sie nicht wollen, es zu tun in einem array die einfachste Sache, meiner Meinung nach, wäre jeder Knoten verfolgen seine x -, y-Koordinaten. Das würde Ihnen ermöglichen, tun im Grunde dasselbe wie mit dem array, aber Sie würden nicht nur einstecken Indizes.
Ist das hilfreich? Wie sind Sie mit der Speicherung der Bitmaps? Was ist das Endziel?
STANN ist die beste open-source-Implementierung im moment.
http://sites.google.com/a/compgeom.com/stann/
Wort zu den weisen, verwenden Sie Bern et al quadtree-Konstruktion-Algorithmus und verzichten auf den funky Baum-Operationen.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4634&rep=rep1&type=pdf
Ich bin die Entwicklung einer Bibliothek jetzt für OpenCl. Ich werde einen link posten, sobald ich fertig bin es zu testen.