python中高效的四叉树实现

Question

对于我正在做的一个项目，我试图写一些代码来检测二维空间中非点粒子之间的碰撞。我的目标是尝试检测几千个粒子的碰撞，每个时间步至少检测几次，我知道这对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

这个函数在我最初的分析中是一个瓶颈，我需要它快速膨胀，因为它的高调用计数。最初，我只是提供一个对象轴对齐的边界框，它几乎以我需要的速度工作，然后意识到我无法确定哪些粒子可能实际上正在碰撞。所以现在我将一个粒子列表传递给我的四叉树构造函数，并使用类属性aabb来获取边界。在

有没有什么方法可以把类似的东西传递给一个对象指针而不是整个对象？另外，还有其他的建议来优化上面的代码吗？在

Answer 1

不知道他们是否会有所帮助，但以下是一些建议：

1. 对于添加到四叉树中的每个粒子，将重新计算v_中点和h_中点。相反，在四元函数初始化时计算一次，然后作为属性访问它们。

2. 我认为在计算top_quad时不需要and。bounds.x + bounds.width < v_midpoint就足够了。左四角也一样。

3. 首先进行简单的检查，必要时只进行较长的检查：bounds.x>；v峎midpoint vs.bounds.x+边界宽度<；v嫒中点

4. 对于大多数粒子，bounds.x + bounds.width被多次计算。也许 吧边界。左以及边界。对吗可以作为每个粒子的属性计算一次。

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