Effiziente Implementierung von Quadtree in Python

Question

Für ein Projekt, an dem ich gerade arbeite, versuche ich Code zu schreiben, um Kollisionen zwischen Nicht-Punkt-Partikeln in einem 2D-Raum zu erkennen. Mein Ziel ist es, zu versuchen, eine Kollision für ein paar tausend Partikel mindestens ein paar Mal pro Zeitschritt zu erkennen, von dem ich weiß, dass es eine große Herausforderung für Python ist. Ich bin diesemgefolgt, der einen Quadtree implementiert, um die Anzahl paarweiser Überprüfungen wesentlich zu reduzieren, die ich machen muss. Also, wo ich glaube, ist ich laufe in Probleme diese Funktion:

def get_index(self, particle): 
    index = -1 
    bounds = particle.aabb 
    v_midpoint = self.bounds.x + self.bounds.width/2 
    h_midpoint = self.bounds.y + self.bounds.height/2 

    top_quad = bounds.y < h_midpoint and bounds.y + bounds.height < h_midpoint 
    bot_quad = bounds.y > h_midpoint 

    if bounds.x < v_midpoint and bounds.x + bounds.width < v_midpoint: 
     if top_quad: 
      index = 1 
     elif bot_quad: 
      index = 2 
    elif bounds.x > v_midpoint: 
     if top_quad: 
      index = 0 
     elif bot_quad: 
      index = 3 

    return index 

Diese Funktion wird aus meiner ersten Profilierung ist die Engpass und ich brauche es schnell zu Blasenbildung, wegen seiner hohen Anrufzahl. Ursprünglich lieferte ich nur eine Objektachsen-ausgerichtete Begrenzungsbox, die fast mit der Geschwindigkeit arbeitete, die ich benötigte, und dann erkannte ich, dass ich keine Möglichkeit hatte zu bestimmen, welche Partikel tatsächlich kollidieren könnten. Jetzt gebe ich eine Liste von Partikeln an meinen Quadtree-Konstruktor weiter und benutze einfach das Klassenattribut aabb, um meine Grenzen zu bekommen.

Gibt es eine Möglichkeit, etwas Analoges zu einem Objektzeiger anstelle des gesamten Objekts zu übergeben? Gibt es zusätzlich noch eine Empfehlung, diesen obigen Code zu optimieren?

Answer 1

Sie wissen nicht, ob sie helfen werden, aber hier sind ein paar Ideen:

1. v_midpoint und h_midpoint werden für jedes Teilchen zu dem Quadtree hinzugefügt neu berechnet. Berechnen Sie sie stattdessen einmal, wenn ein Quad initialisiert ist, und greifen Sie dann als Attribute darauf zu.

2. Ich glaube nicht, dass and für die Berechnung von top_quad benötigt wird. ist ausreichend. Gleiches gilt für left_quad.

3. Haben die einfacheren Kontrollen ersten und tut nur die längeren, falls erforderlich: bounds.x> v_midpoint vs. bounds.x + bounds.width < v_midpoint

4. bounds.x + bounds.width mehrfach für die meisten Teilchen berechnet wird. Vielleicht können die Grenzen links und rechts als Attribute jedes Teilchens berechnet werden.

5. Keine Notwendigkeit, bot_quad zu berechnen, wenn top_quad True ist. Oder umgekehrt.

Vielleicht so:

def get_index(self, particle): 
    bounds = particle.aabb 

    # right  
    if bounds.x > self.v_midpoint: 

     # bottom 
     if bounds.y > self.h_midpoint: 
      return 3 

     # top 
     elif bounds.y + bounds.height < self.h_midpoint: 
      return 0 

    # left 
    elif bounds.x + bounds.width < self.v_midpoint: 

     # bottom 
     if bounds.y > self.h_midpoint: 
      return 2 

     # top 
     elif bounds.y + bounds.height < self.h_midpoint: 
      return 1 

    return -1