Können wir Quad-Tree auf ein nicht quadratisches Rechteck anwenden?

Question

Ich versuche eine 2-D schnelle Kollisionserkennung mit Quad-Tree zu implementieren.

AFAIK, Quad-Tree unterteilt eine Region in 4 Teilregionen, Nordwesten, Nordosten, Südosten und Südwesten. Diese Aufteilung funktioniert perfekt mit einem Quadrat. Aber was, wenn die Region ein nicht-quadratisches Rechteck ist? In diesem Fall können wir die lange Kante und die kurze Kante nicht gleichmäßig teilen, und die kurze Kante bestimmt, wie weit wir teilen können.

Bin ich richtig? Soll das so sein?

Answer 1

Nehmen Sie einfach das Maximum der Breite und Höhe der Begrenzungsbox der Region von Interesse als die Seitenlänge des Quadbaums.

Eine andere Lösung: Zwei Quad-Baum implementtaions, die ich je gesehen habe verwendet ein Rechteck internaly, so dass aus der Box laufen würde, auch wenn die zur Verfügung gestellten Wurzel Grenzen nicht ein Quadrat ist. Sie teilen sowohl die Breite als auch die Höhe der Grenzen in jedem Unterteilungsschritt.
Beachten Sie jedoch, dass es 10 verschiedene Quadtree-Typen gibt. Ich rede von Rectangle Quadretrees.

Eine Implementierung verwendet explizit eine a-Seitenlänge, die durch 2 geteilt wird, so dass dies nicht für Nicht-Wurzel-Grenzen funktionieren würde.

Allerdings empfehle ich immer noch meinen ersten Satz, besser ein Quadrat als Wurzelgrenzen verwenden. Dies funktioniert dann für alle Quad-Tree-Typen.