2
\$\begingroup\$

I'm new on C++ and OOP. I wrote the following QuadTree implementation (I didn't wrote the remove object part yet).

please take a look on it and provide feedback, mainly about C++ OOP design, seperating my code to files, public vs. privte, shared_pt and etc...

QuadTree.h:

#pragma once
#include <iostream>
#include <utility>
#include <memory>

using namespace std;

class Point {
public:
    Point(double _x, double _y) : x(_x), y(_y) {};
    double x, y;
    void printPoint() { std::cout << "(" << x << "," << y << ")" << std::endl; }
};


class LifeFoam {
    int attribute;
    Point location;

public:
    LifeFoam(Point _location, int _attribute) : location(_location), attribute(_attribute) {};
    Point getLocation() { return(location); }
    int getAttribute() { return(attribute); }
};

class Node {
private:
    const Point lowerLeftCorner, upperRightCorner;
    const shared_ptr<Node> parent;
    shared_ptr<Node> upperRightChildPtr = nullptr, upperLeftChildPtr = nullptr, lowerRightChildPtr = nullptr, lowerLeftChildPtr = nullptr;
    LifeFoam* objectPtr = nullptr;

    //private helper methods
    Node* findRegion(Point point);
    bool bIsLeaf() { return(upperRightChildPtr == nullptr);}
    bool bPointInRegion(Point point) { return(point.x >= lowerLeftCorner.x && point.x <= upperRightCorner.x && point.y >= lowerLeftCorner.y && point.y <= upperRightCorner.y); }
    Node* findSubRegion(Point point);
    void seperateRegion(Node* nodeToSeperate);
    void moveCurrObjectToSubRegion();
public:
    void insertObject(LifeFoam* objPtr);
    //void removeObject(LifeFoam& obj);
    Node(const Point _lowerLeftCorner, const Point _upperRightCorner, const shared_ptr<Node> _parent) : lowerLeftCorner(_lowerLeftCorner), upperRightCorner(_upperRightCorner), parent(_parent) {};

    //public helper methods
    std::pair<const Point, const Point> getNodeVerticies() { return(make_pair(lowerLeftCorner, upperRightCorner)); };
    bool bIsEmpty() { return(objectPtr == nullptr); }
    int getObjectVal() { return(objectPtr->getAttribute()); }

    void setObject(LifeFoam* _objectPtr) { objectPtr = _objectPtr; }
    void setChildren(Node _upperRightChild, Node _upperLeftChild, Node _lowerRightChild, Node _lowerLeftChild) {
        upperRightChildPtr = make_shared<Node>(_upperRightChild);
        upperLeftChildPtr  = make_shared<Node>(_upperLeftChild);
        lowerRightChildPtr = make_shared<Node>(_lowerRightChild);
        lowerLeftChildPtr  = make_shared<Node>(_lowerLeftChild);
    }

};  

class QuadTree {
private:
    Node root;
public:
    QuadTree() : root(Point(0, 0), Point(100, 100), nullptr) {};
    QuadTree(Point upperRightEdge, Point lowerLeftEdge) : root(lowerLeftEdge, upperRightEdge, nullptr) {};
};

QuadTree.cpp:


#include <iostream>
#include <cassert>
#include "QuadTree.h"
using namespace std;

#define assertm(msg, exp)

Node* Node::findSubRegion(Point point) {
    assertm("out of bounds", bPointInRegion(x, y));

    Point refPoint = Point((lowerLeftCorner.x + upperRightCorner.x) / 2, (lowerLeftCorner.y + upperRightCorner.y) / 2);
    Node* subRegionPtr;
    if (point.x >= refPoint.x) {
        subRegionPtr = (point.y >= refPoint.y ? upperRightChildPtr.get() : lowerRightChildPtr.get());
    } else {
        subRegionPtr = (point.y >= refPoint.y ? upperLeftChildPtr.get() : lowerLeftChildPtr.get());
    }
    return(subRegionPtr);
}
Node* Node::findRegion(Point point) {
    assertm("out of bounds", bPointInRegion(point));
    if (bIsLeaf()) return(this);

    Node* subRegionPtr = findSubRegion(point);
    return(subRegionPtr->findRegion(point));
}

void Node::seperateRegion(Node* nodeToSeperate) {
    const std::pair<const Point, const Point> nodeToSeperateVerticies= nodeToSeperate->getNodeVerticies();
    const Point midVertex = Point((nodeToSeperateVerticies.first.x+ nodeToSeperateVerticies.second.x) / 2,
                                  (nodeToSeperateVerticies.first.y + nodeToSeperateVerticies.second.y) / 2);

    shared_ptr<Node> pp(nodeToSeperate);
    Node upperRightSubRegion = Node(midVertex, nodeToSeperateVerticies.second, pp);
    Node upperLeftSubRegion = Node(Point(nodeToSeperateVerticies.first.x, midVertex.y), Point(midVertex.x, nodeToSeperateVerticies.second.y), pp);
    Node lowerRightSubRegion = Node(Point(midVertex.x, nodeToSeperateVerticies.first.y), Point(nodeToSeperateVerticies.second.x, midVertex.y), pp);
    Node lowerLeftSubRegion = Node(nodeToSeperateVerticies.first, midVertex, pp);
    
    nodeToSeperate->setChildren(upperRightSubRegion, upperLeftSubRegion, lowerRightSubRegion, lowerLeftSubRegion);

}

void Node::moveCurrObjectToSubRegion() {

    Node* subRegionPtrForCurrentObject = findSubRegion(objectPtr->getLocation());
    subRegionPtrForCurrentObject->setObject(objectPtr);
    objectPtr = nullptr;
}

void Node::insertObject(LifeFoam* objPtr) {
    Point point = objPtr->getLocation();
    Node* currRegionForPoint = findRegion(point);
    if (currRegionForPoint->bIsEmpty()) {
        currRegionForPoint->setObject(objPtr);
    }
    else {
        seperateRegion(currRegionForPoint);
        currRegionForPoint->moveCurrObjectToSubRegion();

        Node* subRegionPtr = findSubRegion(point);
        subRegionPtr->insertObject(objPtr);
    }

}
\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

class QuadTree is useless

It's great that you created a type to represent a whole tree, instead of just having Node. However, your QuadTree isn't doing anything useful. It has constructors to initialize the private member variable root, but there are no other member functions to do anything with it.

Ideally, QuadTree has public member functions that allow you to modify and query the tree, and Node is just a private implementation detail of QuadTree. For example:

class QuadTree {
    class Node {
        …
    };

    Node root;

public:
    QuadTree(): root(…) {};
    …
};

As to what public member functions you want to add depends on what kind of things you want to do with this tree. For example, do you want to use this to store regions or to store points? Given that LifeFoam contains Point location, I suspect the latter. That means you probably want to add an addPoint() member function that takes a Point as a parameter and whatever attributes you want to store at that point.

Apart from adding points, you might want to query the tree. Do you want to know if a given point exists in the tree? Or want to get a list of all points within a certain region? Think about what you want and add those as member functions.

Remove knowledge of LifeFoam from the quadtree

Your Node has a LifeFoam* objectptr member variable. This hardcodes the type of data your tree can store. What if you need another quadtree for some other type of data? You can make your classes templates, just like std::vector, so you can store any kind of data:

template<typename T>
class QuadTree {
    class Node {
        …
        T data;
    };
    …
};

Now every node stores a piece of data, that you can decide elsewhere. For example, if you'd want to store pointers to LifeFoam, you could write:

QuadTree<LifeFoam*> quadTree;

However, I recommend that if you want a point quadtree, you store the Point location explicitly in Node:

template<typename T>
class QuadTree {
    class Node {
        …
        Point location;
        T data;
    };
    …
};

And then create an instance of your tree like so:

QuadTree<int> quadTree;

That gives your quadtree implementation access to the exact location of a node.

What to store in Node and how

There are several issues with the member variables of Node, that make it larger and less efficient than necessary.

First, consider that std::shared_ptrs are kind of heavy-weight smart pointers. Internally, they do atomic reference counting to ensure data is only freed when nothing else can use it anymore. However, there is a problem if you have a parent node containing std::shared_ptrs to its children, and the children containing a std::shared_ptr to the parent. This is a circular reference, and if you are not careful, this can cause a memory leak.

One solution would be to use a std::weak_ptr to store the pointer to the parent. However, nothing in your code actually uses the pointer to the parent. Do you really need it? If not, I would remove it. And in that case, you can turn the std::shared_ptrs holding the children into std::unique_ptrs, which are much simpler and more efficient.

Second, consider the lowerLeftCorner and upperRightCorner. It is not necessary to store that inside a Node. Instead, the region a Node covers can be reconstructed from its position in the quadtree. Consider having a findRegion() member function of QuadTree, which just takes a Point as a paremeter. But the QuadTree itself knows its size, and then passes that to Node's findRegion() member function, like so:

template<typename T>
class QuadTree {
    class Node {
        …
        Point location;
        T data;
    public:
        Node* findRegion(Point point, Point upperRightEdge, Point lowerLeftEdge);
    };
    
    Node root;
    Point upperRightEdge;
    Point lowerLeftEdge;

public:
    QuadTree(): upperRightEdge(0, 0), lowerLeftEdge(100, 100) {}
    Node* findRegion(Point point, Point upperRightEdge, Point lowerLeftEdge);
    …
};

QuadTree::Node* QuadTree::findRegion(Point point) {
    return root.findRegion(point, upperRightEdge, lowerLeftEdge);
}

QuadTree::Node* QuadTree::Node::findRegion(Point point, Point upperRightEdge, Point lowerLeftEdge) {
    if (isLeaf())
        return this;

    Point refPoint = …;
    Node* child;

    if (point.x >= refPoint.x) {
        lowerLeftEdge.x = refPoint.x;
        if (point.y >= refPoint.y) {
            lowerLeftEdge.y = refPoint.y;
            child = upperRightChildPtr.get();
        } else {
             …
        }
    } else {
        …
    }

    return child.findRegion(point, upperRightEdge, lowerLeftEdge);
}

It might seem like you are doing more work traversing the tree now, but it's actually very efficient: you already had to do the bulk of the calculation when calculating refPoint, and now it's just some addition assigning to the .x and .y coordinates of the local variables upperRightEdge and lowerLeftEdge. On modern CPUs, this will stay in registers, which is much more efficient than loading these values from memory. And since you no longer need to store this information in a Node, less memory is used, which means less memory bandwidth required and more of the cache is available for something else.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.