Quadtrees - Nachbarn der einzelnen Zellen ermitteln?

pumuckl

Ich bin dabei, ein Programm zu schreiben, das eine quadratische Fläche in Flächen verschiedener Form unterteilt. Das wird dadurch erreicht, dass die quadratische fläche gleichmäßig gevierteilt wird, die unterflächen bei bedarf wieder usw.
Das sieht dann in etwa so aus:
http://www.derpumu.de/quadtree/htmltest.html

Das Konzept der quadtrees sieht bei mir etwa wie folgt aus:

class QuadTree
  {
  Quadtree* upper_left_child;
  Quadtree* upper_right_child;
  Quadtree* lower_left_child;
  Quadtree* lower_right_child;
  Quadtree* parent;

  int up, down, left, right; //die Koordinaten, die das Quadrat abdeckt;
  Datastruct data;  //Die eigentlichen Daten, z.B. Farbe einer gefärbten Fläche etc.
  }

Wenn ein Quadrat also unterteilt wird, werden vier kleinere Quadrate mit jeweils halb so großer Kantenlänge "eingehängt"

jetzt möchte ich informationen über die Nachbarn der einzelnen Quadrate speichern können, um von einem Quadrat ausgehend, die Nachbarquadrate mit Informationen zu "flooden".
Hat jemand ne Idee wie man das veranstalten könnte?

*push*

life

ich weiß zwar nicht, was das auf der hp darstellen soll und ich weiß auch nicht was du mit informationen "flooden" meinst, aber wenn du einfach ab nem knoten eine information für alle knoten des entsprechenden teilbaums setzen willst, machs doch einfach so:

//pseudocode
void setColor(Color color)
{
   data.color = color;
   foreach children as child
   {
     if(child != NULL)
       child->setColor(color);
   }
}

pumuckl

das auf der HP ist die unterteilung eines quadrates in kleinere quadrate wie oben beschrieben, um die dargestellte blaue Fläche (schwarz umrandet) mit den entsprechenden Quadraten darzustellen.
Und wie schon oben gesagt möchte ich die jeweiligen Nachbarn (auf der Fläche) der einzelnen quadrate erreichen können.
Die Fläche soll folgendermaßen erzeugt werden:
- ich habe als Daten einen (oder mehrere) Polygonzüge (listen von x/y-koordinatenpaaren), die die Umrandung der blauen Fläche bezeichnen.
- diese Polygonzüge werden bei Bedarf um Zwischenpunkte ergänzt, also die Auflösung erhöht bzw. die Abstände zwischen den Punkten so verringert, dass die schwarze Umrandung lückenlos erstellt werden kann.
- wenn das getan ist, müssen "nur noch" die Quadrate innerhalb und außerhalb der Umrandung mit der entsprechenden Farbinformation gefüllt werden. Das geht, wie klar ersichtlich ist, nicht einfach indem man einen gewissen Unterbaum rekursiv abgrast. Deshalb wollte ich einen Weg finden, indem ich von einem einzelnen Quadrat ausgehend immer weiter die Nachbarn erreiche und einfärbe. Die schwarzen quadrate stellen dabei sozusagen eine "mauer" dar, da sie nicht weiter eingefärbt werden. Ich hab das flooden genannt, weil derartige Mechanismen (z.B. bei M$-Paint der Farbeimer) auch oft "flood-fill" genannt werden.

life

also bei mir sieht das so aus:
http://img287.imageshack.us/img287/276/forum9jy.jpg
und ich verstehe immernoch nicht, was das darstellen soll >_<

wenn es nur darum geht einen nachbarn im quadtree zu bestimmen, könntest du es z.b. so machen (ungetestet):

QuadTree* searchUpperNode()
{
  //sucht nach node, die den pixel oberhalb vom jetzigen blatt enthält
  return searchUpperNode(this->up-1, this->left);
}

QuadTree* searchUpperNode(int x, int y)
{
  if(this->up > y)
  {
     //liegt drunter also nächst größeres quad fragen
     if(this->parent != NULL)
         return searchUpperNode(x,y); 
     return NULL; //not found       
  }

  //quad enthält koordinaten nun einfach richtige kind suchen
  if(this->hasChildren())
  {
     //gucken welches child koordinaten enthält
     //dann für dieses kind wieder searchUpperNode aufrufen (oder andere funktion ohne up > y zeugs)  
  }

  //keine kinder dann isses der nachbar
  return this;

}

life schrieb:

also bei mir sieht das so aus:
http://img287.imageshack.us/img287/276/forum9jy.jpg
und ich verstehe immernoch nicht, was das darstellen soll >_<

Sieht bei mir ganz anders aus:
Versuchs mal so:: http://www.derpumu.de/quadtree/s8.gif

otze

probierts mal mitm firefox der zeigts korrekt an

pumuckl

es sollte eigentlich so aussehen: http://www.derpumu.de/quadtree/quadtree.gif

Ich hatte überlegt, so ne Art "Klammer" einzuführen: wenn ein Quadtree unterteilt wird, dann wird so eine klammer zwischen je zwei benachbarten Quadraten eingefügt, die die Verlinkung in beiden Richtungen im Kopf hat. (http://www.derpumu.de/quadtree/cramps.gif rechts oben)
Wenn das Quadrat am Ende einer Klammer unterteilt wird, wird auch das Ende der Klammer dort geteilt (links unten). Das kann auch mehrmals passieren (rechts unten, oberer Teil).
Wird das Quadrat am anderen Ende der Klammer auch geteilt, dann wird die Klammer in zwe Hälften geteilt.... (rechts unten)

Uups falscher Link sieht bei mir natürlich wie bei pumuckl aus

life

dann mach das doch so.. eine wirklich einfache möglichkeit den nachbarn zur laufzeit zu bestimmen gibt es imho nicht. Also wirste wohl nicht drum herumkommen, dir die nachbarn schon beim aufbaun zu merken, wenn du die quadtree struktur beibehalten willst..

pumuckl

eine sparsamere Möglichkeit hab ich bisher auch nicht gefunden. Und den quadtree will ich beibehalten, zumal dadurch die Ausgabe in HTML-code ziemlich simpel wird: eine 2x2-Tabelle, wenn das Element Kinder hat, und ein Bild, wenns keine Kinder hat...

life

ja, die ausgabe scheint ja schon sehr gut zu klappen ..

bei den speichern der nachbarn sollteste dir aber vielleicht überlegen, ob du wirklich immer ALLE nachbarn kennen musst, oder ob es nicht reicht EINEN nachbarn in die jeweilige richtung zu kennen .. :>

pumuckl

naja, die "ausgabe" auf der seite ist per Hand zusammengefrickelt das waren anderthalb stunden copy&paste *g*