Weird issue with a quadtree implementation in C-CodePudding

Below is the script for the quadtree... I'm relatively new to the concept of pointers, so my guess is that I have done something wrong with a double pointer, or something along those lines!

#include "BoidQuadTree.h"
#include <iostream>

Quad::Quad(float boundary_TL_x, float boundary_TL_y, float boundary_BR_x, float boundary_BR_y, unsigned short max_Nodes, unsigned short max_Depth)
{
    this->max_Depth = new unsigned short(max_Depth);
    this->max_Nodes = new unsigned short(max_Nodes);
    this->nodes_Remaining = new unsigned short(max_Nodes);

    this->boundary_TL = new Vector(boundary_TL_x, boundary_TL_y);
    this->boundary_BR = new Vector(boundary_BR_x, boundary_BR_y);

    this->TL = nullptr; // no need to allocate memory yet
    this->TR = nullptr;
    this->BL = nullptr;
    this->BR = nullptr;

    this->boids = new Boid*[max_Nodes]; // Intitialise all pointers to nullptr
}

Quad::~Quad()
{
    if (this->TL == nullptr) { // only deleted if not branched
        delete this->max_Depth;
        delete this->max_Nodes;
        delete[] this->boids;
    }

    delete this->boundary_TL; // always deleted
    delete this->boundary_BR;
    delete this->TL;
    delete this->TR;
    delete this->BL;
    delete this->BR;
    delete this->nodes_Remaining;
}

bool Quad::Insert(Boid* boid)
{
    if (boid != nullptr) {
        if (this->InBoundary(boid->position)) {
            if (this->TL == nullptr) {
                if ((*this->nodes_Remaining) > 0) { // if there is a free position
                    this->boids[(*(this->max_Nodes)) - (*(this->nodes_Remaining))] = boid;
                    (*(this->nodes_Remaining)) -= 1;
                    std::cout << "inserted" << std::endl;
                    return true; // successfully inserted boid pointer
                }
                else { // no free positions in current quad...
                    if (*this->max_Depth > 1) { // Further depth still avaliable, therefore branch all boid pointers into new quads! (can delete boid data from this after branching to free space)
                        this->TL = new Quad(this->boundary_TL->x, this->boundary_TL->y, this->boundary_TL->x   (this->boundary_BR->x / 2), this->boundary_TL->y   (this->boundary_BR->y / 2), *(this->max_Nodes), *(this->max_Depth) - 1);
                        this->TR = new Quad(this->boundary_TL->x   (this->boundary_BR->x / 2), this->boundary_TL->y, this->boundary_BR->x, this->boundary_TL->y   (this->boundary_BR->y / 2), *(this->max_Nodes), *(this->max_Depth) - 1);
                        this->BL = new Quad(this->boundary_TL->x, this->boundary_TL->y   (this->boundary_BR->y / 2), this->boundary_TL->x   (this->boundary_BR->x / 2), this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);
                        this->BR = new Quad(this->boundary_TL->x   (this->boundary_BR->x / 2), this->boundary_TL->y   (this->boundary_BR->y / 2), this->boundary_BR->x, this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);

                        std::cout << "Branched!" << std::endl;

                        for (unsigned short i = 0; i < *(this->max_Nodes); i  ) {
                            this->PushToBranch(this->boids[i]);
                        }
                        this->PushToBranch(boid);

                        delete[] this->boids; // Delete now unneeded data
                        delete this->max_Nodes;
                        delete this->max_Depth;

                        return true;
                    }
                    else {
                        std::cout << "FUNC LOCATION : Quad::Insert() ERROR! Not enough depth to insert boid pointer! Returning false." << std::endl;
                        std::cout << boid->position->x << " " << boid->position->y << std::endl;
                        return false;
                    }
                }
            }
            else { // this quad has branched
                this->PushToBranch(boid);
                std::cout << "inserted into branch" << std::endl;
            }
        }
        else {
            std::cout << "FUNC LOCATION : Quad::Insert() ERROR! Boid not inside the valid range of the quadtree! Returning false." << std::endl;
            return false;
        }
    }
    else {
        std::cout << "FUNC LOCATION : Quad::Insert() ERROR! Attempted to insert a nullptr! Returning false." << std::endl;
        return false;
    }
}

void Quad::Insert(Boid** boids_Array, unsigned int number_Of_Boids)
{
    for (unsigned int i = 0; i < number_Of_Boids; i  ) {
        this->Insert(boids_Array[i]);
    }
}

bool Quad::InBoundary(Vector* position)
{
    if (position->x >= this->boundary_TL->x && position->x <= this->boundary_BR->x && position->y >= this->boundary_TL->y && position->y <= this->boundary_BR->y) {
        return true;
    }
    else {
        return false;
    }
}

void Quad::PushToBranch(Boid* boid) // determines where to insert() boid (to be used on boids that are already checked to be in radius!), and 
{
    if (boid->position->x <= this->boundary_TL->x   (this->boundary_BR->x / 2)) {
        if (boid->position->y <= this->boundary_TL->y   (this->boundary_BR->y / 2)) { // TL
            this->TL->Insert(boid);
        }
        else { // BL
            this->BL->Insert(boid);
        }
    }
    else {
        if (boid->position->y <= this->boundary_TL->y   (this->boundary_BR->y / 2)) { // TR
            this->TR->Insert(boid);
        }
        else { // BR
            this->BR->Insert(boid);
        }
    }
}

The main issue is that it works fine for a very small number of boids, but if i Insert() even 10 (with different randomised positions that are well within the scope of the tree) to a quadtree with a max_Depth of 100 and a max_Nodes value of 1 or 2, i end up with hundreds of branches and around 20 depth errors which makes no sense? Any help would be much appreciated! I am losing my mind ;-;

CodePudding user response：

ahhh... i really am dumb xD i was calculating the boundaries of the branches incorrectly! thanks for all the help and feedback :)

updated calculation

this->TL = new Quad(this->boundary_TL->x, this->boundary_TL->y, (this->boundary_TL->x   this->boundary_BR->x) / 2, (this->boundary_TL->y   this->boundary_BR->y) / 2, *(this->max_Nodes), *(this->max_Depth) - 1);
this->TR = new Quad((this->boundary_TL->x   this->boundary_BR->x) / 2, this->boundary_TL->y, this->boundary_BR->x, (this->boundary_TL->y   this->boundary_BR->y) / 2, *(this->max_Nodes), *(this->max_Depth) - 1);
this->BL = new Quad(this->boundary_TL->x, (this->boundary_TL->y   this->boundary_BR->y) / 2, (this->boundary_TL->x   this->boundary_BR->x) / 2, this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);
this->BR = new Quad((this->boundary_TL->x   this->boundary_BR->x) / 2, (this->boundary_TL->y   this->boundary_BR->y) / 2, this->boundary_BR->x, this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);