quadtree.c

/*
** EPITECH PROJECT, 2024
** B-MUL-100-LYN-1-1-myradar-aurelien.demeusy
** File description:
** quadtree.c
*/

#include "include/structs.h"
#include "include/my.h"
#include <stdlib.h>

quadnode_t *create_node(rect_t boundary, int capacity)
{
    quadnode_t *node = malloc(sizeof(quadnode_t));

    node->region = boundary;
    node->capacity = capacity;
    node->count = 0;
    node->ac = malloc(capacity * sizeof(ac_t));
    node->nw = NULL;
    node->ne = NULL;
    node->sw = NULL;
    node->se = NULL;
    node->isDivided = 0;
    return node;
}

void subdivide(quadnode_t *node)
{
    float x = node->region.x;
    float y = node->region.y;
    float halfwidth = node->region.width / 2;
    float halfheight = node->region.height / 2;

    node->nw = create_node((rect_t){x, y, halfwidth,
    halfheight}, node->capacity);
    node->ne = create_node((rect_t){x + halfwidth, y,
    halfwidth, halfheight}, node->capacity);
    node->sw = create_node((rect_t){x, y + halfheight,
    halfwidth, halfheight}, node->capacity);
    node->se = create_node((rect_t){x + halfwidth,
    y + halfheight, halfwidth, halfheight}, node->capacity);
    node->isDivided = 1;
}

int contains(rect_t rect, ac_t *ac)
{
    return (ac->x >= rect.x && ac->x + ac->width <= rect.x + rect.width &&
            ac->y >= rect.y && ac->y + ac->height <= rect.y + rect.height);
}

void insert(quadnode_t *node, ac_t ac)
{
    if (!contains(node->region, &ac)) {
        return;
    }
    if (node->count < node->capacity) {
        node->ac[node->count] = ac;
        node->count += 1;
        return;
    }
    if (!node->isDivided) {
        subdivide(node);
    }
    insert(node->nw, ac);
    insert(node->ne, ac);
    insert(node->sw, ac);
    insert(node->se, ac);
}

void query(quadnode_t *node, rect_t range, ac_t *found, int *foundCount)
{
    if (!contains(node->region, &(ac_t){range.x, range.y})) {
        return;
    }
    for (int i = 0; i < node->count; i++) {
        if (contains(range, &node->ac[i])) {
            (*foundCount)++;
            found[(*foundCount)] = node->ac[i];
        }
    }
    if (!node->isDivided) {
        return;
    }
    query(node->nw, range, found, foundCount);
    query(node->ne, range, found, foundCount);
    query(node->sw, range, found, foundCount);
    query(node->se, range, found, foundCount);
}