Übung 7: Tiefe der Quadtrees/kd-Trees

Benutzeravatar
cofi
Mausschubser
Mausschubser
Beiträge: 86
Registriert: 22. Sep 2009 12:07

Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von cofi »

Wie weit soll man die Entwicklung der Bäume treiben? Wenn ich beispielsweise einen Quadtree komplett aufbaue -- d.h. solange unterteile, bis alle Kinder aus einer Farbe bestehen -- habe ich am Ende so viele Unterteilungen, dass nichts mehr erkennbar ist.

Da die Beispiele in den Folien sind beispielsweise auche nicht vollständig (Folie 24) sind: Was soll man als Abbruchbedingung nutzen? Einen kompletten Baum oder n Iterationen?

Enrico
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 20. Sep 2009 18:36

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von Enrico »

Hey,

beim zeichnen des Quadtrees ist mir aufgefallen, dass der Baum eine unmögliche Größe annimmt, damit in einem Kästchen auch nur ein Typ vorhanden ist !
So habe ich nun 32 Kästchen die ich anschauen muss... Habt ihr ähnliche Probleme ?

Grüße

moel
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 19. Apr 2011 13:57

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von moel »

Hi,
bei mir ist das gleiche Problem bin gerade bei 64 Kästchen und ich habe schon ein Din A4 blatt verwendet und es millimeter klein gemacht und es ist immer noch weiter zu unterteilen.
Ich denke mal wir müssen es nicht noch weiter unterteilen, da wir anhand unserer jetzigen Daten schon die Positionen der einzelnen Symbole ausmachen können.
Wäre aber mal cool, wenn jemand von den tutoren oder der Prof darauf antworten könnte, da ich schon seit freitag schon auf die antwortet warte (siehe cofi.oben).

Gruss

lara
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 1. Mai 2008 16:05

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von lara »

beim Erstellen des kd-tree muss man ja erst in der mitte, wo der Pfeil es anzeigt, eine erste Linie ziehen. Wenn ich es genau mittig mache, berühre ich das Dreieck. Ist das bei euch auch so? Mache ich da etwas falsch?

Kann mir jemand das Vorgehensweise eines Quadtree erklären?

Enrico
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 20. Sep 2009 18:36

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von Enrico »

@ Lara

Bei mir ist das genauso ! Also keine Panik ;)

Naja eigentlich ist das Verfahren an sich recht einfach, du halbierst das Bild senkrecht, und waagerecht, sodass vier große Quadrate entstehen.
Das machst du solange (zumindestens habe ich das in der Vorlesung so verstanden ?), bis immer nur eine Symbolart in einem deiner Quadrate sind.
Ich habe so 32 kleine Quadrate in meiner Zeichnung gehabt, finde es aber nicht gerade "didaktisch sinnvoll" einen solch riesigen Baum zu zeichnen ...

Wenn du noch Hilfe brauchst, schick mir ne PN.. :)

LG

Enrico

moel
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 19. Apr 2011 13:57

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von moel »

Ja, hast recht Immer ein Quadrat in 4 gleiche Quadrate teilen. daher kommt der Begriff "Quad".
Aber mal eine Frage an euch die 32 Quadrate , man kann doch nur 16 oder 64 Quadrate haben, sofern wir keinen Treffer haben? Oder?

lara
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 1. Mai 2008 16:05

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von lara »

wieviele Quadrate habt ihr denn? muss ich für jedes Objekt 4 quadrate haben? wie ist es, wenn ein Objekt direkt in einem Quadrat liegt, muss ich es trotzdem teilen?

Andreas P.
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 21. Okt 2009 16:29

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von Andreas P. »

Also ich habs relativ genau genommen und hab somit 37 Quadrate, weil ich auch nur die Quadrate nochmals unterteilt, wenn die Bedingung, dass pro Quadrat max. nur eine Figur sein darf, nicht erfüllt ist.
Bin mal gespannt :roll:
mfG

nein23
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 7. Okt 2009 18:15
Wohnort: Darmstadt

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von nein23 »

Ein offizielles Statement wäre echt super. Vorallem da übermorgen Abgabe ist.

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von dschneid »

Ist es denn sicher, dass bei der Einteilung für den Quadtree immer vier genau gleiche Teile, also Quadrate, entstehen müssen? Kann man nicht auch irgendwie so einteilen, dass vier Rechtecke entstehen? Die englische Wikipedia zumindest sagt zu einem Quadtree nur, dass jede Region in vier Unterregionen aufgeteilt wird, ohne besondere Anforderungen an die Form derselben. Dann wäre die Sache ja relativ einfach.

Ich würde den Veranstaltern hier einfach freundlich unterstellen, dass sie keine Aufgaben stellen, die viel Arbeit machen und keinen erkennbaren Sinn haben, außer eine Grafik mit immer mehr Unterteilungen zu füllen, bis man außer Trennlinien nichts mehr sieht.

(Ebenso muss man meiner Meinung nach auch beim kd-Baum nicht immer mittig trennen, wie das hier weiter oben mal stand, dafür gibt's auch ganz nette Beispielbilder auf Wikipedia.)

AlexanderF
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von AlexanderF »

dschneid hat geschrieben:Ist es denn sicher, dass bei der Einteilung für den Quadtree immer vier genau gleiche Teile, also Quadrate, entstehen müssen?
Ich danke, dass ist nicht der Fall,
wenn das Ursprungsbild nicht schon quadratisch ist, kann man es schlecht in 4 Quadrate aufteilen,

das bringt mich zu meinen Fragen:

Auf Folie 28 des aktuellen Foliensatzes, ist ein Beispiel für einen Quadtree angegeben,
in dem Beispiel sind folgenden Voraussetzungen erfüllt:
das Bild hat die selbe Höhe wie Breite,
Höhe und Breite sind 2er Potenzen,
und es kommen nur schwarze und weiße Punkt vor

diese drei Punkte sind bei der Hausübung nicht erfüllt:
das Bild innerhalb des schwarzen Rahmens hat folgende Ausmaße in Pixel: width: 224, height: 184,
und es kommen verschiedene Graustufen vor (an den Rändern zwischen weiß und schwarz).

wie sieht hier der Algorithmus aus?

ist es ok wenn man nicht weiß als schwarz annimmt?

gruß, Alexander

badvirt
Nichts ist wie es scheint
Beiträge: 23
Registriert: 13. Okt 2010 16:03

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von badvirt »

Beim Quadtree muss man das Feld nicht unbedingt in Quadrate unterteilen. Quad (eng: Viereck). Es können auch Rechtecke sein (Quadrate sind einfach nur schöner/praktischer). Es geht nur darum, dass man ein gegebenes Gebiet immer in 4 kleine aufteilt. Die Rekursionstiefe muss auch nicht immer der Pixeltiefe entsprechen, wie es in einem Beispiel auf der Folie dargestellt ist. Man sollte je nach Problemstellung eine geeignete Tiefe wählen, z.B., dass ein Rechteck nur ein Object bzw. ein Teil davon einschließt.

Der kd-Baum muss nicht symmetrisch sein, d.h. die erste Linie muss nicht unbedingt in der Mitte durchlaufen, wie es oben mal zu lesen war. Man kann einfach die y bzw. x Position der Geraden in den Knoten speichern (einfach bei Wiki anschauen).

Jan.R
Nichts ist wie es scheint
Beiträge: 23
Registriert: 19. Okt 2006 17:34

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von Jan.R »

Also soweit ich gelesen habe und an einer Stelle wurde sogar deutlich erwähnt daß Quad in Quadtree Nichts mit dem Quadrat zu tun hat.
Es steht lediglich dafür den Raum in 4 Teile zu teilen.
Leider scheiden sich bei den Definitionen die Geister, teilweise heißt es "4 gleiche Teile", andererseits nur "4 Teile".
Die Frage ist nur wo hört man auf, runterbrechen auf Pixel Ebene ist total unsinnig als Übungsaufgabe.

Ich habe es auf 154 Rechtecke runtergebrochen allerdings noch keinen Baum dazu weil ich denke dass es unnötig war.
Meine Lösung mit weniger Rechtecken in der in jedem Rechteck nur ein Bruchteil eines Symboles enthalten ist scheint mir sinnvoller.
Ich warte/hoffe auf ein offizielles Statement-

Beim kd-tree kann der Schnitt gemacht werden wo man will.
Es muß keine halbierende des aktuellen Feldes sein, die Felder dürfen getrennt werden wo man möchte.
Laut einem Beispiel daß ich gefunden habe darf auch mehrfach senkrecht geteilt werden so daß ein Feld z.B. nur in Streifen geteilt wird.
Dear Lord, please grant me the ability to punch people in the face over standard TCP/IP.

Drno
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 236
Registriert: 10. Feb 2005 20:16

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von Drno »

Bei der Aufgabe war es so gedacht, dass in jeder Zelle nur ein Objekt(teil) liegt. Zu dem Quadtree: Dies hat nicht unmittelbar etwas mit Quadraten zu tun, sondern mit dem Split in 4 Kinder (siehe Octree mit 8 Kindern). Natürlich kann man den Raum normalisieren und dort wären die Unterteilungen quadratisch, ansonsten sind die Unterteilungen aber immer regulär beim Quadtree, d.h. die Subräume sind alle gleich groß.
Beim kd-tree ist die Schnittstrategie Definitionssache. Eine Option ist es, abwechselnd entlang x oder y zu schneiden und dort jeweils einen median split durchzuführen, d.h. das in jedem Halbraum nach dem Split ungefähr die gleiche Anzahl Objekte liegt.
Programming today is a race between software engineers striving to build bigger and better idiot proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning.

Enrico
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 20. Sep 2009 18:36

Re: Übung 7: Tiefe der Quadtrees/kd-Trees

Beitrag von Enrico »

So wie ich es gerade verstanden habe, soll in jeder "Unterteilung" ein Objekt liegen, d.h. nicht zwei Objekte in einer Unterteilung.

@drno, d.h. man benötigt eine Unterteilung in mind. 32 kleine Quadrate / Vierecke - Richtig?

Grüße

Antworten

Zurück zu „Archiv“