Quad Tree mit vielen beweglichen Objekten

Ich habe eine Quad Tree-Implementierung, die für das, was ich versuche, sehr nützlich ist. Mein Problem ist, dass das Update für den Quad-Baum sehr lange dauert, wenn mein Ansichtsfenster viele Objekte enthält.

Es ist bekannt, dass Quad Trees für nicht statische Objekte langsam sind. Ich habe einige Methoden ausprobiert, um die Dinge zu beschleunigen, aber Tatsache ist, dass ich sehr oft eine große Anzahl von Objekten aktualisieren muss.

Gibt es einen besseren Algorithmus, den ich mir stattdessen ansehen sollte? Gibt es einige abgeleitete Quad Tree-Implementierungen, von denen Sie wissen, dass sie für mich nützlich sein könnten?

Wie bewegen Sie Quad Tree-Objekte? Die einfachste (und langsamste) Methode besteht darin, das Objekt zu entfernen und erneut einzufügen. Der Open-Source- XNA-Quad-Baum, den ich und ein Freund erstellt haben, macht ein wenig Logik, wenn sich ein Objekt bewegt:

If the object is still inside the same quad
    if the object fits into a child quad
        Add to child
Else
    move the object to the parent(s) until it fits, and optionally going back down into children

Wenn Sie so etwas bereits tun, kann es sich lohnen, andere räumliche Indexmethoden wie Spatial Hashing zu untersuchen .

Ich benutze Grenzen für Objekte und füge sie in das tiefste Quad ein, das sie enthält. (Ich war noch nie damit zufrieden, Dinge als Punkte zu behandeln.)

Für sich schnell bewegende Objekte, bei denen es sich normalerweise auch um kleine Objekte handelt, z. B. Aufzählungszeichen, berechne ich die Grenzen ihres Pfads für eine bestimmte Anzahl von Zeitschritten oder die maximale Größe, sodass ich eine Aufzählungszeichen eher durch ein größeres Rechteck als durch ein kleineres Quadrat gebunden habe und dies nicht muss bewege sie fast genauso oft.

Sie können auch den Verschiebungscode selbst optimieren, um das Objekt intelligent zu verschieben, anstatt es zu entfernen und erneut einzufügen.