QuadTree for collision detection

I was recently working on a game using the SFML library, Later on, I experienced performance issues due to collision detection. I have been told to use a QuadTree structure to optimize the collision detection. I have implemented the basic of the QuadTree functionality and it seems work fine in my game. The full project is available here. I would like to know how I can improve it.

QuadTree.hpp

#pragma once

#include "SceneNode.hpp"

#include 

class QuadTree final : private sf::NonCopyable
{
    static const auto DefaultNodes  = 4u;
    using Ptr                       = std::unique_ptr;
    using ChildrenContainer         = std::array;
    using ObjectsContainer          = std::vector;

public:
    explicit                QuadTree(std::size_t Level, const sf::FloatRect& Bounds);
                            ~QuadTree();

    void                    clear();
    void                    insert(SceneNode& object);
    void                    getCloseObjects(const sf::FloatRect& Bounds, ObjectsContainer& returnObjects);

private:
    void                    split();
    int                     getIndex(const sf::FloatRect& Rect);

private:
    ObjectsContainer        mObjects;
    ChildrenContainer       mChildren;

    sf::FloatRect           mBounds;
    std::size_t             mlevel;
};

QuadTree.cpp

```
#include "QuadTree.hpp"

namespace
{
constexpr auto MaxLevels = 5u;
constexpr auto MaxObjects = 2u;
}

QuadTree::QuadTree(std::size_t Level, const sf::FloatRect& Bounds)
: mObjects()
, mChildren()
, mBounds(Bounds)
, mlevel(Level)
{
}

QuadTree::~QuadTree()
{
clear();
}

void QuadTree::clear()
{
mObjects.clear();

for (auto&& child : mChildren)
{
if (child != nullptr)
{
child->clear();
child.reset(nullptr);
}
}
}

void QuadTree::split()
{
auto width = mBounds.width / 2.f;
auto height = mBounds.height / 2.f;
auto x = mBounds.left;
auto y

destructor / clear()

You don't actually need the destructor. Everything will be cleaned up just fine anyway.

Your clear() function could also be simplified a bit:

void QuadTree::clear()
{
    mObjects.clear();

    for (auto& child : mChildren) // Use a &, since that's what you need...
        // Reset this node's children. everything else happens through destructors. :)
        // No need for a nullptr argument either, just use the default argument.
        child.reset(); 
}

Similar comparisons with nullptr can be avoided later too. Just use the bool conversion that unique_ptr provides.

split()

In your split() function, you don't need the calls to std::move.

getIndex()

The getIndex checks are a little weird. You check that both sides of the bounds are within the top or left quadrant, but then only check one side for the bottom and right quadrants. If the bounds can't (or shouldn't) have a negative height, you only need to check one side (maybe add an assert() to check for negative sizes). If the bounds can have a negative height, then you need to check both sides for all the quadrants.

Instead of hardcoding quadrant indices, you should use an enum, e.g.:

enum class Quadrant
{
    TopLeft, TopRight,
    BottomLeft, BottomRight,
    NotFound,
};

Alternatively, you could make the index a bitmask instead. This needs two bits, one for top / bottom, and one for left / right. The -1 failure result should also be a constant instead of hardcoded. Then your getIndex function becomes something like this:

int QuadTree::getIndex(const sf::FloatRect& Rect)
{
    assert(Rect.height >= 0.f);
    assert(Rect.width  >= 0.f);

    auto verticalMidpoint   = mBounds.left + mBounds.width / 2.f;
    auto horizontalMidpoint = mBounds.top + mBounds.height / 2.f;

    // Can the object "completely" fit within this quadrant?
    bool top = (Rect.top + Rect.height  horizontalMidpoint);
    bool left = (Rect.left + Rect.width  verticalMidpoint);

    if ((top || bottom) && (left || right))
        return (top << 0) | (left << 1);

    // This is still -1, but make it a constant static variable or something!
    return IndexNotFound;
}

I would even be tempted to separate out the error code from the index entirely, make this function return a bool, and add a reference argument to return the index. Then you could use size_t for the index type instead of int (maybe add an Index typedef to the class).

Note that the checks don't actually ensure that the object does completely fit in a quadrant. It just checks which side of the center line the rect is on. This might be fine (I think it only affects the edge quadrants?) but it's something to think about.

insert()

I would suggest using an mHasChildren boolean value, instead of checking the first child for a nullptr every time. Set mHasChildren to false in the constructor, and change it to true in split(). If you don't want the additional bool, then put the null first element check in a hasChildren() member function.

I don't think your insert() logic is correct:

if (mObjects.size()  MaxLevels)
    return;

mLevel should never be greater than MaxLevels... Also, you need to think about exactly when you want to do the splitting and moving objects (only once!).

I would use remove_if to move / erase the objects. If you define a lambda function to return true / false if the object was moved, then you'll see a similarity with the first part of the function (getting the index and calling insert on a child). This can be abstracted to a private member function, leaving you with something like this:

// Make this private...
bool QuadTree::insertInChild(SceneNode* object)
{
    assert(mHasChildren);

    auto index = getIndex(object.getBoundingRect());

    if (index == IndexNotFound)
        return false;

    mChildren[index]->insert(object);
    return true;
}

// You might find it cleaner in the long run for this function to take a pointer too...
void QuadTree::insert(SceneNode& object)
{
    if (mHasChildren && insertInChild(&object))
        return;

    mObjects.push_back(&object);

    // This node is already split, and we can't move any objects down.
    if (mHasChildren)
        return;

    // Can't split this node, so no point checking number of objects.
    if (mlevel == MaxLevel)
        return;

    // Don't need to split this node yet.
    if (mObjects.size() < MaxObjects)
        return;

    split();

    mObjects.erase(
        std::remove_if(mObjects.begin(), mObjects.end(), 
            [this] (SceneNode* o) { return insertInChild(o); }),
            //std::bind(&QuadTree::insertInChild, this, std::placeholders::_1)), // same thing...
        mObjects.end());
}

getCloseObjects would probably be cleaner if you only call getIndex if the node actually has children:

```
void QuadTree::getCloseObjects(const sf::FloatRect& Bounds, ObjectsContainer& returnObjects)
{
if (mHasChildren)
{
auto index = getIndex(Bou

StackExchange Code Review Q#107167, answer score: 4