Quadtree

[Luma]

Hallo,
in Bezug auf die Spieleprogrammierung (ich poste diesen Thread aber absichtlich in diesem Unterforum, weil er nur bedingt damit etwas zu tun hat) bin ich im Internet über den sogenannten Quadtree gestolpert. Ich habe mich sodann auf die Suche nach mehr Infos dazu gemacht, aber nichts rechtes finden können. Selbst Wikipedia ist da recht mau ausgestattet. Kennt ihr vielleicht einen guten Link zu einer Seite, wo ich nähre Infos finden kann (muss jetzt nicht direkt mit Java im Zusammenhang stehen, mich interessieren auch ganz allgemeine Infos)? (Die Googlesuche habe ich bereits befragt, d.h. die PDFs und DOCs von Google kenne ich bereits.) Oder vielleicht ein ganz gutes Buch?

Gruß
Lutz

 

[Marco13]

Die Frage ist schon sehr unspezifisch. ~"Kennt jemand ein gutes Buch über Computer?" :wink: Je nachdem, in welchem Zusammenhang, kannst du ja (wie du vielleicht schon gemerkt hast) auch mal nach "Octree" oder dem (allgemeinen) Kd-Tree suchen....

 

[ARadauer]

@marco: Quadtree ist unspezfisch?

@luma: also ich hab zu hause noch massig dokumente rumliegen die kann ich dir ja mal zukommen lassen. ich hab meine bachelorarbeit über r-trees geschrieben... schreib mir eine pm, damit ich nicht vergesse

 

[Marco13]

@marco: Quadtree ist unspezfisch?

Entweder zu unsezifisch - oder zu spezifisch :wink: Ein Quadtree ist nur eine von vielen "ähnlichen" Datenstrukturen - und wird in vielen verschiedenen Zusammenhängen eingesetzt...

 

[Luma]

Entweder zu unsezifisch - oder zu spezifisch :wink: Ein Quadtree ist nur eine von vielen "ähnlichen" Datenstrukturen - und wird in vielen verschiedenen Zusammenhängen eingesetzt...

Mag sein, nur kann ich das nicht wissen. Octree sagt mir auch was, ist, soweit ich das aber beurteilen kann, für meine Anforderung nicht geeignet. (Okay, war da ein bisschen ungenau, was meine Anforderungen ("Spieleprogrammierung") angeht: Ich bin über die Quadtrees gestolpert, als ich mich zum Thema Kollisionserkennung in der 2D-Spieleprogrammierung recherchiert habe.)

 

[Marco13]

Ja, genau um dieses "geeignet" geht es ja: Ein Qctree ist das gleiche wie ein Quadtree - nur eben in 3D statt in 2D. Und ein kD-Tree ist (für k=2) auch (fast) ein Quadtree, nur wird nicht immer in der Mitte der Fläche unterteilt, sondern 2 mal "da, wo es am besten ist". Und ein BSP-Tree ist auch (fast) ein Quadtree, nur wird eben nicht immer in der Mitte unterteilt, sondern da, wo es am besten ist, und zusätzlich muss die Unterteilung nicht an den Achsen ausgerichtet sein.

Anders formuliert: Ein kd-Tree ist in 2D ein Spezialfall vom BSP-Tree, und ein Quadtree ist ein Spezialfall vom kD-Tree. Vieles von dem, was man zu diesen beiden Tree-Arten findet, läßt sich also mit ein bißchen Phantasie auf Quadtrees übertragen.