Quadtree Node -> pointers to the children node

[yahn]

This is what I have, but I don't think it's right:

In the hpp file I have:
mChildren **Node;

and in the c++ file

when I want to create the children:
*mChildren = new Node[4];

and when I want to access the children nodes:
mChildren[i]...

To me, that doesn't seem right. Is that what it should be?

Thank you

[Perspective]

There's no reason for the children array to be 2-dimensional.

mChildren* Node;
mChildren = new Node[4];
mChildren[i] = ith child node. (which needs to be created as well)

[yahn]

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

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

#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