Je dois élaborer un Quadtree n'ayant que trois allocations de mémoire.
Les allocations doivent être séparées en deux parties : une pour le Quadtree(représenter par un tas) et l'autre, c'est un ensemble de points (représenter par une liste chaînée qui pointe sur le représentant de mon ensemble de points et le suivant)
Le problème est que je suis totalement perdue pour la construction du quadtree pouvez-vous m'aiguiller s'il vous plaît ?
Voici le programme et les algorithmes que j'ai faits :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define LIMITE 2
#define MAX 2
#define X 10
#define Y 10
#define H 10
typedef struct Carre{
int x;
int y;
int largeur;
int hauteur;
}Carre;
typedef struct Quadtree{
int nombre_particule;
Liste_Points pts;
Carre tree_carre;
struct Quadtree * northWest;
struct Quadtree * northEast;
struct Quadtree * southWest;
struct Quadtree * southEast;
}Quadtree , *Arbre;
void information(Quadtree **tab , int indice){
/*
Ajout dans le Tas les informations dont on a besoin comme le nombre de particules ,
est une liste chaînée de point
*/
tab[indice]->nombre_particule = 0;
for (int i = 0; i < MAX; i++){
ajout_fin(tab[indice]->pts , 0 , 0);
}
}
void initialisation_quadtree(Quadtree ** tab , int taille , int dimension){
/*
initialisation du quadtree
*/
tab = (Quadtree*)malloc(sizeof(Quadtree)* taille);
if(tab == NULL) exit(1);
for(int i = 0 ; i < taille ; i++){
if( i == 0){
/**********coordonnée du carré **********/
tab[i]->tree_carre.x = 0;
tab[i]->tree_carre.y = 0;
tab[i]->tree_carre.largeur = dimension;
tab[i]->tree_carre.hauteur = dimension;
}
if (i < (taille - 1) / 4){
tab[i]->northWest = &tab[4*i + 1];//pointeur vers l'un des 4 fils du quadtree
/**********coordonnée du carré **********/
tab[i]->northWest->tree_carre.x = 0;
tab[i]->northWest->tree_carre.y = 0;
tab[i]->northWest->tree_carre.largeur = dimension / 2;
tab[i]->northWest->tree_carre.hauteur = dimension / 2;
tab[i]->northEast = &tab[4*i + 2];//pointeur vers l'un des 4 fils du quadtree
/**********coordonnée du carré **********/
tab[i]->northEast->tree_carre.x = 0;
tab[i]->northEast->tree_carre.y = dimension / 2;
tab[i]->northEast->tree_carre.largeur = dimension / 2;
tab[i]->northEast->tree_carre.hauteur = dimension;
tab[i]->southWest = &tab[4*i + 3];//pointeur vers l'un des 4 fils du quadtree
/**********coordonnée du carré **********/
tab[i]->southWest->tree_carre.x = dimension / 2;
tab[i]->southWest->tree_carre.y = 0;
tab[i]->southWest->tree_carre.largeur = dimension ;
tab[i]->southWest->tree_carre.hauteur = dimension / 2;
tab[i]->southEast = &tab[4*i + 4];//pointeur vers l'un des 4 fils du quadtree
/**********coordonnée du carré **********/
tab[i]->southEast->tree_carre.x = dimension / 2;
tab[i]->southEast->tree_carre.y = dimension / 2;
tab[i]->southEast->tree_carre.largeur = dimension ;
tab[i]->southEast->tree_carre.hauteur = dimension ;
}
dimension = dimension / 2;
}
}
int recherche(){
/*
pas trop d'idée
*/
}
int ajout_points(Quadtree **tab , int taille , Points point){
/*
On ajoute un point en faisant les trois cas possibles.
i <- 0
Tant que i < taille
//1er cas : si tab[i] ->nombre_particule < limite_points + 1
alors ajouter le point après le dernier point ajouté dans l'ensemble de points appelé set
set[dernier + 1]->pts.x <- point.x
set[dernier + 1]->pts.y <- point.y
renvoie -1 // on ne change pas de représentant.
//2e cas : sinon on utilise la fonction recherche (renvoie le représentant du nœud suivant.)
//3e cas : si on a atteint les feuilles alors on stocke les points dans les feuilles
*/
}
// int main(){
// }
Je ne perçois pas trop ce que tu veux faire, mais normalement dans un tas, il n'y a pas besoin de pointeur vers les fils. On les retrouvent par calcul.
D'ailleurs, à la place de :
tab[i]->northWest = &tab[4*i + 1];//pointeur vers l'un des 4 fils du quadtree
/**********coordonnée du carré **********/
tab[i]->northWest->tree_carre.x = 0;
tab[i]->northWest->tree_carre.y = 0;
tab[i]->northWest->tree_carre.largeur = dimension / 2;
tab[i]->northWest->tree_carre.hauteur = dimension / 2;
je ne sais pas si ça va dans le sens de la question, mais
1. on représente souvent un tas par un tableau qui contient un arbre binaire
la racine est à l'index 0
le fils gauche du noeud n est à l'index 2n+1, le fils droite à 2n+2
2. ça s'adapte facilement aux arbres de degré 4
la racine est à l'indice 0
les fils du noeud n sont en 4n+k; avec k de 1 à 4 -- ou 4n + 1 +k, avec k de 0 à 3, comme vous préférez.
et bien sur le père d'un noeud est en floor( (n-1) / 4)
Ceci dit, qu'on fasse ça ou autre chose, il faut quand même s'arranger pour traiter les 4 fils comme un tableau, pour ne pas avoir à faire du code copié-collé pour les 4. C'est degueu.
Le tas est un bon moyen d'encoder un arbre implicitement, mais il faut qu'il soit presque complet, avec la dernière ligne alignée à gauche. Ce n'est pas forcément le cas dans un quadtree, puisque chacun des 4 fils sera une partie fixe du sous ensemble (par exemple le premier fils en haut à gauche).
Et donc si tu as plus de détails à des endroits quelconques, tu auras davantage de profondeur à certains endroits et pas d'autres.
Cependant, si on considère que la profondeur est fixe pour tous, alors oui, tu peux avoir un arbre binaire complet, et donc un tas dans lequel l'index des fils est implicite (calculté par 2n+1 et 2n+2 comme il a été dit), et aussi les coordonnées du carré sont également implicites ! Tu n'as pas besoin de stocker par chaque noeud des coordonnées, elles se calculent en descendant l'arbre !
(un tas, c'est un arbre binaire (presque) complet, avec un calcul implicite pour aller aux noeuds fils (on a besoin de ça), et également une relation d'ordre pour trier, mais ça ici on s'en fout), je pense que ton prof a parlé de tas uniquement pour la partie calcul implicite du fils)
Chaque feuille contient donc uniquement une liste de points !
Donc, du coup, si j'ai bien compris pour chaque feuille, je stocke la liste chaînée de points, puis je modifie le calcul des coordonnées du carré, mais j'ai une autre question, mon prof m'a dit que je devais mettre un pointeur sur l'adresse sur les quatre fils, mais je ne sais pas trop pourquoi moi non plus.Ça veut dire que lorsque le tableau est initialisé, et par exemple, si je veux parcourir le tas pour l'afficher, je peux le faire de la manière suivante :
void afficher(Tas t , int taille , int i /*i = 0*/){
if(i >= taille) return;
if(t[i]->nombre_particule > 0){
printf(....);
}
if(tab[i]->northwest->nombre_particule >0){
printf(...);
}
if(tab[i]->northEast->nombre_particule >0){
printf(...);
}
if(tab[i]->southwest->nombre_particule >0){
printf(...);
}
if(tab[i]->southEast->nombre_particule >0){
printf(...);
}
afficher(t , taille , i + 4);
}
déjà, tu dis qu'il faut limiter le nombre d'allocations. Donc pour le quadtree sous forme de tas, ok je comprends.
Mais par contre, tes points sont dans une liste chainée ? On alloue un max avec une liste chainée.
Dans quel sens veux tu retrouver tes données ?
Car le concept du quadtree, c'est que tu descends sur une zone via l'arbre, et tu as donc très rapidement la liste des points dans cette zone. (si tu stockes bien une liste dans chaque feuille).
Est ce que c'est ça que tu veux faire ?
Moi c'est vraiment ton histoire de liste chainée alors qu'il y aune contrainte du nombre d'allocations qui me gène.
Oui, mes points sont dans une liste chaînée, je te montre comment j'ai fait et je l'ai mis dans la structure de mon quadtree ensuite il faut que change l’initialisation du quadtree pour qu'au niveau des feuilles, j'ai ma liste chaînée de points.
@LaureDeze: Je me demande s'il ne serait pas souhaitable que tu nous donne l'énoncé de ton problème pour qu'on puisse mieux te guider. Parce que, comme je le perçois, tu fais des choses, soit en double, soit de la mauvaise façon. Et moi non plus, je ne comprend pas le besoin des listes chaînées. Et pourquoi un tas? Est-ce que tu places tes éléments dans un certain ordre? Lequel?
@michelbillaud: Ta formule pour le quadtree sous forme de tableau fonctionne bien: Si la racine est en 0: les fils sont pere * 4 + k (k = 1, 2, 3, 4) pere = (fils - 1) / 4 (division entière)
edit: Alors, je me suis un peu promené sur le web et surtout sur Wikipedia. J'imagine la situation suivante: J'ai un carré avec un certain nombre de particules et de dimension D. Je divise ce carré en quatre (quad) carrés dans les directions NE, NW, SE, SW et de dimensions D/2. Je suppose qu'on pourra savoir le nombre de particules dans chacun de ces quatre "sous-carrés". Je me place au centtre de chacun de ces carrés et je fais la même chose de façon récursive, jusqu'à une certaine limite (précision). Dans ce cas, on aurait un quadtree complet. Dans les carrés de dernier niveau, on aurait la liste (chaînée) des points (particules) dans ces carrés. Ou bien c'est le contraire. On veut savoir combien de particules se trouvent dans chaque niveau de carrés à partir d'une liste de points globale.
Si on descent jusqu'au niveau N (le niveau 0 est la racine), on aura besoin d'un tableau de longueur:
(4^(N+1) - 1) / (4 - 1)
pour le tas.
En remplaçant N par N-1 dans la formule, j'obtiens la position de la première feuille (en partant de 0)
- Toujours selon ma compréhension du problème, la dimension de chaque carré sera la moitié de celle de son père. Et le centre de chaque carré fils sera décalé de D/4 de la position du centre du carré père. Comment s'y retrouver? Si je pars de pere*4+1 et que je numérote judicieusement les fils de 0 à 3. Je pourrais avoir les +x et -x et les +y et -y en jouant sur les bits 0 et 1 de la position.
Le Tout est souvent plus grand que la somme de ses parties.
creer un quadtree à l'aide d'un tas
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Le Tout est souvent plus grand que la somme de ses parties.