Quadtree Node -> pointers to the children node

This is a discussion on Quadtree Node -> pointers to the children node within the C++ Programming forums, part of the General Programming Boards category; This is what I have, but I don't think it's right: In the hpp file I have: mChildren **Node; and ...

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    137

    Quadtree Node -> pointers to the children node

    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

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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)

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    137
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  2. Replies: 7
    Last Post: 06-16-2006, 09:23 PM
  3. Big help in Astar search code...
    By alvifarooq in forum C++ Programming
    Replies: 6
    Last Post: 09-24-2004, 11:38 AM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  5. Dynamic list of Objects in External File
    By TechWins in forum C++ Programming
    Replies: 3
    Last Post: 12-18-2002, 01:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21