quadtree.c

#include "quadtree.h"

bool quadtree_is_leaf(node *nd)
{
    return (NULL == nd->child[0]);
}

int32_t quadtree_get_depth_from_image_size(int32_t sizex)
{
    return (int32_t)log2(sizex);
}

node *quadtree_tree_create(int32_t depth)
{
    node *a = calloc(1, sizeof(node));
    if (depth > 0)
    {
        // printf("Create %d\n", depth);
        for (int32_t i = 0; i < CHILDREN; i++)
        {
            a->child[i] = quadtree_tree_create(depth - 1);
        }
    }
    return a;
}

int32_t quadtree_max(int32_t x, int32_t y)
{
    return (x >= y ? x : y);
}

int32_t quadtree_array_max(int32_t size, int32_t tab[size])
{
    int32_t m = INT_MIN;
    for (int32_t i = 0; i < size; i++)
    {
        m = quadtree_max(m, tab[i]);
    }
    return m;
}

int32_t quadtree_depth(node *a)
{
    int32_t p[CHILDREN] = {0};
    if (quadtree_is_leaf(a))
    {
        return 0;
    }
    else
    {
        for (int32_t i = 0; i < CHILDREN; i++)
        {
            p[i] = 1 + quadtree_depth(a->child[i]);
        }
        return quadtree_array_max(CHILDREN, p);
    }
}

void quadtree_print(node *arbre, int32_t decal, char *sep)
{
    if (NULL != arbre)
    {
        for (int32_t i = 0; i < decal; i++)
        {
            printf("%s", sep);
        }
        printf("%d\n", (uint32_t)arbre->data);
        decal++;
        if (!quadtree_is_leaf(arbre))
        {
            for (int32_t i = 0; i < CHILDREN; i++)
            {
                quadtree_print(arbre->child[i], decal, sep);
            }
        }
    }
}

// Fonction utile pour les symétries
void quadtree_swap(void **ptr1, void **ptr2)
{
    void *tmp = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = tmp;
}

void quadtree_sum(node *arbre)
{
    if (!quadtree_is_leaf(arbre))
    {
        for (int32_t i = 0; i < CHILDREN; i++)
        {
            quadtree_sum(arbre->child[i]);
        }
        for (int32_t i = 0; i < CHILDREN; i++)
        {
            arbre->data += arbre->child[i]->data;
        }
    }
}

node *quadtree_position(int32_t li, int32_t col, node *a, int32_t d)
{
    node *crt = a;
    do
    {
        int32_t ligne = (li >> d) & 1;          // Permet de sélectionne le bit à considérer en fonction de la profondeur; Exemple: 10 >> 1 = 1
        int32_t colonne = (col >> d) & 1;       //Exemple: 10 >> 1 = 1;
        int32_t index = (ligne << 1) | colonne; // Exemple: 1<<1 = 10 | 1(col) = 11=>3

        crt = crt->child[index];
        d--;
    } while (!quadtree_is_leaf(crt));
    return crt;
}

double quadtree_position_value(int32_t li, int32_t col, node *a, int32_t d)
{
    node *crt = a;
    do
    {
        int32_t ligne = (li >> d) & 1;          // Permet de sélectionne le bit à considérer en fonction de la profondeur; Exemple: 10 >> 1 = 1
        int32_t colonne = (col >> d) & 1;       //Exemple: 10 >> 1 = 1;
        int32_t index = (ligne << 1) | colonne; // Exemple: 1<<1 = 10 | 1(col) = 11=>3

        crt = crt->child[index];
        d--;
    } while (!quadtree_is_leaf(crt));
    return crt->data;
}

void quadtree_matrix2tree(matrix *mat, node *arbre)
{
    int32_t d = quadtree_depth(arbre) - 1;
    for (int32_t li = 0; li < mat->lin; li++)
    {
        for (int32_t co = 0; co < mat->col; co++)
        {
            node *crt = quadtree_position(li, co, arbre, d);
            crt->data = mat->data[li][co];
        }
    }
}

void quadtree_tree2matrix(node *tree, matrix *mat)
{
    int32_t d = quadtree_depth(tree) - 1;
    for (int32_t li = 0; li < mat->lin; li++)
    {
        for (int32_t co = 0; co < mat->col; co++)
        {
            mat->data[li][co] = quadtree_position_value(li, co, tree, d);
        }
    }
}

// OK
void quadtree_horizontal_symetry(node *tree)
{
    if (NULL != tree)
    {
        for (uint32_t i = 0; i < CHILDREN; i += 1)
        {
            quadtree_horizontal_symetry(tree->child[i]);
        }
        quadtree_swap((void**)&tree->child[0], (void**)&tree->child[1]);
        quadtree_swap((void**)&tree->child[2], (void**)&tree->child[3]);
    }
}

// OK
void quadtree_vertical_symetry(node *tree)
{
    if (NULL != tree)
    {
        for (uint32_t i = 0; i < CHILDREN; i += 1)
        {
            quadtree_vertical_symetry(tree->child[i]);
        }
        quadtree_swap((void**)&tree->child[0], (void**)&tree->child[2]);
        quadtree_swap((void**)&tree->child[1], (void**)&tree->child[3]);
    }
}

void quadtree_central_symetry(node *tree)
{
    quadtree_vertical_symetry(tree);
    quadtree_horizontal_symetry(tree);
}

void quadtree_tree_destroy(node **tree)
{
    if (NULL != *tree)
    {
        if (!quadtree_is_leaf(*tree))
        {
            for (uint32_t i = 0; i < CHILDREN; i += 1)
            {
                quadtree_tree_destroy(&(*tree)->child[i]);
            }
        }
        else
        {
            free(*tree);
        }
    }
}