pointers - 在 python 中,指针高效的四叉树实现

  显示原文与译文双语对照的内容

对于一个项目我正在努力编写一些代码来检测 2D 空间中非点粒子之间的碰撞。 我的目标是尝试检测几千颗粒子的碰撞,每次我知道这是 python的一个高顺序。 我遵循了这个博客文章,它实现了一个四叉树,以显著减少我需要的。 所以我认为我遇到问题的地方是这个函数:


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



这个函数从我的初始分析是瓶颈,我需要它的快速起泡,因为它的高呼叫计数。 最初我只是提供一个对象轴对齐框,它几乎以我所需的速度工作,然后意识到我无法确定。 所以现在我将粒子列表传递给我的四叉树构造函数,并使用类属性tmodel来获取我的界限。

我是否可以把类似的东西传递给对象指针而不是整个对象? 另外还有其他建议来优化上述代码?

时间: 原作者:

不知道他们是否会有所帮助,但以下是一些想法:

v_midpoint和h_midpoint被计算为所有添加到四元树的粒子。 相反,当一个四边形初始化时,计算它们一次,然后将它们作为属性访问。

我不认为在计算top_quad时 and 是必需的。 bounds.x + bounds.width <v_midpoint 对于left_quad来说已经足够了。

首先进行简单检查,必要时只执行较长的检查: bounds.x> v_midpoint vs bounds.x + bounds.width <v_midpoint

对于大多数粒子,bounds.x + bounds.width 计算多次。 也许 bounds.left 和 bounds.right 可以作为每个粒子的属性来计算一次。

如果top_quad是 true,则无需计算 bot_quad 。 或者 visa 。

可能这样:


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



...