Stack Overflow Exception with Quad Tree

Question

I am experiencing an issue with a Quad Tree implementation I am working on in C#. In the file Tree.cs, the following line will cause a Stack Overflow Exception, starting consistently around 50 objects in the tree (probably enough to cause the first branch of the bottom right quad):

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

For some reason it seems that, when I allow this code to be called, it creates an infinite loop, hence the Stack Overflow Exception. I am not seeing why this would cause an infinite recursion while the others don't.

Here's the code. Ball.cs and Tree.cs both reside in a Classes folder.

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();
        }

    }
}

It's not necessarily infinite recursion. When you recurse throughout your tree, you simply need to have more nodes in the call stack than you have space in your stack to store that data to get an SOE. — Servy
– Servy, Commented Dec 8, 2016 at 22:06
To diagnose a stack overflow, examine the stack trace. The middle of it will be all the same thing over and over again. That's where the unbounded recursion is, so examine those stack frames carefully. — Eric Lippert
– Eric Lippert, Commented Dec 8, 2016 at 23:27

Mike Cowan · Accepted Answer · 2016-12-08 23:31:17Z

1

You need to revise the way you're creating the sub-trees. When you create the fourth sub-tree (bottom right quadrant), you're using the following numbers:

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

This always results in the same dimensions (101, 200, 101, 200) for the bottom right quadrant branch because you're only using the maximum numbers. This is true for the bottom right quadrant in every subsequent branch as well.

The program will run fine until you hit the threshold on that fourth sub-tree. It then attempts to branch, and as it branches, it sends all of it's balls into the subsequent fourth sub-tree. This will keep occurring because all of those balls have coordinates in that quadrant. That is where your infinite loop is occurring.

If you're trying to keep subdividing the quadrants, then you need to base the new dimensions off both the minimum and maximum widths and heights of the parent quadrant.

EDIT:

This code should subdivide the quadrants properly:

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

edited Dec 8, 2016 at 23:31

answered Dec 8, 2016 at 23:14

Mike Cowan

9295 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

DForck42 Over a year ago

ahh! you're absolutely right! I didn't see the error in the math I was making, I will get around to checking this

DForck42 · Accepted Answer · 2016-12-08 22:45:06Z

0

So it seems that I needed logic to test if creating a new set of nodes would be viable. I decided I wanted a node to have a minimum width of 10, so I changed this code:

//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;
}

And now I no longer get the Stack Overflow Exception

answered Dec 8, 2016 at 22:45

DForck42

20.6k14 gold badges61 silver badges86 bronze badges

Collectives™ on Stack Overflow

Stack Overflow Exception with Quad Tree

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related