Pythonでの効率的なクアッドツリーの実装

Question

私は現在、私はいくつかのコードを記述して、2D空間内の非ポイントパーティクル間の衝突を検出しようとしています。私の目標は、私が知っている時間ステップごとに少なくとも数回、数千個の粒子の衝突を検出しようとすることです。私は大幅に私が作る必要がある数のペアごとのチェックを減らすためにquadtreeを実装する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 

私の最初のプロファイルからこの機能は、ボトルネックであると私はそれは、その高いコール数の、高速でふくれする必要があります。もともとは、私が必要とするスピードでほぼ動作していたオブジェクト軸に合わせたバウンディングボックスを供給していましたが、実際にどのパーティクルが衝突しているのか判断できませんでした。だから今私はquadtreeコンストラクタにパーティクルのリストを渡しているだけで、クラスの属性aabbを使って境界を取得しています。

オブジェクト全体ではなくオブジェクトポインタに何かアナログを渡すことはできますか？また、上記のコードを最適化するための推奨事項がありますか？

Answer 1

、彼らがお手伝いしますならば知っているが、ここではいくつかのアイデアですしないでください。

1. v_midpointとh_midpointは四分木に追加されるすべての粒子のために再計算されます。代わりに、Quadが初期化されたときにそれらを1回計算し、それを属性としてアクセスします。

2. top_quadの計算にはandが必要と思われません。 bounds.x + bounds.width < v_midpointで十分です。 left_quadと同じです。

3. は最初のシンプルなチェックを行い、必要な場合にのみ長い方の操作を行います。

4. bounds.x + bounds.widthは、ほとんどの粒子に対して複数回計算されbounds.x> v_midpoint対bounds.x + bounds.width < v_midpoint。たぶん、bounds.leftとbounds.rightは各パーティクルの属性として1回計算できます。

5. top_quadがTrueの場合、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