クワッドツリーでのスタックオーバーフロー例外

Question

私はC＃で取り組んでいるクアッドツリーの実装に問題があります。何らかの理由で

else 
{ 
    //bottom right 
    TreeList[3].PushB(b); 
    return; 
} 

：ファイルTree.csでは、次の行は、ツリー内で一貫して約50個のオブジェクトを（右下のクワッドの最初の分岐を引き起こし、おそらく十分な）開始、スタックオーバーフロー例外が発生しますこのコードを呼び出すことを許可すると、無限ループが作成されるため、Stack Overflow Exceptionとなります。私はなぜこれが無限の再帰を引き起こすのか見ていないが、他の人はそうではない。

ここにコードがあります。 Ball.csとTree.csはどちらもClassesフォルダにあります。

Ball.cs：

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace QuadTree.Classes 
{ 

    class Ball 
    { 
     protected int x, y, r; 
     protected decimal vx, vy; 
     public static int min_w = 0, 
      max_w = 200, 
      min_h = 0, 
      max_h = 200; 

     //treating origin as top-left of screen 


     public Ball(int set_x = 1, int set_y = 1, decimal set_vx = 1, decimal set_vy = 1, int set_r = 1) 
     { 
      x = set_x; 
      y = set_y; 
      vx = set_vx; 
      vy = set_vy; 
      r = set_r; 
     } 


     public int get_x() 
     { 
      return x; 
     } 


     public int get_y() 
     { 
      return y; 
     } 


     public void Print() 
     { 
      Console.WriteLine("x: {0} y: {1} vx: {2} vy: {3} r: {4}", x, y, vx, vy, r); 
     } 


     //get the y-intercept of the current ball 
     protected decimal getB() 
     { 
      return (decimal)y - ((vy/vx) * (decimal)x); 
     } 


     //get the y-intercept given an x, y, and slope 
     public decimal getB(int x, int y, decimal m) 
     { 
      return (decimal)y - (m * (decimal)x); 
     } 


     //get the slop of the line that goes through both balls 
     protected decimal getM(Ball b) 
     { 
      return getM(y, b.y, x, b.x); 
     } 


     //get the slop of the line going through two points 
     public decimal getM(int y1, int y2, int x1, int x2) 
     { 
      if (x1 - x2 == 0) 
      { 
       return 0; 
      } 
      else 
      { 
       return ((decimal)(y1 - y2))/((decimal)(x1 - x2)); 
      } 
     } 


     public void Move() 
     { 
      x += (int)vx; 
      y += (int)vy; 

      if (x > max_w) 
      { 
       vx *= -1; 
       x = x - (x - max_w); 
      } 
      else if (x < min_w) 
      { 
       vx *= -1; 
       x *= -1; //won't work if min_w != 0 
      } 

      if(y > max_h) 
      { 
       vy *= -1; 
       y = y - (y - max_h); 
      } 
      else if (y < min_h) 
      { 
       vy *= -1; 
       y *= -1; //won't work if min_h !=0 
      } 
     } 


     //detect if the current ball collides with the given ball 
     public void Collide(Ball b) 
     { 
      decimal d; 

      d = (decimal)Math.Sqrt(Math.Pow((x - b.x), 2) + Math.Pow((y - b.y), 2)); 

      if (d<= r || d <= b.r) 
      { 
       ResolveCollision(b); 
      } 
      return; 
     } 


     //determine the resulting vectors after the collision 
     private void ResolveCollision(Ball b) 
     { 
      //get the line between the center points 
      decimal M; 
      M = getM(b); 


      //determine angle between the line and ball a 
      double theta_1; 

      if (b.vx != 0) 
      { 
       double top = (double)((M - (b.vy/b.vx))); 
       double bottom = (double)(1 + (M * (b.vy/b.vx))); 

       if (bottom != 0) 
       { 
        theta_1 = Math.Atan(top/bottom); 
       } 
       else 
       { 
        theta_1 = 0; 
       } 
      } 
      else 
      { 
       if (1 + M != 0) 
       { 
        theta_1 = Math.Atan((double)(M/(1 + M))); 
       } 
       else 
       { 
        theta_1 = 0; 
       } 

      } 


      theta_1 = theta_1 * (Math.PI/180); 

      //calculate new vx and vy for ball a 
      //http://www.gamefromscratch.com/post/2012/11/24/GameDev-math-recipes-Rotating-one-point-around-another-point.aspx 
      double new_vx, new_vy; 


      new_vx = Math.Cos(theta_1) * (double)(vx) - Math.Sin(theta_1) * (double)(vy) + x; 
      new_vy = Math.Sin(theta_1) * (double)(vx) + Math.Cos(theta_1) * (double)(vy) + y; 



      vx = (decimal)new_vx - x; 
      vy = (decimal)new_vy - y; 

      //determine angle between the line and ball b 

      if (b.vx != 0) 
      { 
       double top = (double)((M - (b.vy/b.vx))); 
       double bottom = (double)(1 + (M * (b.vy/b.vx))); 

       if (bottom != 0) 
       { 
        theta_1 = Math.Atan(top/bottom); 
       } 
       else 
       { 
        theta_1 = 0; 
       } 


      } 
      else 
      { 
       if (1 + M != 0) 
       { 
        theta_1 = Math.Atan((double)(M/(1 + M))); 
       } 
       else 
       { 
        theta_1 = 0; 
       } 
      } 


      theta_1 = theta_1 * (Math.PI/180); 

      //calculate new vx and vy for ball a 


      new_vx = Math.Cos(theta_1) * (double)(b.vx) - Math.Sin(theta_1) * (double)(b.vy) + b.x; 
      new_vy = Math.Sin(theta_1) * (double)(b.vx) + Math.Cos(theta_1) * (double)(b.vy) + b.y; 


      b.vx = (decimal)new_vx - x; 
      b.vy = (decimal)new_vy - y; 
     } 
    } 
} 

Tree.cs

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace QuadTree.Classes 
{ 
    class Tree //: IDisposable 
    { 
     protected int min_w, 
      max_w, 
      min_h, 
      max_h, 
      thresh_hold, level; 

     bool leaf = true; 

     protected List<Ball> BallList = new List<Ball>(); 
     protected List<Tree> TreeList = new List<Tree>(); 


     public Tree(int set_min_w, int set_max_w, int set_min_h, int set_max_h, int set_thresh_hold, int set_level) 
     { 
      min_w = set_min_w; 
      max_w = set_max_w; 
      min_h = set_min_h; 
      max_h = set_max_h; 
      thresh_hold = set_thresh_hold; 
      level = set_level; 
     } 


     //push a ball onto the tree 
     public void PushB(Ball b) 
     { 
      if(leaf) 
      { 
       BallList.Add(b); 

       if (BallList.Count > thresh_hold) 
       { 
        Branch(); 
       } 
      } 
      else 
      { 
       LeafPush(b); //push the ball to a leaf node 
      } 
      return; 
     } 


     //push a ball onto a leaf of the current node 
     protected void LeafPush(Ball b) 
     { 
      if (b.get_x() <= max_w/2) 
      { 
       //left 
       if (b.get_y() <= max_h/2) 
       { 
        //top left 
        TreeList[0].PushB(b); 
        return; 
       } 
       else 
       { 
        //bottom left 
        TreeList[2].PushB(b); 
        return; 
       } 
      } 
      else 
      { 
       //right 
       if (b.get_y() <= max_h/2) 
       { 
        //top right 
        TreeList[1].PushB(b); 
        return; 
       } 
       else 
       { 
        //bottom right 
        TreeList[3].PushB(b); 
        return; 
       } 
      } 
     } 


     private void Branch() 
     { 
      Console.WriteLine("Branching level {0}", level); 

      leaf = false; 

      TreeList.Add(new Tree(min_w, max_w/2, min_h, max_h/2, thresh_hold, level + 1));    //top left 
      TreeList.Add(new Tree((max_w/2) + 1, max_w, min_h, max_h/2, thresh_hold, level + 1));   //top right 
      TreeList.Add(new Tree(min_w, max_w/2, (max_h/2) + 1, max_h, thresh_hold, level + 1));   //bottom left 
      TreeList.Add(new Tree((max_w/2) + 1, max_w, (max_h/2) + 1, max_h, thresh_hold, level + 1)); //bottom right 

      foreach(Ball b in BallList) 
      { 
       LeafPush(b); 
      } 

      BallList.Clear(); 

      return; 
     } 
    } 
} 

Program.csの

using QuadTree.Classes; 
using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading; 
using System.Threading.Tasks; 

namespace QuadTree 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      Random rnd = new Random(); 

      List<Ball> BallList = new List<Ball>(); 

      for (int i = 0; i < 100; i++) 
      { 
       BallList.Add(new Ball(rnd.Next(Ball.min_w, Ball.max_w), 
             rnd.Next(Ball.min_h, Ball.max_h), 
             rnd.Next(1, 5), 
             rnd.Next(1, 5), 
             rnd.Next(1, 5))); 
      } 




      Tree t = new Tree(Ball.min_w, Ball.max_w, Ball.min_h, Ball.max_h, 10, 0); 

      foreach (Ball b in BallList) 
      { 
       b.Move(); 
       t.PushB(b); 
      } 


      Console.ReadLine(); 
     } 

    } 
} 

Answer 1

だから、私はロジックを必要としているようです新しいノードセットの作成が実行可能かどうかをテストします。私は私が10の最小幅を持っているノードを望んでいたことを決めたので、私はこのコードを変更：

//push a ball onto the tree 
public void PushB(Ball b) 
{ 
    if(leaf) 
    { 
     BallList.Add(b); 

     if (BallList.Count > thresh_hold) 
     { 
      //test if branching will produce a viable area 
      if ((max_w/2) - min_w >= 10) 
      { 
       Branch(); 
      } 
     } 
    } 
    else 
    { 
     LeafPush(b); //push the ball to a leaf node 
    } 
    return; 
} 

そして今、私は、もはやスタックオーバーフロー例外に

Answer 2

を取得していないあなたは、あなたがしている方法を修正する必要がありますサブツリーを作成する。あなたは第4のサブツリー（右下の象限）を作成するときは、次の番号を使用している：

(max_w/2) + 1, max_w, (max_h/2) + 1, max_h 

これは常に同じ大きさになり

（101、200、101、200）の右下の象限のためにあなたが最大数だけを使用しているからです。これは、すべての後続ブランチでも同様にの右下の象限に当てはまります。

プログラムは、その4番目のサブツリーのしきい値に達するまで正常に実行されます。その後、分岐しようとし、分岐すると、すべてのボールを次の第4のサブツリーに送ります。これらのボールのすべてがその象限に座標を持っているので、これが続けられます。それがあなたの無限ループが起こっている場所です。

象限を細分化する場合は、新しい尺度を親象限の最小幅と最大幅の両方から外す必要があります。

EDIT：

このコードは正しく象限を分割する必要があります

int center_w = min_w + (max_w - min_w)/2; 
int center_h = min_h + (max_h - min_h)/2; 
TreeList.Add(new Tree(min_w, center_w, min_h, center_h, 
    thresh_hold, level + 1)); // top left 
TreeList.Add(new Tree(center_w + 1, max_w, min_h, center_h, 
    thresh_hold, level + 1)); //top right 
TreeList.Add(new Tree(min_w, center_w, center_h + 1, max_h, 
    thresh_hold, level + 1)); //bottom left 
TreeList.Add(new Tree(center_w + 1, max_w, center_h + 1, max_h, 
    thresh_hold, level + 1)); //bottom right