Quad Tree Help in C++

Alright, I am going to start this question at 500 points. If I get the answer I need I will boost the points to 1000. I need this question answered. So here goes.

you have this:
class point
{
public:
      float x, y;
}

class rect
{
public:
      float minx, miny, maxx, maxy;
}

class QNode
{
      point pt;
      rect bbox;
      vector<point> points;
      QNode* ne, nw, se, sw;
}

Question. I have a quad tree class that starts off with the root (QNode*) point to a Node with a point 0,0. How do I insert a Node into the tree?

Code would help, if the answer gets me to the point where I have a working insert function I will give whoever answers it 1000 points. Thank you for any help
LVL 2
LinkyAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

jhshuklaCommented:
first, you should add a few public functions to QNode:
class QNode
{
public:
  RETURN_TYPE  insert (QNode);

  RETURN_TYPE  getNE();
  RETURN_TYPE  getNW();
  RETURN_TYPE  getSE();
  RETURN_TYPE  getSW();
  RETURN_TYPE  getBounds();
  RETURN_TYPE  getPoint();

  // similar functions for setting values

private:
  point pt;
  rect bbox;
  vector<point> points;
  QNode* ne, nw, se, sw;
};

RETURN_TYPE QNode::insert (QNode node){
  if(node.pt.x > pt.x && node.pt.y > pt.y){
    if(ne == NULL)  ne = new QNode(node); //see note
    else ne->insert (node);
    return RETURN_TYPE_VARIABLE;
  }
  if(node.pt.x < pt.x && node.pt.y > pt.y){    //for nw  }
  if(node.pt.x > pt.x && node.pt.y < pt.y){    //for se  }
  if(node.pt.x < pt.x && node.pt.y < pt.y){    //for sw  }
/*
you might want additional check to see if the new node is within bounding box
or might want to update the inserted node's bbox to reflect the area covered
*/
}

NOTE:
the copy constructor will create an exact copy of the original node. in many cases you want it to be that way but almost never when you have pointers as data members. the reason is that, if you free memory from one pointer, the other pointer is still pointing to the same memory location and there is no way for you to know whether that a valid memory somewhere later in the program. look at this example
------------------8<-----------------------------
class pointer {
public:
  int * p;
};

pointer p1, p2;
p1.p = new int;
p2.p = p1.p;
...
delete p1.p;
...
p2.p = 100;            <<<<<<<<<<<< runtime error
------------------>8-----------------------------
if you don't want this behavior, then you have to write your own copy constructor. inside you have two options: (1) make the pointers NULL; (2) copy the tree recursively. here is the prototype:

class QNode{
public:
  QNode(QNode);
...
};

QNode::QNode(QNode node){
  ... your code ...
}

this is not a fully working solution but with the information so far provided and not knowing how exactly you want to insert I cannot help more than this. I also noted that semicolons are missing at the end of class declarations.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
LinkyAuthor Commented:
Here is my code and it doesn't work. PLEASE! I need to get insert working. Please I need help! Someone out there! Please!


#ifndef QUADTREE_H_
#define QUADTREE_H_

// POINT CLASS DEFINITION
class point
{
public:
      point()                                          // defualt constructor
            : x(0), y(0),vx(0), vy(0), m(0) { }
      point(double x_, double y_)            // assignment constructor
            : x ( x_ ), y ( y_ ) { }
      // Copy-Constructor
      point( double x_, double y_, double vx_, double vy_, double m_, string n_)
            : x(x_), y(y_), vx(vx_), vy(vy_), m(m_), n(n_) { }

      double x; double y; double vx; double vy; double m; string n;
      
};

// RECT CLASS DEFINITION
class rect
{
public:
      rect()
            : minx ( 0 ), miny ( 0 ), maxx ( 0 ), maxy ( 0 ) { }
      rect(double mx, double my, double mxx, double mxy)
            : minx ( mx ), miny ( my ), maxx ( mxx ), maxy ( mxy ) { }
      rect(double x, double y)
            : minx( 0 ), miny( 0 ), maxx ( x ), maxy ( y ) { }

      double minx;      // minimum x value
      double miny;      // minimum y value
      double maxx;      // maximum x value
      double maxy;      // maximum y value
};

rect quadsplit( const rect & bound, int q );
bool inbox( const rect & bound, const point & pt );
int checkquad( const rect & bound, const point & pt );

rect quadsplit( const rect & bound, int q )
{
      if( q == 0 )
            return rect( ( bound.maxx / 2 ), ( bound.maxy / 2 ), bound.maxx, bound.maxy );
      else if( q == 1 )
            return rect( bound.minx , ( bound.maxy / 2 ), ( bound.maxx / 2 ), bound.maxy );
      else if( q == 2 )
            return rect( bound.minx, bound.miny, ( bound.maxx / 2 ), ( bound.maxy / 2 ) );
      else if( q == 3 )
            return rect( ( bound.maxx / 2 ), bound.miny, bound.maxx, ( bound.maxy / 2 ) );
      return rect(0,0,0,0);
}

bool inbox( const rect & bound, const point & pt )
{

      if(pt.x < bound.minx)
            return false;
      if(pt.y < bound.miny)
            return false;
      if(pt.x > bound.maxx)
            return false;
      if(pt.y > bound.maxy)
            return false;

      return true;
}

int checkquad( const rect & bound, const point & pt )
{
      int count = 0;
      int prev = -1;
      vector<rect> splitbound;
      vector<bool> grid;

      splitbound.push_back(quadsplit(bound, 0));
      splitbound.push_back(quadsplit(bound, 1));
      splitbound.push_back(quadsplit(bound, 2));
      splitbound.push_back(quadsplit(bound, 3));
      
      grid.push_back(false); grid.push_back(false);
      grid.push_back(false); grid.push_back(false);

      for(int i = 0; i < splitbound.size(); i++)
      {
            if(inbox(splitbound[i], pt))
            {
                  grid[i] = true;
                  count++;
                  prev = i;
            }
      }
      if(count > 1)
      {
            if(grid[0] == true && grid[1] == true && grid[2] == true && grid[3] == true)
                  return 2;
            if(grid[0] == true && grid[1] == true)
                  return 1;
            if(grid[2] == true && grid[3] == true)
                  return 2;
            if(grid[1] == true && grid[2] == true)
                  return 2;
            if(grid[0] == true && grid[3] == true)
                  return 3;
      }

      return prev;
}



// QUAD TREE NODE
class QNode
{
public:
      QNode()            // default constructor
            : ne ( NULL ), nw ( NULL ), se ( NULL ), sw ( NULL ), full( false ) { }

      QNode* ne; QNode* nw; QNode* se; QNode* sw;
      point pt;
      rect bound;
      bool full;      
};

// QUAD TREE CLASS
class QTree
{
public:
      QTree();
      QTree( double x, double y );
      ~QTree();

      void insert( const point & pt );
      bool isleaf( const QNode* & p );
      int size() { return size_; }
      void print() { print( root ); }
      void printroot() { cout << "ROOT: " << root->pt.x << endl; }
private:
      QNode* root;
      int size_;
      QNode* q;
      bool ins;
      point extra;

      void insert( const point & pt, QNode* & p);
      
      void split( QNode* & p);
      void print( QNode* & p);
};

QTree::QTree()
{
      root = new QNode;
      size_ = 0;
      ins = false;
      point extra;

      rect bbox(2.50e11, 2.50e11);
      root->bound = bbox;
}

QTree::QTree( double x, double y )
{
      root = new QNode;
      size_ = 0;
      ins = false;

      rect bbox(x, y);
      root->bound = bbox;
}

QTree::~QTree()
{
}

void QTree::insert( const point & pt )
{
      q = NULL;
      insert( pt, root );

}

void QTree::insert( const point & pt, QNode* & p )
{

}

void QTree::split( QNode* & p )
{
      p->ne = new QNode; p->nw = new QNode;
      p->sw = new QNode; p->se = new QNode;
      p->ne->bound = quadsplit( p->bound, 0 );
      p->nw->bound = quadsplit( p->bound, 1 );
      p->sw->bound = quadsplit( p->bound, 2 );
      p->se->bound = quadsplit( p->bound, 3 );
}

void QTree::print( QNode* & p)
{
      if(p->ne == NULL)
      {
            cout << "POINT: " << p->pt.x << " " << p->pt.y << endl;
      }
      else
      {
            print( p->ne ); print( p->nw ); print( p->sw ); print( p->se );
      }
}

bool QTree::isleaf( const QNode* & p )
{
      if(p->ne != NULL)
            return false;
      if(p->nw != NULL)
            return false;
      if(p->sw != NULL)
            return false;
      if(p->se != NULL)
            return false;
      return true;
}
#endif
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.