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