• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1362
  • Last Modified:

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
0
Linky
Asked:
Linky
1 Solution
 
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
 
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

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Tackle projects and never again get stuck behind a technical roadblock.
Join Now