2D Bitmap und "Boundingboxes"

[Der_Unwissende]

HI,
dass das einem Octree für 2D ähnelt finde ich ist eine lustige Idee. Der 2D Octree heißt (ganz logisch) Quadtree. Die Idee entspricht eigentlich genau der eines Octree oder BinTree. Fangen wir mal unten an.
Bei keiner Dimension habe ich einen Punkt, Kollision ist trivial.
Bei einer Dimension kann ich weiter nach links oder Rechts gehen. Teile ich also eine gerade in der Mitte in zwei Teile und diese Teile wieder in der Mitte... Ich hätte einen Binären Baum.
Bei zwei Dimensionen habe ich Höhe und Breite. Der Einfachheit halber können wir sogar von einem Quadrat ausgehen (macht die Sache auch schneller). Hier kann ich jetzt einfach das gesamte Quardrat in 4 Teile zerlegen, diese wieder in 4 usw.
Bei drei Dimensionen brauche ich wieviel Teile? Genau 2^{3} oder auch 8 -> Octree. Du zerlegst den Raum in 8 Quarder, diese wieder in 8...

Warum macht man das? Na ja, z.B. zur Kollisionskontrolle. Im zwei Dimensionalen Raum kann ich gucken, in welchem der 4 Quadrate sich mein betrachteter Körper befindet. Es können bis zu 3 Quadrate (75%) rausfallen aus der Betrachtung. So schränkt man einfach den Bereich ein, den man absucht. Gut, doch woher weiß man jetzt in welchen Quadraten sich ein Körper befindet? Richtig man baut eine Boundingbox rum. Die Beschreibt ungefähr die Form des Körpers, tut dies jedoch geometrisch sehr einfach durch Rechtecke, mit denen man leichter rechnen kann. Also ist es nicht eine Art von 2D Octree, sondern wird benötigt um den Quadtree sinnvoll anzuwenden.
Der Weg der hier angegeben wurde ist eine Möglichkeit. Du kannst aber wieder den Quadtree Trick anwenden. Du gehst ja rekursiv vor und die einzelnen Quadrate werden immer kleiner. Dies machst du bis sie deine Toleranzgrenze (du willst ja eine ungefähre Box) erreicht haben (also alles von deinen Körpern liegt tolerierbar von der Kante des umgebenden Quadrats entfernt). Nun kannst du einfach für alle Quadrate schauen, ob sich hierin ein Körper befindet (z.B. geg. durch die Farbe). Wenn ja, fässt du den einfach mit den Nachbarn, die auch einen Körper enthalten zu einem größeren Körper zusammen. So hast du dann ein Rechteck, dass sich aus ein paar dieser Quadrate zusammen setzt.

Gruß Der Unwissende