python 中的高效四叉树实现

Question

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

不知道他们是否有帮助，但这里有一些想法：

v_midpoint 和 h_midpoint 为每个添加到四叉树的粒子重新计算。相反，在初始化 Quad 时计算一次它们，然后将它们作为属性访问。
我认为计算 top_quad 不需要 and。 bounds.x + bounds.width < v_midpoint 就足够了。 left_quad.
先做简单的检查，必要时才做长的检查：bounds.x > v_midpoint 对比 bounds.x + bounds.width < v_midpoint
bounds.x + bounds.width 对大多数粒子计算多次。也许bounds.left和bounds.right可以计算一次作为每个粒子的属性
如果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

python 中的高效四叉树实现

Efficient quadtree implementation in python

python

pointers

optimization

quadtree