Tags: debugging, element, inserting, microsoft, msdn, overflow, quad, run, software, stack, stackoverflow, time, tree, visual
Stack Overflow Problem
On Microsoft » Microsoft Visual C#
24,082 words with 6 Comments; publish: Tue, 01 Jan 2008 18:55:00 GMT; (30078.13, « »)
I am having a stackoverflow problem when inserting an element in my quad tree. I get it every time if I run without debugging, but when I run through step by step with the debugger on it doesn't overflow. Any reason for this? And is there a way to dump the stack after the error has occured so I can see what exactly is happening?
Thanks
http://visual-csharp.itags.org/q_visual-csharp_53378.html
All Comments
Leave a comment...
- 6 Comments
The common cause of this problem is that when you iterate through some block of code infinitely.
It doesnot come while debugging becuase it executes too slow in debug mode since you are breaking at each line of code.
See this piece of code:
public Color ControlColor
{
set
{
return this.ControlColor = value; // See, this line is creating infinite recursion by calling itself again and again...
}
}
So when ever you set value of such property, you'll get StackOverflow exception.
See your code. I hope you are doing the same thing mistakenly.
I hope this will help.
Best Regards,
Rizwan aka RizwanSharp
#1; Wed, 12 Sep 2007 22:37:00 GMT
- The code isnt recursing infinitely. It actually finishes when in debug mode and displays the form. #2; Wed, 12 Sep 2007 22:38:00 GMT
The code isnt recursing infinitely. It actually finishes when in debug mode and displays the form. Can you post the block of code from where the exception is coming up?
#3; Wed, 12 Sep 2007 22:39:00 GMT
Thats the problem. I am not sure exactly where the exception is coming from. I will post the code. First off, this is the first time I have done a quad tree so if it is in no way the best way to do it I could use some tips. In order for an object to be inserted into the tree it must implement an interface that returns the position of the object. What is going on is a call is being made to insert 50 or so objects into the tree.
Code Snippetpublic
class QuadTreeNode : Collection{
int[] bounds;QuadTreeNode[] children;
private ArrayList elements; private int containerSize; private QuadTreeNode parent; public QuadTreeNode(int[] bounds, int containerSize, QuadTreeNode Parent){
this.containerSize = containerSize;elements =
new ArrayList(); this.bounds = new int[4];children =
new QuadTreeNode[4]; for(int i = 0; i < 4; i++){
children[i] =
null; this.bounds[i] = bounds[i];}
parent = Parent;
}
public int getContainerSize(){
return elements.Count;}
public ArrayList getContents(){
return elements;}
public ArrayList getContentsOfSubTree(){
ArrayList contents =
new ArrayList(); if((elements != null) && (elements.Count > 0)) return elements; else{
contents =
new ArrayList(); if(children[0] != null)contents.AddRange(children[0].getContentsOfSubTree());
if(children[1] != null)contents.AddRange(children[1].getContentsOfSubTree());
if(children[2] != null)contents.AddRange(children[2].getContentsOfSubTree());
if(children[3] != null)contents.AddRange(children[3].getContentsOfSubTree());
}
return contents;}
public void Insert(Element2D e){
if((e.getPos()[0] >= bounds[0]) && (e.getPos()[0] <= bounds[1])&&(e.getPos()[1] >= bounds[2]) && (e.getPos()[1] <= bounds[3]))
{
if((elements.Count < containerSize) &&(children[0] ==
null) &&(children[1] ==
null) &&(children[2] ==
null) &&(children[3] ==
null))elements.Add(e);
else{
splitContents();
switch(findQuadrant(e)){
case 0: if(children[0] == null)createChild(0);
children[0].Insert(e);
break; case 1: if(children[1] == null)createChild(1);
children[1].Insert(e);
break; case 2: if(children[2] == null)createChild(2);
children[2].Insert(e);
break; case 3: if(children[3] == null)createChild(3);
children[3].Insert(e);
break;}
}
}
elseparent.Insert(e);
}
public ArrayList searchWithinRange(double[] pos, double range){
ArrayList contents =
new ArrayList(); bool[] nearEdge = new bool[4];nearEdge[0] = isEdgeWithinRange(pos, 0, range);
nearEdge[1] = isEdgeWithinRange(pos, 1, range);
if(nearEdge[0] && nearEdge[1]){
nearEdge[2] = isEdgeWithinRange(pos, 2, range);
if(nearEdge[0] && nearEdge[1] && nearEdge[2])nearEdge[3] = isEdgeWithinRange(pos, 3, range);
}
if(nearEdge[0] && nearEdge[1] && nearEdge[2] && nearEdge[3]){
if((elements != null) && (elements.Count > 0)) return elements; if(children[0] != null)contents.AddRange(children[0].getContentsOfSubTree());
if(children[1] != null)contents.AddRange(children[1].getContentsOfSubTree());
if(children[2] != null)contents.AddRange(children[2].getContentsOfSubTree());
if(children[3] != null)contents.AddRange(children[3].getContentsOfSubTree());
}
else if(nearEdge[0] || nearEdge[1] || nearEdge[2] || nearEdge[3] ||((pos[0]>bounds[0])&&(pos[0]<bounds[1])&&(pos[1]>bounds[2])&&(pos[1]<bounds[3])))
{
if((elements != null) && (elements.Count > 0)) return elements; if(children[0] != null)contents.AddRange(children[0].searchWithinRange(pos, range));
if(children[1] != null)contents.AddRange(children[1].searchWithinRange(pos, range));
if(children[2] != null)contents.AddRange(children[2].searchWithinRange(pos, range));
if(children[3] != null)contents.AddRange(children[3].searchWithinRange(pos, range));
}
return contents;}
private int findQuadrant(Element2D e){
double[] pos = e.getPos(); if((pos[0] <= (bounds[0]+((bounds[1]-bounds[0])/2))) &&(pos[1] <= (bounds[2]+((bounds[3]-bounds[2])/2))))
return 0; else if ((pos[0] <= (bounds[0]+((bounds[1]-bounds[0])/2))) &&(pos[1] >= (bounds[2]+((bounds[3]-bounds[2])/2))))
return 1; else if ((pos[0] >= (bounds[0]+((bounds[1]-bounds[0])/2))) &&(pos[1] >= (bounds[2]+((bounds[3]-bounds[2])/2))))
return 2; else return 3;}
private void splitContents(){
foreach(Element2D e in elements){
int quadrant = findQuadrant(e); switch(quadrant){
case 0: if(children[0] != null)children[0].Insert(e);
else{
createChild(0);
children[0].Insert(e);
}
break; case 1: if(children[1] != null)children[1].Insert(e);
else{
createChild(1);
children[1].Insert( e);
}
break; case 2: if(children[2] != null)children[2].Insert(e);
else{
createChild(2);
children[2].Insert(e);
}
break; case 3: if(children[3] != null)children[3].Insert(e);
else{
createChild(3);
children[3].Insert(e);
}
break;}
}
elements.Clear();
}
private void createChild(int child){
switch(child){
case 0: int[] childBounds0 = {bounds[0],(bounds[0]+((bounds[1]-bounds[0])/2)),
bounds[2],
(bounds[2]+((bounds[3]-bounds[2])/2))};
children[0] =
new QuadTreeNode(childBounds0, containerSize, this); break; case 1: int[] childBounds1 = {bounds[0],(bounds[0]+((bounds[1]-bounds[0])/2)),
(bounds[2]+((bounds[3]-bounds[2])/2)),
bounds[3]};
children[1] =
new QuadTreeNode(childBounds1, containerSize, this); break; case 2: int[] childBounds2 = {(bounds[0]+((bounds[1]-bounds[0])/2)),bounds[1],
(bounds[2]+((bounds[3]-bounds[2])/2)),
bounds[3]};
children[2] =
new QuadTreeNode(childBounds2, containerSize, this); break; case 3: int[] childBounds3 = {(bounds[0]+((bounds[1]-bounds[0])/2)),bounds[1],
bounds[2],
(bounds[2]+((bounds[3]-bounds[2])/2))};
children[3] =
new QuadTreeNode(childBounds3, containerSize, this); break;}
}
private bool isEdgeWithinRange(double[] p, int edge, double range){
double[] line = new double[4]; switch(edge){
case 0:line[0] = bounds[0];
line[1] = bounds[2];
line[2] = bounds[0];
line[3] = bounds[3];
break; case 1:line[0] = bounds[0];
line[1] = bounds[3];
line[2] = bounds[1];
line[3] = bounds[3];
break; case 2:line[0] = bounds[1];
line[1] = bounds[3];
line[2] = bounds[1];
line[3] = bounds[2];
break; case 3:line[0] = bounds[1];
line[1] = bounds[2];
line[2] = bounds[0];
line[3] = bounds[2];
break;}
double u = ((p[0]-line[0])*(line[2]-line[0])+(p[1]-line[1])*(line[3]-line[1]))/Math.Pow(Math.Sqrt((line[2]-line[0])*(line[2]-line[0])+(line[3]-line[1])*(line[3]-line[1])),2);
double interceptx = line[0]+u*(line[2]-line[0]); double intercepty = line[1]+u*(line[3]-line[1]); if((u < 1) && (u > 0) &&(Math.Sqrt((interceptx-p[0])*(interceptx-p[0])+(intercepty-p[1])*(intercepty-p[1])) < range) ||
(Math.Sqrt((line[0]-p[0])*(line[0]-p[0])+(line[1]-p[1])*(line[1]-p[1])) < range) ||
(Math.Sqrt((line[2]-p[0])*(line[2]-p[0])+(line[3]-p[1])*(line[3]-p[1])) < range))
return true; else return false;}
public QuadTreeNode getChild(int index){
return children[index];}
public void Remove(Element2D e){
if(elements.Contains(e))elements.Remove(e);
elsechildren[
this.findQuadrant(e)].Remove(e);}
public void updateElement(Element2D e, float newX, float newZ){
if(elements.Count == 0)children[
this.findQuadrant(e)].updateElement(e, newX, newZ); else{
if(elements.Contains(e)){
if((e.getPos()[0] < bounds[0]) || (e.getPos()[0] > bounds[1])||(e.getPos()[1] < bounds[2]) || (e.getPos()[1] > bounds[3]))
{
elements.Remove(e);
e.setPos(newX, newZ);
parent.Insert(e);
}
}
}
}
Perhaps I am taking up to much of the stack with local variables in the methods. Am I being incredibly inefficient with this stuff? But I still dont understand how it can finish when debugging and not otherwise.
Thanks for the help dude, this has been irking me.
#4; Wed, 12 Sep 2007 22:40:00 GMT
I browsed through the code and didn't really find anything. Where do you get the stack overflow?
Do you have some code to reproduce the stack overflow? Sometimes its the data and code together that causes the overflow and not only the code.
#5; Wed, 12 Sep 2007 22:41:00 GMT
I think u can attach the application to windbg and get a dump, and use >kb command to get the call stack.
this can give u exact function to find the erroronius loop.
kirann
#6; Wed, 12 Sep 2007 22:42:00 GMT