Solved

# Quad Tree Help in C++

Posted on 2004-11-19
1,288 Views
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

LVL 9

Accepted Solution

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){
}

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

LVL 2

Author Comment

Here is my code and it doesn't work. PLEASE! I need to get insert working. Please I need help! Someone out there! Please!

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

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

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

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

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.