C++四叉树实现异常求助：插入Boid触发大量分支与深度错误

本人对指针概念较为生疏，推测问题源于指针操作失误。当前实现的四叉树在插入极少量Boid时运行正常，但当max_Depth设为100、max_Nodes设为1或2，插入10个位置合法的随机Boid时，会出现数百个分支及约20个深度错误。

四叉树实现代码 #

#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);
        }
    }
}

问题根源及修复方案 #

1. 子象限边界计算错误 #

问题：创建子四叉树时，错误使用boundary_BR->x / 2计算边界，导致子象限范围不断偏移，Boid被错误分配，触发无意义分支。
修复：基于当前象限的宽高计算中线，再确定子象限边界：

float midX = this->boundary_TL->x + (this->boundary_BR->x - this->boundary_TL->x) / 2;
float midY = this->boundary_TL->y + (this->boundary_BR->y - this->boundary_TL->y) / 2;

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

2. boids数组未初始化 #

问题：构造函数中声明了数组但未将元素初始化为nullptr，导致垃圾指针被传入PushToBranch，触发无效插入和分支。
修复：添加初始化循环：

this->boids = new Boid*[max_Nodes];
for (unsigned short i = 0; i < max_Nodes; ++i) {
    this->boids[i] = nullptr;
}

3. 分支后指针未置空 #

问题：分支后删除max_Nodes、max_Depth和boids但未置空，存在误访问导致的未定义行为风险。
修复：删除后立即置空指针：

delete[] this->boids;
this->boids = nullptr;
delete this->max_Nodes;
this->max_Nodes = nullptr;
delete this->max_Depth;
this->max_Depth = nullptr;

4. PushToBranch边界判断逻辑重复 #

问题：使用<=判断边界，可能导致Boid被重复分配到左/上象限，集中触发分支。
修复：用中线做判断，区分左右/上下象限：

void Quad::PushToBranch(Boid* boid)
{
    float midX = this->boundary_TL->x + (this->boundary_BR->x - this->boundary_TL->x) / 2;
    float midY = this->boundary_TL->y + (this->boundary_BR->y - this->boundary_TL->y) / 2;

    if (boid->position->x < midX) {
        if (boid->position->y < midY) { // TL
            this->TL->Insert(boid);
        } else { // BL
            this->BL->Insert(boid);
        }
    } else {
        if (boid->position->y < midY) { // TR
            this->TR->Insert(boid);
        } else { // BR
            this->BR->Insert(boid);
        }
    }
}

5. 析构函数优化 #

问题：删除指针后未置空，存在重复删除风险。
修复：删除后立即置空所有指针：

Quad::~Quad()
{
    delete this->boundary_TL;
    this->boundary_TL = nullptr;
    delete this->boundary_BR;
    this->boundary_BR = nullptr;

    if (this->TL == nullptr) {
        delete this->max_Depth;
        this->max_Depth = nullptr;
        delete this->max_Nodes;
        this->max_Nodes = nullptr;
        delete[] this->boids;
        this->boids = nullptr;
    }

    delete this->TL;
    this->TL = nullptr;
    delete this->TR;
    this->TR = nullptr;
    delete this->BL;
    this->BL = nullptr;
    delete this->BR;
    this->BR = nullptr;
    delete this->nodes_Remaining;
    this->nodes_Remaining = nullptr;
}

内容的提问来源于stack exchange，提问作者Oscar James Pope-Lenkowiec