python中有效的四叉樹實現

Question

對於我正在研究的項目，我試圖編寫一些代碼來檢測2D空間中非點粒子之間的碰撞。我的目標是嘗試每個時間步至少幾次檢測幾千個粒子的碰撞，我知道這是python的一個高階命令。我遵循這個實現了四叉樹的blog post，以顯着減少我需要進行的成對檢查次數。那麼，我相信，我遇到的問題是這樣的功能：

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 

這從我最初的分析功能是瓶頸，我需要它來起泡，因爲它的高調用數快。最初我只是提供一個物體軸對齊的邊界框，它幾乎以我需要的速度工作，然後意識到我沒有辦法確定哪些粒子實際上可能會碰撞。所以現在我將一個粒子列表傳遞給我的四叉樹構造函數，並使用class屬性aabb來獲得我的邊界。

有沒有辦法將類似物傳遞給對象指針而不是整個對象？另外還有其他建議來優化這個代碼嗎？

Answer 1

不知道它們是否會有所幫助，但這裏有一些想法：

1. v_midpoint和h_midpoint重新計算加入到四叉樹每一個粒子。相反，當Quad初始化時計算一次，然後將它們作爲屬性訪問。

2. 我不認爲在計算top_quad時需要and。 bounds.x + bounds.width < v_midpoint就足夠了。相同的left_quad。

3. 先做簡單的檢查，並在必要時只能做一個較長：bounds.x> v_midpoint與bounds.x + bounds.width < v_midpoint

4. bounds.x + bounds.width計算多次對大多數顆粒。也許bounds.left和bounds.right可以作爲每個粒子的屬性計算一次。

5. 如果top_quad爲真，則不需要計算bot_quad。或者反之亦然。

也許是這樣的：

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