I know this is a lot to ask, but can anyone verify that this is, in fact, a working quadtree? It took me a long time to get it to "work." I don't know how to make sure that I did everything right, though. I suspect I probably did something wrong. I would really appreciate if you could look at this.
Thank you
Code:
#include "quadtree.hpp"
Node::Node() {
mBucketSize = 4;
mParent = NULL;
}
Node::Node(double x, double y, double w, double h, unsigned int bucketSize, Node *parent) {
mBucketSize = bucketSize;
mX = x;
mY = y;
mW = w;
mH = h;
mParent = parent;
}
Node::~Node() {
if (mChildren.size() > 0) {
for (int i = 0; i < 4; i++) {
delete mChildren[i];
}
}
}
void Node::setX(double x) {
mX = x;
}
double Node::getX() {
return mX;
}
void Node::setY(double y) {
mY = y;
}
double Node::getY() {
return mY;
}
void Node::setW(double w) {
mW = w;
}
double Node::getW() {
return mW;
}
void Node::setH(double h) {
mH = h;
}
double Node::getH() {
return mH;
}
std::list<Item *> *Node::getBucket() {
return &mBucket;
}
void Node::spill(Item *item) {
if (mChildren.size() > 0) {
return;
}
mChildren.push_back(new Node(mX , mY , mW/2, mH/2, mBucketSize, this));
mChildren.push_back(new Node(mX + mW/2, mY , mW/2, mH/2, mBucketSize, this));
mChildren.push_back(new Node(mX , mY + mH/2, mW/2, mH/2, mBucketSize, this));
mChildren.push_back(new Node(mX + mW/2, mY + mH/2, mW/2, mH/2, mBucketSize, this));
// add this item
traverse(item->mX, item->mY)->addItem(item);
// add existing items
while (!mBucket.empty()) {
Item *tItem = mBucket.front();
mBucket.pop_front();
traverse(tItem->mX, tItem->mY)->addItem(tItem);
}
}
void Node::merge() {
unsigned int items = 0;
for (int i = 0; i < 4; i++) {
items += mChildren[i]->getBucket()->size();
}
if (items <= mBucketSize) {
for (int i = 0; i < 4; i++) {
mBucket.splice(mBucket.end(), *mChildren[i]->getBucket());
delete mChildren[i];
}
mChildren.erase(mChildren.begin(), mChildren.end());
}
}
void Node::addItem(Item *item) {
if (mBucket.size() < mBucketSize) {
mBucket.push_back(item);
} else {
spill(item);
}
}
void Node::removeItem(Item *item) {
mBucket.remove(item);
if (mParent != NULL) {
mParent->merge();
}
}
Node *Node::traverse(int x, int y) {
if (mChildren.size() == 0) {
return this;
}
double cX1, cY1, cX2, cY2;
for (int i = 0; i < 4; i++) {
cX1 = mChildren[i]->getX();
cY1 = mChildren[i]->getY();
cX2 = cX1 + mChildren[i]->getW();
cY2 = cY1 + mChildren[i]->getH();
if (x >= cX1 && y >= cY1 && x <= cX2 && y <= cY2) {
return mChildren[i]->traverse(x, y);
}
}
return NULL;
}
Quadtree::Quadtree(int x, int y, int w, int h, unsigned int bucketSize) {
rNode = new Node(x, y, w, h, bucketSize, NULL);
mBucketSize = bucketSize;
}
Quadtree::~Quadtree() {
if (rNode != NULL) {
delete rNode;
}
}
void Quadtree::addItem(Item *item) {
if (item->mX >= rNode->getX() && item->mY >= rNode->getY() && item->mX <= rNode->getX() + rNode->getW() && item->mY <= rNode->getX() + rNode->getH()) {
rNode->traverse(item->mX, item->mY)->addItem(item);
}
}
void Quadtree::removeItem(Item *item) {
if (item->mX >= rNode->getX() && item->mY >= rNode->getY() && item->mX <= rNode->getX() + rNode->getW() && item->mY <= rNode->getX() + rNode->getH()) {
rNode->traverse(item->mX, item->mY)->removeItem(item);
}
}
Node *Quadtree::findNode(Item *item) {
return rNode->traverse(item->mX, item->mY);
}
Code:
#ifndef QUADTREE_HPP_INCLUDED
#define QUADTREE_HPP_INCLUDED
#include <vector>
#include <list>
class Item {
public:
int mX;
int mY;
double mID;
};
class Node {
private:
double mX;
double mY;
double mW;
double mH;
unsigned int mBucketSize;
Node *mParent;
std::vector<Node *> mChildren;
std::list<Item *> mBucket;
public:
Node();
Node(double x, double y, double w, double h, unsigned int bucketSize, Node *parent);
~Node();
void setX(double x);
double getX();
void setY(double y);
double getY();
void setW(double w);
double getW();
void setH(double h);
double getH();
std::list<Item *> *getBucket();
void spill(Item *item);
void merge();
void addItem(Item *item);
void removeItem(Item *item);
Node *traverse(int x, int y);
};
class Quadtree {
private:
Node *rNode;
unsigned int mBucketSize;
public:
Quadtree(int x, int y, int w, int h, unsigned int bucketSize);
~Quadtree();
void addItem(Item *item);
void removeItem(Item *item);
Node *findNode(Item *item);
};
#endif // QUADTREE_HPP_INCLUDED