Quadtree implementation

I've implemented a quadtree in C++. Ignore any apparent similarity to the pseudocode on Wikipedia, it's all in your head, I swear.

How can I improve it? Algorithm speed/space improvements, any extra functions that I'm likely to want... as well as general practice.

```
#ifndef _QUADTREE_H_
#define _QUADTREE_H_

#include
#include

struct Point
{
float x, y;
Point(float x = 0, float y = 0):x(x), y(y){};
};

struct AABB
{
Point centre;
Point halfSize;

AABB(Point centre = Point(), Point halfSize = Point()): centre(centre), halfSize(halfSize){};

bool contains(Point a)
{
if(a.x centre.x - halfSize.x)
{
if(a.y centre.y - halfSize.y)
{
return true;
}
}
return false;
}

bool intersects(AABB other)
{
//this right > that left this left other.centre.x - other.halfSize.x || centre.x - halfSize.x that top
if(centre.y + halfSize.y > other.centre.y - other.halfSize.y || centre.y - halfSize.y
struct Data
{
Point pos;
T* load;

Data(Point pos = Point(), T* data = NULL): pos(pos), load(data){};
};

template
class Quadtree
{
private:
//4 children
Quadtree* nw;
Quadtree* ne;
Quadtree* sw;
Quadtree* se;

AABB boundary;

std::vector > objects;

int CAPACITY;
public:
Quadtree();
Quadtree(AABB boundary);

~Quadtree();

bool insert(Data d);
void subdivide();
std::vector > queryRange(AABB range);
};

template
Quadtree::Quadtree()
{
CAPACITY = 4;
nw = NULL;
ne = NULL;
sw = NULL;
se = NULL;
boundary = AABB();
objects = std::vector >();
}

template
Quadtree::Quadtree(AABB boundary)
{
objects = std::vector >();
CAPACITY = 4;
nw = NULL;
ne = NULL;
sw = NULL;
se = NULL;
this->boundary = boundary;
}

template
Qua

Ok, so here we go for a few tips:

-
Several methods such as AABB::contains and AABB::intersects do not modify the AABB instance they are called with. Therefore, you should const-qualify these methods to make sure that they can also be called in a const context.

bool intersects(AABB other) const { /* ... */ }
                            ^^^^^

-
As pointed by @glampert in the comments, an AABB instance wheights four floats, so it's becoming quite heavy compared to a built-in type. Therefore, when you pass it to a function, you might want to pass it by const reference instead of passing it by value if you only plan to read from it without modifying it:

bool intersects(const AABB& other) const { /* ... */ }
                ^^^^^     ^

-
_QUADTREE_H_ begins with an underscore followed by a capital letter. Therefore, it is an identifier reserved to the implementation. To fix this, the simplest thing to do is to drop the leading underscore and use QUADTREE_H_ instead.

-
Wherever possible (hint: always), use nullptr instead of NULL to avoid subtle and tricky overload problems.

-
From C++11 onward, you can write Point pos = {} instead of Point pos = Point() to default-initialize the Point. It is terser and incurs less changes if you ever want to change the class name.

-
You can also drop the class name when you declare and initialize at once thanks to C++11 uniform initialization:

Point qSize = { boundary.halfSize.x, boundary.halfSize.y };

Note that in this case, what you actually want to write is probably this:

Point qSize = boundary.halfSize;

As a size note, if you need to do more Point/Vector arithmetics, you better implement the full classes and overload the operators to gain in readability and avoid having to write everything coordinate-by-coordinate everytime you need to perform a simple operation.

-
If CAPACITY is never meant to change, you could make it a static constexpr member variable. Also, I wouldn't use ALLCAPS_CASE for its name, which is a case that we generally use to denote the use of macros.

static constexpr int capacity = 4;

-
Try to use the constructor initialization list when you can so that the compiler does not have to assign values to variable after the object is constructed:

template 
Quadtree::Quadtree():
    nw{nullptr},
    ne{nullptr},
    sw{nullptr},
    se{nullptr}
{}

You don't have to explicitly default-initialize the other parameters since they will be default-initialized anyway if you don't write anything.

-
You have an old C-style for loop with indices-based iteration here:

for(int i = 0; i < objects.size(); i++)
{
    if(range.contains(objects.at(i).pos))
    {
        pInRange.push_back(objects.at(i));
    }
}

I am sure that you will like the C++11 range-based for loop:

for(auto&& object: objects)
{
    if(range.contains(object.pos))
    {
        pInRange.push_back(object);
    }
}

Hey, it's terser and you don't have to fear off-by-one iteration errors anymore :)

-
Also, you wondered whether in-class initializer were C++14. Good news, they are avaible in C++11. They were only slightly upgraded to cover more obscure cases in C++14, so you can totally write your Point class like this:

struct Point
{
    float x = 0.0f;
    float y = 0.0f;
};

The constructor will then use the in-class initializers to initialize the structure. Note that I changed 0 to 0.0f which is the correct literal for float. While correct literals are generally not that relevant, getting them right becomes more and more important in a type-deducing C++ world.

StackExchange Code Review Q#84374, answer score: 22