Untitled

class QuadTree {
public:
    QuadTree(double* boundary, int capacity) : depth(300) {
        isDivided = false;
        this->capacity = capacity;

        this->boundary[0] = boundary[0];
        this->boundary[1] = boundary[1];
        this->boundary[2] = boundary[2];
        this->boundary[3] = boundary[3];

        children[0] = nullptr;
        children[1] = nullptr;
        children[2] = nullptr;
        children[3] = nullptr;
    }
    bool insert(Particle& particle) {
        // if ball is not within bounds than do not insert 
        if (!contains(particle)) {
            return false;
        }
        // if capacity is not reached than add particle to points vector
        if (points.size() < capacity) {
            points.push_back(particle);
        //    nSquare(points);
            return true;
        }
        // if max depth is reached than end the insertions
        if (depth == 0) {
            points.push_back(particle);
            return false;
        }
        if(!isDivided) { // if capacity is reached than subdivide
            subdivide();
            // insert points into all children
            for (auto& point : points) {
                for (int i = 0; i < 4; ++i) {
                    if (children[i]->insert(point)) {
                        break;
                    }
                }
            }
        }

        for (int i = 0; i < 4; i++) {
            if (children[i]->insert(particle)) {
                return true;
            }
        }
        
        return false;
    }
    void update(std::vector<Particle> &particle) {
        isDivided = false;
        points.clear();
        for (int i = 0; i < particle.size(); i++) {
            insert(particle[i]);
            
        }
        traverseCollisions(particle);
    }
    void draw() {
        if (isDivided) {
            for (int i = 0; i < 4; i++) {
                children[i]->draw();
            }
        }
        else {
            Graphics::rectangleOutlinePoints(boundary[0], boundary[1], boundary[2], boundary[3], COLOR_GREEN);
        }
    }

    void nSquare(std::vector<Particle>& balls) {
        for (int a = 0; a < balls.size(); a++) {
            for (int b = 0; b < balls.size(); b++) {
                if (isColl(balls[a], balls[b])) {
                    resolveCollisionsID(balls[a].id, balls[b].id);
                }
            }
        }
    }

    void traverseCollisions(std::vector<Particle> &balls) {
        for (int i = 0; i < balls.size(); i++) {
            double x = balls[i].currentPos[0];
            double y = balls[i].currentPos[1];
            double r = balls[i].radius;
            double ballBound[4] = { x - r,y - r,x + r,y + r };
            
            // Traverse the QuadTree and test the ball against intersecting nodes
            traverseAndTestNode(balls[i], ballBound, this);
        }
    }
    void traverseAndTestNode(Particle& ball, const double ballBound[4], QuadTree* node) {
        // Check if the ball intersects with the current node
        if (!node->intersects(ballBound)) {
            return;
        }

        // Test the ball against points in the current node
        for (Particle& point : node->points) {
            if (isColl(ball, point)) {
                resolveCollisionsID(ball.id, point.id);
            }
        }

        // Recursively traverse the children nodes
        if (node->isDivided) {
            for (int i = 0; i < 4; i++) {
                traverseAndTestNode(ball, ballBound, node->children[i].get());
            }
        }
    }



    bool intersects(const double ballBound[4]) {
        // Check if the ball's bounding box intersects with the node's boundary
        if (ballBound[0] > boundary[0] && ballBound[2] < boundary[2] && ballBound[1] > boundary[1] && ballBound[3] < boundary[3]) {
            return true;
        }
        else { return false; }
    }

private:
    bool isDivided;
    double boundary[4];
    int capacity;
    int depth;
    std::vector<Particle> points;
    std::unique_ptr<QuadTree> children[4];
    void subdivide() {
        // makes it easier to read the definitions for nw,ne,sw,se
        double x = boundary[0];
        double y = boundary[1];
        double w = (boundary[2] - boundary[0]) / 2;
        double h = (boundary[3] - boundary[1]) / 2;
        // determines the new boundaries for the subquadrants
        double nw[] = { x, y, x + w, y + h };
        double ne[] = { x + w, y, x + 2 * w, y + h };
        double sw[] = { x, y + h, x + w, y + 2 * h };
        double se[] = { x + w, y + h, x + 2 * w, y + 2 * h };
        // create the instances of the new quadtrees for all four children
        children[0] = std::make_unique<QuadTree>(nw, this->capacity);
        children[1] = std::make_unique<QuadTree>(ne, this->capacity);
        children[2] = std::make_unique<QuadTree>(sw, this->capacity);
        children[3] = std::make_unique<QuadTree>(se, this->capacity);
        // Set the depth of the child QuadTrees
        for (int i = 0; i < 4; ++i) {
            children[i]->depth = this->depth - 1;
        }
        // subdivision has occureced so isDivided is set to true
        isDivided = true;
    }
    bool contains(Particle& particle) {
        double px = particle.currentPos[0];
        double py = particle.currentPos[1];
        if (px > boundary[0] && px < boundary[2] && py > boundary[1] && py < boundary[3]) {
            return true;
        }
        else { return false; }
    }
};